43
$\begingroup$

I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest one where nobody has a proof whether it halts or not?

Improve this question
$\endgroup$
5
  • 13
    $\begingroup$ The answer depends on the specifics of the machine model (number of symbols, etc.). According to Wikipedia article on Busy Beaver there is 2-symbol 5-sate machine that is not known whether it halts or not. $\endgroup$
    – Kaveh
    Feb 11, 2014 at 7:32
  • 2
    $\begingroup$ Note that Aaron's question is not about the decidability of a given language, but really the existence of a proof that a specific Turing machine halts. For any Turing machine, "its" halting problem (whether this very machine halts on the empty input) is "decidable": it is either Yes or No, and both languages {Yes} and {No} are decidable. This is very different from whether one has a proof that the machine stops or not. Aaron, if you do mean "what is the smallest $M$ such that the language $\{w \mid M$ stops on $w\}$ is undecidable," can you please edit your question? $\endgroup$
    – Michaël Cadilhac
    Feb 11, 2014 at 23:02
  • 1
    $\begingroup$ @MichaëlCadilhac The halting problem is usually interpreted as, "Given a machine $M$ and an input $w$, does $M$ halt for input $w$?" not "Given a machine $M$, does $M$ halt for all inputs?" $\endgroup$
    – David Richerby
    Feb 12, 2014 at 10:48
  • $\begingroup$ @DavidRicherby: To me, the halting problem is the language of machine (codes) that halt on the empty input. If it is not the intended meaning here, I think it should be specified to dissipate possible (ok, my) confusion. $\endgroup$
    – Michaël Cadilhac
    Feb 12, 2014 at 11:07
  • $\begingroup$ multiple ways of studying the problem are valid & interrelated & there is indeed a subtlety in distinguishing them which the questioner did not. $\endgroup$
    – vzn
    Feb 12, 2014 at 16:18

5 Answers 5

Reset to default
46
$\begingroup$

The largest Turing machines for which the halting problem is decidable are:

$TM(2,3), TM(2,2), TM(3,2)$ (where $TM(k,l)$ is the set of Turing machines with $k$ states and $l$ symbols).

The decidability of $TM(2,4)$ and $TM(3,3)$ is on the boundary and it is difficult to settle because it depends on the Collatz conjecture which is an open problem.

See also my answer on cstheory about Collatz-like Turing machines and "Small Turing machines and generalized busy beaver competition" by P. Michel (2004) (in which it is conjectured that $TM(4,2)$ is also decidable).

Kaveh's comment and Mohammad's answer are correct, so for a formal definition of the standard/non-standard Turing machines used in this kind of results see Turlough Neary and Damien Woods works on small universal Turing machines, e.g. The complexity of small universal Turing machines: a survey (Rule 110 TMs are weakly universal).

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Isn't the halting problem for any given finite set of Turing machines always decidable? Since there are only finitely many machines in $TM(4, 2)$, it must be possible to construct a lookup table which correctly says which machines halt and which ones don't, and so there must be a Turing machine which uses this lookup table to correctly answer the question. $\endgroup$
    – Tanner Swett
    Feb 12, 2014 at 20:25
  • 3
    $\begingroup$ @TannerSwett: here we consider the halting set $\{\langle M,x \rangle \mid M \text{ halts on } x\}$ or, in other words, for which Turing machines $HALT_M = \{ x \mid M \text{ halts on } x\}$ is decidable (see Michel's paper). $\endgroup$
    – Marzio De Biasi
    Feb 12, 2014 at 20:56
  • 2
    $\begingroup$ I feel unsatisfied by this answer. Certainly there are specific, trivial Turing machines, of any (k, l), which are decidable. I think the original question wanted a specific example of a Turing machine for which termination has been proven to be undecidable. $\endgroup$
    – Brent
    Jan 15, 2021 at 19:12
  • 1
    $\begingroup$ I dug a little more and found a comment to another question that pegged the size of one example at 1919 states. cstheory.stackexchange.com/questions/29244/… $\endgroup$
    – Brent
    Jan 15, 2021 at 19:19
  • 1
    $\begingroup$ @Brent: you're right the original question is about a specific Turing machine. The answer below by Denis is in the same direction. That TM, probably doesn't halt (unless you question the foundations of mathematics :-) but you cannot prove it. If the OP is interested in an actual TM for which there is no proof whether it halts or not (but not necessarily unprovable), perhaps a smaller machine could be built that halts if and only if a simple unknown conjecture is true or false (e.g the Collatz conjecture) ... it could be a nice idea for a post on my blog ;-) $\endgroup$
    – Marzio De Biasi
    Jan 15, 2021 at 20:23
