1
$\begingroup$

Consider the following function $f: \omega\to \{0,1\}$:

  • Set $f(n) = 1$ if for all $k\in \omega$ there are prime numbers $p,q > k$ such that $n = p-q$, and
  • set $f(n) = 0$ otherwise.

(Trivially, if $n$ is odd, we have $f(n) = 0$. Moreover, the question whether $f(2) = 1$ is the subject of the twin prime conjecture.)

Is $f$ computable?

Improve this question
$\endgroup$
2
  • $\begingroup$ Likely it is just $f(n) = 0$ if $n$ is odd, and $f(n) = 1$ if $n$ is even, and thus $f$ is computable -- but whether this really is so is of course an open problem. $\endgroup$
    – Stefan Kohl ♦
    Commented Sep 22, 2015 at 10:40
  • $\begingroup$ Do some people "in the know" think that the twin prime conjecture might be undecidable? $\endgroup$
    – Dominic van der Zypen
    Commented Sep 22, 2015 at 10:49

1 Answer 1

Reset to default
2
$\begingroup$

I once heard Harvey Friedman suggest that the set of prime-differences, that is, the set of all natural numbers $n$ for which there are primes $p,q$ with $p-q=n$, as a possible candidate for all we knew for an intermediate Turing degree — a noncomputable set between $0$ and $0'$ — that was natural, not specifically constructed to have that feature.

Improve this answer
$\endgroup$
13
  • 3
    $\begingroup$ Is there a specific reason for the assumption that the set of prime differences has a reasonable chance to be noncomputable? -- I think the basic heuristics pretty clearly suggests it's just the set of even natural numbers. $\endgroup$
    – Stefan Kohl ♦
    Commented Sep 22, 2015 at 10:55
  • 1
    $\begingroup$ Dominic, I'm not sure that this is actually the answer to your question. $\endgroup$
    – Joel David Hamkins
    Commented Sep 22, 2015 at 11:43
  • 1
    $\begingroup$ @JoelDavidHamkins - I accepted your answer because it seemed to me that the answer to my question depends on the decidability of the Twin Primes Conjecture, but now I'm confused whether that's the case... $\endgroup$
    – Dominic van der Zypen
    Commented Sep 22, 2015 at 14:00
  • 2
    $\begingroup$ @DominicvanderZypen There's no direct relationship - the function could be computable even if the twin prime conjecture fails, or is undecidable. $\endgroup$
    – Noah Schweber
    Commented Sep 22, 2015 at 14:32
  • 2
    $\begingroup$ Basically, something can be "nonconstructively computable" - that is, we can have a definable set/function $X$ and a program $\Phi$ which computes $X$ but such that there is no proof in our theory that $\Phi$ (or any other specific program) computes $X$. This is a weird mix of classical and constructive flavors, but is a key feature of the subject. $\endgroup$
    – Noah Schweber
    Commented Jan 17, 2020 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .