# 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

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.