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?

$\endgroup$
  • $\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 Sep 22 '15 at 10:40
  • $\begingroup$ Do some people "in the know" think that the twin prime conjecture might be undecidable? $\endgroup$ – Dominic van der Zypen Sep 22 '15 at 10:49
1
$\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.

$\endgroup$
  • 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 Sep 22 '15 at 10:55
  • 1
    $\begingroup$ Dominic, I'm not sure that this is actually the answer to your question. $\endgroup$ – Joel David Hamkins Sep 22 '15 at 11:43
  • 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 Sep 22 '15 at 14:32
  • 1
    $\begingroup$ @NoahSchweber, how can you assert such a definitive statement about what is possible? It seems to me that we don't really know anything about it with certainty. $\endgroup$ – Joel David Hamkins Sep 22 '15 at 15:33
  • 1
    $\begingroup$ @JoelDavidHamkins Sorry, that was my bad, you're absolutely right. I was unclear - I should have said "there is no obvious direct relationship." I was just getting at the confusion between "an atomic fact about the function is undecidable in a specific system" and "the function is not computable", which is a subtle issue (at least, it tripped me up when I was learning this). $\endgroup$ – Noah Schweber Sep 22 '15 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.