1
$\begingroup$

It is known that some famous Number Theoretic problems are equivalent to halting of specific Turing machines:

  1. Goldbach conjecture holds iff a 47 state TM halts

  2. Lagarias' formulation of Riemann hypothesis makes it plausible to exhibit a Turing machine that halts iff Riemann hypothesis is true, see The Riemann Hypothesis in computer science

A relatively small Turing machine was exhibited whose behavior is independent of ZFC.

Q: Is it possible for each statement in math to exhibit a minimal Turing Machine that halts iff the statement is true? (minimal = minimal number of states).

Remark: Being "minimal" here should be taken relative to an axiom system( e.g. there is a version in PA, in second order arithmetics etc.)

Related posts:

Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?

Status of Grand Conjecture

Is all ordinary mathematics contained in high school mathematics?

Improve this question
$\endgroup$
3
  • $\begingroup$ Perhaps related is Andrej Bovykin's research: researchgate.net/publication/…. He was developing an "atlas" that would include mathematical statements formulated as statements about certain polynomials. Some papers om the atlas may be found on the internet. $\endgroup$
    – Sam Sanders
    Commented Aug 5 at 7:55
  • $\begingroup$ Do you mean "halts iff RH is true" or "halts iff RH is false"? $\endgroup$
    – Lucenaposition
    Commented Aug 6 at 1:53
  • $\begingroup$ "Minimal" is problematic. Firstly, the question of whether two TMs compute the same function is uncomputable. Secondly, you point out that the busy beaver function has a limit $N$ such that $BB(N)$ is independent of ZFC. This means that if you have a TM larger than $N$ which computes a function, you can't test all smaller TMs to see whether they compute the same function. FWIW I wouldn't be surprised if $N < 100$. I have a 64-state TM whose termination is currently only known, AFAIK, if we assume a rank-into-rank cardinal. $\endgroup$
    – Peter Taylor
    Commented Aug 12 at 16:22

1 Answer 1

Reset to default
5
$\begingroup$

For any statement S, there is some Turing machine T such that T halts iff S is true. If S is true, pick for T any Turing machine which halts. If S is false, pick for T any Turing machine which does not halt. But this is rather trivial.

What you presumably want is a procedure which associates to any statement S a Turing machine T such that it is provable [in some particular proof system of interest to you] that "T halts iff S is true". This can be done for S if and only if S is provably equivalent to a so-called $\Sigma_1$ statement (roughly speaking, a statement of the form "There exist natural numbers (or whatever such-encodable objects) x, y, z, … such that blah blah", where "blah blah" contains no further unbounded quantifications).

But in general, there are many mathematical statements which have unbounded universal quantifiers, which are not provably equivalent to any $\Sigma_1$ statement. Indeed, in general, the negation of a $\Sigma_1$ statement isn't even $\Sigma_1$.

If it really were the case that for every mathematical statement S, there were some Turing machine T such that provably "T halts iff S is true", then there would be no such phenomenon as undecidability/incompleteness (in the Gödelian sense). For we could then find a proof of either S or its negation by constructing the two corresponding Turing machines and running them in parallel until the one or the other halted.

Improve this answer
$\endgroup$
8
  • 5
    $\begingroup$ @QiaochuYuan That is asking for too much, since if the open question is provably true, then it is provably equivalent to 1=1, and if it is false, then it is provably equivalent to 0=1, both of which are $\Sigma_1$. One might try to ask for an independent statement that is provably not $\Sigma_1$. But here again, this will never be possible, since if it is independent, then it is consistent that it holds, and so it is consistent that it is equivalent to 1=1. So, what you should actually want is: a statement for which we cannot prove it is equivalent to a $\Sigma_1$ statement. $\endgroup$
    – Joel David Hamkins
    Commented Aug 4 at 21:10
  • 1
    $\begingroup$ And for this, almost all the usual independent statements work. e.g. Con(PA), Goodstein, etc. cannot be provably equivalent to $\Sigma_1$, since any true $\Sigma_1$ statement is not independent. $\endgroup$
    – Joel David Hamkins
    Commented Aug 4 at 21:11
  • 3
    $\begingroup$ The Goldbach Conjecture is literally $\Pi_1$: $$\forall n\,\exists a, b \lt 2n(n \gt 2 \to \mathsf{prime}(a) \land \mathsf{prime}(b) \land a + b = 2n)$$ where $\mathsf{prime}(x)$ is a $\Delta_0$ formula that says $x$ is prime. There is no known $\Sigma_1$ formulation, as far as I know. $\endgroup$
    – François G. Dorais
    Commented Aug 4 at 22:25
  • 1
    $\begingroup$ Then again, the 4-Color Theorem is also a $\Pi_1$ statement, which was proven equivalent to a $\Sigma_1$ statement and then reduced to a large finite computation that resolved the issue. The same could be true of Goldbach. $\endgroup$
    – François G. Dorais
    Commented Aug 4 at 22:38
  • 1
    $\begingroup$ P $=$ NP is naturally $\Sigma_2$, while P $\neq$ NP is naturally $\Pi_2$. $\endgroup$
    – Sridhar Ramesh
    Commented Aug 5 at 3:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .