# Can the twin prime problem be solved with a single use of a halting oracle?

It occurred to me that if it were possible to determine whether a given program halts, that could be used to answer the twin primes conjecture

A) Write a program which takes input n and then counts upward until it's found n pairs of twin primes B) Write a program which for any input n returns true if A halts and false otherwise C) Write a program which counts upward running B on every n until B returns false D) If C halts, there are finitely many twin primes, otherwise infinite.

I was wondering if there was a way to do this without nesting halting problems... ie if you only get one chance to ask whether a program halts, is that sufficient to answer the twin primes conjecture

-
The title doesn't match the question. Perhaps you could change the title to something like, "Can the twin prime problem be solved with a single use of a halting oracle?". –  S. Carnahan Jul 23 '11 at 6:16
.. and the answer would be yes, to S. Carnahan's rewrite, if you get the code number for the program correct. Gerhard "Ask Me About System Design" Paseman, 2011.07.22 –  Gerhard Paseman Jul 23 '11 at 6:24
that is a better name. thanks –  dspyz Jul 23 '11 at 7:04
I feel like it is worth remarking that there are reasonable strengthinings of the twin prime conjecture which are $\Pi_1$. For example, in the notation of bit.ly/n8AyP4, the statement that $10^{-100}<\frac{2C_2n}{\pi_2(n)\ln(n)^2}<10^{100}$ for all $n$. –  Kevin Ventullo Jul 24 '11 at 0:38

Note that your program is actually using a lot more than the halting oracle $0'$. It is using $0''$ — the halting oracle for machines using the $0'$ oracle. The oracle $0''$ is capable of deciding any $\Pi_2$ statement (like the twin prime conjecture) with a single definite query. Let's look at the twin prime conjecture in further detail.

For any fixed $N$, the $\Pi_1$ statement "there are no twin prime pairs after $N$" can be resolved by a single query to $0'$. Thus, if there are only finitely many twin primes, then there is a single query to $0'$ that will let us know that — the catch is that we don't know which query will give us the answer. Note that we can still get by with finitely many queries to $0'$ by trying all natural numbers $N$ in order until we get a positive answer to the query "there are no twin prime pairs after $N$" (assuming the twin prime conjecture is actually false).

To say "there are infinitely many twin primes" is a $\Pi_2$ statement. In general, one cannot positively decide a $\Pi_2$ statement by a single query to $0'$. However, the twin prime conjecture is a very specific $\Pi_2$ statement, so these general case arguments do not necessarily apply.

For example, it is conceivable that the existence of infinitely many twin primes is in fact equivalent to the existence of a magic twinmaker, which is a certain $\Pi_1$ property of a natural number. In this case, we could resolve the twin prime conjecture by making a single query to $0'$: we could ask whether "there are no twin prime pairs after $N$" for some suitably chosen $N$, or we could ask whether "$N$ is a magic twinmaker" for some suitably chosen $N$. Again, the catch is that we don't know $N$ and, moreover, we don't even know which of the two questions to ask!

However, the situation is not so bad, we could still get by with only finitely many queries to $0'$ without making lucky guesses. We go through all the natural numbers $N$ in order, in each case asking whether "there are no twin primes after $N$" or whether "$N$ is a magic twinmaker" until we get a positive answer. Since one of the two cases must occur for some $N$, we will eventually get a positive answer.

Unfortunately, this magic twinmaker concept is completely made up for the purpose of illustration. It could be that the twin prime conjecture is a generic $\Pi_2$ statement, in which case we cannot expect to decide it positively with a single query to $0'$.

-

I have no disagreement with the answer of François Dorais, but I have a different take on the problem.

Let $S$ be any statement of number theory, such as the Twin prime conjecture, Goldbach's conjecture, etc. of any quantifier complexity.

Let us say that $S$ is $ZF$-decidable if $ZF$ either proves $S$, or $ZF$ proves the negation of $S$ (here $ZF$ is Zermelo-Fraenkel set theory).

Proposition. Under the assumption that $ZF$ is arithmetically sound (i.e., it proves no false arithmetical sentence), there is a recursive function $f$ such that truth of any $ZF$-decidable statement $S$ of number theory can be determined by one query "Is $f(S)$ $\in K?$" (where $S$ is identified with its the Gödel number, and $K$ is the halting oracle).

The above proposition follows immediately from the well-known fact that $K$ is a complete r.e. set; i.e., every recursively enumerable set $X$ is Turing-reducible to $K$; indeed, given such an $X$ there is a even a 1-1 recursive function $f$ such that $n\in X$ iff $f(n) \in K$. The $X$ at work here is the set of (Gödel numbers of) theorems of $ZF$.

Therefore, if the twin prime conjecture is decidable within $ZF$, and $ZF$ is arithmetically sound, then its truth-value can be determined by a single query to the halting oracle.

Two closing comments are in order:

(1) It is well-known that if a statement $S$ of number theory is $ZFC$-decidable (where $ZFC$ is $ZF$ plus the axiom of choice), then $S$ is $ZF$-decidable. The proof is nontrivial and makes a detour through Gödel's constructible universe, and absoluteness considerations (this is due to Kreisel; according to McIntyre, it was surprisingly missed by Gödel himself).

(2) There is nothing special about $ZF$ here, the above proposition holds for any axiomatic system $T$ with a recursive set of axioms, including those weaker than $ZF$, such as $PA$ (Peano arithmetic) or stronger than $ZF$, e.g., $ZF$ with "large cardinals".

-
If the twin prime conjecture is decidable in ZF, and ZF is arithmetically (or $\Sigma^0_2$) sound, then its truth value can be determined by an algorithm using no oracle whatsoever: enumerate all ZF proofs until you find a proof of the conjecture or of its negation. –  Emil Jeřábek Nov 29 '13 at 14:33

I just saw according to this thread that it's an open problem: http://boards.straightdope.com/sdmb/archive/index.php/t-569801.html

-
@GH: I am afraid you are confusing the fact that there is no automatic way to solve the halting problem (for all computer programs), with the fact that perhaps we can prove that a particular program halts. The question talks about one particular computer program, which is unknown whether it halts or not; indeed this particular program halts iff the twin conjecture holds. –  boumol Jul 23 '11 at 10:31
@GH: One of the ways to formulate this kind of question is as follows: Is an explicit algorithm A using the oracle for the halting problem known such that A answers “Yes” if and only if the twin prime conjecture holds? –  Tsuyoshi Ito Jul 23 '11 at 15:03
@boumol: I disagree. The question asks how can we decide the twin prime conjecture with a halting oracle. Actually within a formal system like ZFC one can reformulate the twin prime conjecture to a single halting problem: the program generates all conclusions of ZFC and stops if the twin prime conjecture is above them. This program halts iff the twin prime conjecture is valid within ZFC. –  GH from MO Jul 23 '11 at 19:22
@GH "There is no halting oracle" No, this is incorrect. There is a halting oracle. There's just no computable halting oracle. –  Sam Alexander Jul 23 '11 at 21:12
I dropped the condition “use the oracle only once” by mistake. What I meant to say was that one way to formulate this question rigorously is: Is an explicit algorithm A using the oracle for the halting problem only once known such that A answers “Yes” if and only if the twin prime conjecture holds? Without some kind of formulation, “The twin prime conjecture is (or is not) decidable” does not make much sense. –  Tsuyoshi Ito Jul 23 '11 at 21:21