# Computability of prime difference function

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?

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

## 1 Answer

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.

• 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. – Stefan Kohl Sep 22 '15 at 10:55
• Dominic, I'm not sure that this is actually the answer to your question. – Joel David Hamkins Sep 22 '15 at 11:43
• @DominicvanderZypen There's no direct relationship - the function could be computable even if the twin prime conjecture fails, or is undecidable. – Noah Schweber Sep 22 '15 at 14:32
• @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. – Joel David Hamkins Sep 22 '15 at 15:33
• @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). – Noah Schweber Sep 22 '15 at 15:37