# Decidability of prime gap sequences

Is the following problem undecidable?

Given a sequence of $n$ gaps $d_1,d_2,...,d_n$, does there exist a sequence of $n+1$ primes $p_1,p_2,...,p_{n+1}$ such that $p_{i+1} - p_i = d_i$ ?

If not, is the problem still undecidable if we pick a fixed $n$, e.g. only one gap (n=1), or only two gaps (n=2).

With undecidable I mean that you cannot build a Turing machine that given the sequence $d_1,...,d_n$ as input always halts and gives the correct answer.

• Suppose that there are no primes $p_{1},p_{2}$ with $p_{2}-p_{1} = d_{1}.$ How would your Turing machine know this? – Geoff Robinson Mar 28 '14 at 8:52
• @GeoffRobinson: that is the question, is there a formal proof that it is undecidable? – Marzio De Biasi Mar 28 '14 at 8:53
• Are the primes consecutive or not? (The wording suggests nonconsecutive.) – The Masked Avenger Mar 28 '14 at 9:12
• The prime k-tuples conjecture implies that the question is decidable. Current technology can only decide if a gap sequence is admissible, and can only say yes it is realized in finite time. – The Masked Avenger Mar 28 '14 at 9:26
• Harvey Friedman has suggested that the 1-gap case may be an example of a c.e. problem that is not decidable and also not equivalent to the halting problem. If this were true, it would be an instance of the long-sought natural examples of intermediate Turing degrees between $0$ and $0'$. – Joel David Hamkins Mar 28 '14 at 10:53

• Given two rationals $a<b$, can one decide whether there a zero of Reimann's zeta function whose real part belongs to $(a,b)$?
• Given a finite sequence of digits $w$, can one decide whether $w$ appears in the decimal expansion of $\pi$?
• Given an integer $n$, can one decide whether the Collatz sequence starting at $n$ eventually reaches $1$?
In all three cases, the answer is assumed to be positive for a trivial reason (in the first case, by simply checking whether $a<1/2<b$ or whether $a<-2n<b$ for some nonnegative integer $n$, in the second and third case by answering `yes' all the time) but proving this does not appear to be simpler than the general conjecture. I feel like your problem somewhat falls into this category.
• Minor correction: $\zeta(s)$ also has some trivial zeros. – user25199 Mar 28 '14 at 9:25