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



Can the twin prime problem be solved with a single use of a halting oracle?
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](http://en.wikipedia.org/wiki/Arithmetical_hierarchy) (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'$.


