Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
2  
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
add comment

3 Answers 3

up vote 14 down vote accepted

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'$.

share|improve this answer
add comment

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".

share|improve this answer
    
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
add comment

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

share|improve this answer
1  
@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
1  
@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
1  
@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
2  
@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
1  
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
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.