Can the twin prime problem be solved with a single use of a halting oracle? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T09:31:56Z http://mathoverflow.net/feeds/question/71050 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71050/can-the-twin-prime-problem-be-solved-with-a-single-use-of-a-halting-oracle Can the twin prime problem be solved with a single use of a halting oracle? dspyz 2011-07-23T06:06:00Z 2011-07-25T16:34:47Z <p>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</p> <p>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.</p> <p>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</p> http://mathoverflow.net/questions/71050/can-the-twin-prime-problem-be-solved-with-a-single-use-of-a-halting-oracle/71057#71057 Answer by dspyz for Can the twin prime problem be solved with a single use of a halting oracle? dspyz 2011-07-23T08:51:30Z 2011-07-23T08:51:30Z <p>I just saw according to this thread that it's an open problem: <a href="http://boards.straightdope.com/sdmb/archive/index.php/t-569801.html" rel="nofollow">http://boards.straightdope.com/sdmb/archive/index.php/t-569801.html</a></p> http://mathoverflow.net/questions/71050/can-the-twin-prime-problem-be-solved-with-a-single-use-of-a-halting-oracle/71075#71075 Answer by François G. Dorais for Can the twin prime problem be solved with a single use of a halting oracle? François G. Dorais 2011-07-23T17:41:37Z 2011-07-23T21:27:00Z <p>Note that your program is actually using a lot more than the halting oracle $0'$. It is using $0''$ &mdash; the halting oracle for machines using the $0'$ oracle. The oracle $0''$ is capable of deciding any <a href="http://en.wikipedia.org/wiki/Arithmetical_hierarchy" rel="nofollow">$\Pi_2$ statement</a> (like the twin prime conjecture) with a single definite query. Let's look at the twin prime conjecture in further detail.</p> <p>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 &mdash; 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).</p> <p>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.</p> <p>For example, it is conceivable that the existence of infinitely many twin primes is in fact equivalent to the existence of a <em>magic twinmaker</em>, 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! </p> <p>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.</p> <p>Unfortunately, this <em>magic twinmaker</em> 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'$.</p> http://mathoverflow.net/questions/71050/can-the-twin-prime-problem-be-solved-with-a-single-use-of-a-halting-oracle/71245#71245 Answer by Ali Enayat for Can the twin prime problem be solved with a single use of a halting oracle? Ali Enayat 2011-07-25T16:34:47Z 2011-07-25T16:34:47Z <blockquote> <p>I have no disagreement with the answer of François Dorais, but I have a different take on the problem.</p> </blockquote> <p>Let $S$ be <em>any</em> statement of number theory, such as the Twin prime conjecture, Goldbach's conjecture, etc. of any quantifier complexity.</p> <p>Let us say that $S$ is $ZF$-<em>decidable</em> if $ZF$ either proves $S$, or $ZF$ proves the negation of $S$ (here $ZF$ is Zermelo-Fraenkel set theory). </p> <blockquote> <p><strong>Proposition.</strong> 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 <strong>"Is $f(S)$ $\in K?$"</strong> (where $S$ is identified with its the Gödel number, and $K$ is the halting oracle).</p> </blockquote> <p>The above proposition follows immediately from the well-known fact that <strong>$K$ is a complete r.e. set</strong>; 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$.</p> <blockquote> <p>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.</p> </blockquote> <p>Two closing comments are in order:</p> <p>(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).</p> <p>(2) There is nothing special about $ZF$ here, the above proposition holds for <em>any</em> 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".</p>