34
$\begingroup$

I would like to add that there are some Turing Machines for which the Halting problem is independent of ZFC.

For instance take a Turing machine which looks for a proof of contradiction in ZFC. Then if ZFC is consistent, it won't halt, but you cannot prove it in ZFC (because of Gödel's second incompleteness theorem).

So it is not only a matter of not having found a proof yet, sometimes proofs don't even exist.

Improve this answer
$\endgroup$
5
  • $\begingroup$ ZFC? What does ZFC mean? I just can't figure it out from the context. $\endgroup$
    – Acapulco
    Feb 12, 2014 at 3:19
  • 7
    $\begingroup$ @Acapulco lmgtfy.com/?q=zfc&l=1 $\endgroup$
    – Sasho Nikolov
    Feb 12, 2014 at 3:27
  • 2
    $\begingroup$ Lol! ok. I got lmgtfy'ed. Touchè. Didn't think it would be initials that would immediately and uniquely relate to this topic. In any case I don't think it hurts to add a courtesy "ZFC (Zermelo–Fraenkel set theory)" clarification the first time its mentioned, also to avoid ambiguity in case there is? :) $\endgroup$
    – Acapulco
    Feb 12, 2014 at 5:05
  • 16
    $\begingroup$ @Acapulco, please see tour and help center. Any theoretical computer scientist would know what ZFC stands for so there is not really a need for a clarification. $\endgroup$
    – Kaveh
    Feb 12, 2014 at 5:22
  • 1
    $\begingroup$ In particular, note the recently discovered $2$-symbol machines with ZFC-independent halting problem, discussed here (7918 states), here and here (1919 states). The number of states is almost certain to be decreased further. $\endgroup$
    – r.e.s.
    Jun 29, 2016 at 22:10
14
$\begingroup$

Overview of Turing Machine decidability starting on the a blank tape (Busy Beaver style)

For the blank tape input only (as opposed to the more traditional Busy Beaver statement which asks decidability for every single possible input configuration):

The best overview of "lists of unproven machines" by various sources currently is this page from the "The Busy Beaver Challenge" (bbchallenge): https://bbchallenge.org/story#skelets-43-undecided-machines As of 2023 The bbchallenge is the most visible ongoing project to calculate BB(5), the Busy Beaver "shift" function of 5 AKA s(5) in some older literature, which counts how many steps a Turing machine runs for on a tape full of 0's before halting. Non-halting ones are excluded. So calculating BB(5) implies solving the halting problem for every single Turing machine with 5 states.

As highlighted by the bbchallenge, it also depends a lot on what you consider "verified", ranging from manual proof, to unverified programmatic checks, to formal proofs.

One of the major features of the bbchallenge are deciders. Deciders are programs that attempt to decide if a large number of Turing machines halt or not. But note that all deciders seem to be parameterized with "search depth like parameters", so it is not easy to be sure if more would be solved with larger parameters and more computational time. And in is a notable example of that some rare cases, time can get ridiculously large, requiring more advanced/specialized techniques in practice for proving specific machines, Skelet #1 below.

Back in 2003, Skelet produced a list of only 43 machines that he was not able to decide with a large formally unverified Pascal decider program, plus a few manual proofs. That list has generally considered to contain some of the "most likely unproven/hardest to prove ones".

Then more recently and independently, bbproject contributors also managed to decide all machines except 34 with deciders, but with much better review/verification procedures: https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3

