This question is about whether every mathematical theorem can be reduced to the question of whether a single Turing machine halts. In particular, I'm interested in conjectures that are currently unproven.

For example: Wikipedia says that it's currently unknown whether there are any odd perfect numbers. Since it's decidable whether a given number is perfect, one could write a Turing machine that checks each odd number in turn and halts if it finds one that's perfect. (This Turing machine does not take any input.) If we knew whether that Turing machine halts, then we would know whether the conjecture is true, and vice versa.

However, as another example, what about the twin primes conjecture? It's decidable whether a given number is the first prime in a twin pair, but in this case we can't just halt when we find the first one, because the question is about whether there are an infinite number. It's not clear to me whether it's possible to make a Turing machine that halts if and only if the twin primes conjecture is true.

We can surely make a Turing machine that halts if and only if the twin primes conjecture is provable within Peano arithmetic or some other formal system, but that's a different question, since it might be true but not provable in the particular system we choose.

So my questions are

  • Is it possible to make a Turing machine that halts if and only if the twin primes conjecture is true? (And if so, how?)
  • Is it possible, in general, to make a Turing machine that halts if and only if some given mathematical statement is true? Can this Turing machine be constructed algorithmically from the formal statement?
  • If it's not possible in general, is there some way to classify mathematical statements into whether they're equivalent to the halting of a single Turing machine, or a turing machine with an oracle, etc.? If so, is this classification decidable for a given statement?
  • $\begingroup$ What does "true" mean? What kind of models are we evaluating this truth relative to? You'll have to define that first I think. $\endgroup$
    – Jake
    Dec 4 '16 at 8:09
  • $\begingroup$ I think all such Turing machines can only test provability. Even if you aren't explicitly iterating over true statements in PE, you're still looking for a proof in another form. The difference is that odd perfect number existence obviously cannot be both true and unprovable, while twin primes might. $\endgroup$ Dec 4 '16 at 8:42
  • $\begingroup$ Any conjecture about uncountable sets can't be expressed using Turing machines. $\endgroup$
    – Raphael
    Dec 4 '16 at 10:59

Your question is answered by the arithmetical hierarchy. The existence of an odd perfect number is a $\Sigma_1$ statement, and so you can test it using a $\Sigma_1$ machine, which halts iff the statement is true. The twin prime conjecture is a $\Pi_2$ statement, and so you can construct a TM with access to the halting oracle which halts iff the statement is false.

In a strict logical sense, you can always make a Turing machine that halts iff statement $\phi$ holds:

  1. If $\phi$ holds, then take a machine which halts.
  2. If $\phi$ doesn't hold, then take a machine which doesn't halt.

To see that this construction is valid, consider the logical form of your statement:

$$ \forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}. $$ You can clear this confusion up by asking a slightly different questions:

What is a set of statements $\Phi$ such that there exists a Turing machine which halts on $\phi \in \Phi$ iff $\phi$ is valid?

Above I have indicated that $\Sigma_1$ statements form such a set.

  • $\begingroup$ Thank you, I think the arithmetical hierarchy is exactly what I was asking for. I think what I actually intended to ask was "is there a total computable function from (some subset of) mathematical statements to Turing machines that take no input, such that the machine corresponding to a given statement halts iff the statement is true?" But of course that's equivalent to the version you proposed. $\endgroup$
    – Nathaniel
    Dec 4 '16 at 9:38

Let $f(1)=2$, $f(2)=4$, and let $f(n+1)=f(n)!$ for every integer $n \geq 2$. For a positive integer $n$, let $\Theta_n$ denote the statement: if a system

$$S \subseteq \{x_i! = x_k: i,k \in \{1,\ldots,n\}\} \cup \{x_i \cdot x_j=x_k: i,j,k \in \{1,\ldots,n\}\}$$

has only finitely many solutions in integers $x_1,\ldots,x_n$ greater than $1$, then each such solution $(x_1,\ldots,x_n)$ satisfies $\min(x_1,\ldots,x_n) \leq f(n)$. We conjecture that the statements $\Theta_1,\ldots,\Theta_{16}$ are true.

The statement $\Theta_{16}$ proves the implication: if there exists a twin prime greater than $f(16)+3$, then there are infinitely many twin primes, please see this paper by A. Tyszka (On sets $W \subseteq \mathbb{N}$ such that the infinity of $W$ is equivalent to the existence in $W$ of an element that is greater than a threshold number computed with using the definition of $W$)

That is, assuming the statement $\Theta_{16}$, a single query to $0'$ decides the twin prime problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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