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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2011 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 2011 at 6:24
that is a better name. thanks – dspyz Jul 23 2011 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 2011 at 0:38

## 3 Answers

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

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

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

-

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 2011 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 2011 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 Jul 23 2011 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 2011 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 2011 at 21:21
show 5 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 73, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9310258626937866, "perplexity_flag": "head"}