So it is interesting to see that both approaches found about ~30-40 machines that were not "easily" automatically provable and required manual proofs. This is of course where the gold lies, as these non-automatable machines are the ones most likely to represent "complex theorems worthy of mathematician's brain time", see also: ""Real" open conjectures reduced to Turing Machines below."

If these are worth a mathematician's brain time or not, is another story. Some of the machines appear to require computational + brain approaches, e.g. Skelet #1, which while epic, might not hold that much insight into Life, the Universe and Everything. Some however will hold deeper meaning of course.

Skelet's 43 holdouts

Skelet's holdouts were initially published at: https://skelet.ludost.net/bb/nreg.html

Dan Briggs manage to prove some of Skelet's 43 never halt circa 2021: https://github.com/danbriggs/Turing/blob/master/paper/HNRs.pdf

The BB challenge also solved some with their own deciders: https://bbchallenge.org/skelet

The "individual machines" section of the bbchalenge Discuss is likely best way to find an publish state of the art, it is basically the "Journal of BB(5) Research" if you will! https://discuss.bbchallenge.org/c/individual-machines/7 Some early movements occasionally also happen on Discord, go figure: https://discord.com/channels/960643023006490684/1026577255754903572 Notably, #1 and #34 also fell:

#1 was particularly epic, a shifted cycle with cycle of about ~8 billion steps.

It seems likely that the bbproject managed to resolve all of the holdouts as mentioned at: http://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/4?u=cirosantilli and surrounding posts.

BB(6)

It currently looks like will likely never know BB(6). Or it would require a CERN-like mega-project, or AGI. Therefore if you are looking for some small Turing machines to prove, going through BB(6) one a time, trying every known decider on it, and failing that going for manual proof seems like a good approach!

A good argument we think BB(6) might never be known is that $BB(6) \ge 10 \uparrow \uparrow 15$, overview: https://www.sligocki.com/2022/06/21/bb-6-2-t15.html (Pavel Kropitz, 2022) i.e. Pavel came up with a machine he managed to prove halts after that time/many 1's written.

Therefore, if there are any BB(6) holdouts that take nearly as much computation time to decide, we might really never solve them. Compare that e.g. to BB(5), where the current champion halts after ~47 million steps, but where Skelet #1 has a cycle of the order of billions.

"Real" open conjectures reduced to Turing Machines

Some mathematical problems can be reduced to deciding the halting problem of a specific Turing machine. The best example of this is perhaps Goldbach conjecture, where it is obvious how you can make a Turing machine that just walks every positive number one by one, tries every possible pair of smaller numbers that sum up to it, and checks if they are prime. Then it halts if no valid pair is found for a number, or continues to infinity otherwise.

Such Turing machines serve therefore as examples of "known hard to prove problems". Going down that route also allows to show that certain Turing machines are undecidable in a certain proof system, e.g. ZF. This is done by modelling the logic system itself with a Turing machine.

https://bbchallenge.org/story#what-is-known-about-bb is the best list available as of 2023:

  • BB(15) is at least as hard as Erdős' conjecture on powers of 2: "for n > 8, there is at least one digit 2 in the base-3 representation of 2n". [Stérin and Woods, 2021] (smallest TM for an open mathematical problem)
  • BB(27) is at least as hard as Goldbach conjecture: “for n > 2, every even integer is the sum of two primes” unverified construction [Aaronson, 2020] (smallest TM for a famous open mathematical problem)
  • BB(744) is at least as hard as Riemann Hypothesis [Matiyasevich and O’Rear and Aaronson, unpublished] (smallest TM for a mega-famous open mathematical problem)
  • BB(748) is independent of [ZF] (https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory) [O’Rear, unpublished] (smallest value we currently know we can never know for sure)
  • BB(5,372) is at least as hard as Riemann Hypothesis [Yedidia and Aaronson, 2016]
  • BB(7, 910) is independent of ZFC [Yedidia and Aaronson, 2016]

Most/all of these proofs involved compiling down simple programming languages to Turing machines programmatically, see also: https://cs.stackexchange.com/questions/50815/compiler-that-compiles-to-a-turing-machine

