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

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

2011-07-23T06:06:00Z

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

Answer by dspyz for Can the twin prime problem be solved with a single use of a halting oracle?

2011-07-23T08:51:30Z

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

Answer by François G. Dorais for Can the twin prime problem be solved with a single use of a halting oracle?

2011-07-23T17:41:37Z

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

Answer by Ali Enayat for Can the twin prime problem be solved with a single use of a halting oracle?

2011-07-25T16:34:47Z

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