It is worth noting however that not all mathematical problems can be directly reduced to a "simpler halting problem" (that does not directly involve proving another Halting problem). E.g. this is not the case for Collatz conjecture, as a counterexample would go off to infinity and you wouldn't be able to tell: https://mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur Goldbach is fundamentally different from Collatz in that you can just try every smaller number and be done for each integer.

Some real cool but mostly philosophical aspects of such reductions are:

  • they allow us to estimate how hard a conjecture might be to prove: the more states in the Turing machine the harder
  • they might allow for automated proofs to be carried out via deciders. In this way, they can be seen as a sort of "normal form" for large chunks of mathematics, much like 3SAT is a kind of normal form for NP.

Blank tapes vs arbitrary tapes

As highlighted by Marzio, the question of "decide every N-state Turing machine for every possible input" has already reached the wall basically:

  • 3 states: decidable
  • 4 states: unknown believed to be decidable
  • 5 states: a Collatz-like problem
  • 10 states: Collatz itself
  • 15 states: Turing machine simulation (Universal Turing machine)

These numbers were extracted from the following answers which give their references:

Also note that the second image is already outdated as we have a 15-state universal machine as per first image, just it simulates slower than the previously known 19-state one.

While those could potentially be reduced slightly if an even smaller machine is found, we are already basically bricked at 5 states in terms of what we can prove.

This is what makes the blank-tape only problem more compelling to me. It is fundamentally simpler, as we don't have to consider infinitely many inputs for each machine: one machine, one input, can I decide it.

As a result, we get to zoom in much more, and the boundary between decidable, hard maths problem and undecidable has humongous gaps that beg to be improved. Notably, given that we got away with only 30-40 manual proofs for BB(5), it is not clear if BB(6) will present fundamentally hard maths problems or not. What about BB(7)? And so on. Because now we are at BB(15), which is a monumental gap away from BB(5).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Note: This is discussing the Halting problem when started on a blank tape as specified by the Busy Beaver problem. If you consider the Halting problem for TMs across all tapes, then all Universal TM are known to be undecidable as other answers have noted. $\endgroup$
    – sligocki
    Sep 21, 2023 at 14:34
  • 1
    $\begingroup$ Another reason that BB(6) or BB(7) may require serious Math advances to be solved is sligocki.com/2022/04/03/mother-of-giants.html . I've only found these for a (related) Beeping Busy Beaver. But they will happen in normal BB sooner or later. Specifically, these are TMs where we can specify their behavior exactly and simply as a Collatz-like process, but Math is not advanced enough to let us decide if they actually halt or when. $\endgroup$
    – sligocki
    Sep 21, 2023 at 14:36
  • $\begingroup$ @sligocki thanks, I put more emphasis on the blank tape only assumption of the answer. About BB(6) and BB(7) containing fundamentally difficult problems, I'm not too sure about that yet. Finding that out is actually the most exciting aspect of investigating BB(6) in my opinion. For now I feel like BBB might be incredibly harder than BB + BB(5) does not seem "so bad" considering we got away with only 30-40 manual proofs without deciders. But for sure, our current hard problem bound of BB(15) is too high. Also, thanks for your awesome work on proof and exposition of BB-related issues! $\endgroup$
    – Ciro Santilli OurBigBook.com
    Sep 21, 2023 at 18:34
  • 1
    $\begingroup$ Yeah, I certainly think that BBB(5) is much harder than BB(6). But note that this "Mother of Giants" is nowhere near the complexity possible in BBB(5). It's "quasihalting" condition is extremely simple and decidable. So I think there's a really good chance that such a machine exists in BB(6) and I feel very confident that it's in BB(7). Glad you enjoy my blog! It brings me a lot of pleasure to see people referencing it across the web :) $\endgroup$
    – sligocki
    Sep 22, 2023 at 19:15
4
$\begingroup$

No one has a proof whether Universal Turing machine halts or not. In fact, such proof is impossible as a result of the undecidability of the the Halting problem . The smallest is a 2-state 3-symbol universal Turing machine which was found by Alex Smith for which he won a prize of $25,000.

Improve this answer
$\endgroup$
2
  • 8
    $\begingroup$ Note, however, that, according to the Wikipedia page cited, the proof of universality is disputed. Also, this is not the standard model of Turing machines: the allegedly universal machine has no halt state so cannot simulate any machine that halts, at least in the standard sense of what a universal Turing machine does. $\endgroup$
    – David Richerby
    Feb 11, 2014 at 8:54
  • 5
    $\begingroup$ @DavidRicherby: I think that the weakly-universality of the rule 110 is quite accepted: it requires two different words repeated on the left and right of the input, and the halting condition is the generation of a special glider (generated if and only if the simulated machine halts). See Matthew Cook's "Universality in elementary cellular automata". $\endgroup$
    – Marzio De Biasi
    Feb 11, 2014 at 9:12
-4
$\begingroup$

an inexactly phrased but reasonable general question that can be studied in several particular technical ways. there are many "small" machines measured by states/symbols where halting is unknown but no "smallest" machine is possible unless one comes up with some justifiable/quantifiable metric of the complexity of a TM that takes into account both states and symbols (apparently nobody has proposed one so far).

actually research into this problem related to Busy Beavers suggests that there are are many such "small" machines lying on a hyperbolic curve where $x \times y$, $x$ states and $y$ symbols, is small. in fact it appears to be a general phase transition/boundary between decidable and undecidable problems.

this new paper Problems in number theory from busy beaver competition 2013 by Michel a leading authority exhibits many such cases for low $x,y$ and shows the connection to general number theoretic sequences similar to the Collatz conjecture.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ It's not necessary to establish a metric taking into account symbols and states. Once there are two symbols on the tape, it's clear that the halting problem is undecidable for almost all numbers of states -- as I recall, it's possible to write a universal TM with only five states. If we knew the exact boundary of decidability, I'm sure it would be easy to describe that boundary in terms of (#states,#symbols) pairs. $\endgroup$
    – David Richerby
    Feb 12, 2014 at 10:58
  • $\begingroup$ the busy beaver research indeed involves finding proofs for whether TMs halt for initial setups with small # of states, symbols; there are resolvable cases. if one wants the "smallest" anything one must create a precise metric that measures "small". the pt above is that a metric that only involves states or symbols alone can be regarded as misleading as far as representing the known boundary which involves both (and machines not known to be universal). the undecidability boundary in this research is not "easy" to specify in terms of anything at all, that is its fundamental nature.... $\endgroup$
    – vzn
    Feb 12, 2014 at 16:05
  • 1
    $\begingroup$ Nobody proposed a metric based on only #states or only #symbols. And the (#states,#symbols) boundary is trivial to describe. For one state, it is decidable. For $2\leq i\leq 4$ states, it is decidable for alphabets of size at most $k_i$, where $k_2$, $k_3$, $k_4$ are unknown constants. For five states, it is undecidable (except, maybe, for alphabets of size 1). Describing the boundary is trivial; the only non-trivial part is figuring out the values of $k_2$, $k_3$, $k_4$. $\endgroup$
    – David Richerby
    Feb 12, 2014 at 16:54
  • $\begingroup$ nobody proposed any metric at all so far. no important boundary in this area is "trivial to describe" & one would expect that scenario would be impossible via Rices thm. this seems to show a lack of familiarity with the research & the cited ref which is interested in resolvability of inputs for machines that are smaller than those known to be universal (and conjectured to not be universal). your comments seem to focus on universal vs nonuniversal machine boundaries which is not the same as the busy beaver decidability boundaries being explored eg in the cited refs (both above & Marzio's). $\endgroup$
    – vzn
    Feb 12, 2014 at 16:57
  • $\begingroup$ Doesn't the fact that I just described it in a Stack Exchange comment imply that it's trivial to describe? The point about universality is that it gives upper bounds for the boundary: if you can implement a universal machine with $x$ states and $y$ symbols, the halting problem for $x$-state, $y$-symbol TMs is clearly undecidable. $\endgroup$
    – David Richerby
    Feb 12, 2014 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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