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?

  • 10
    $\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 '14 at 7:32
  • 1
    $\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 '14 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 '14 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 '14 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 '14 at 16:18

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

  • 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 '14 at 20:25
  • 2
    $\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 '14 at 20:56

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.

  • $\begingroup$ ZFC? What does ZFC mean? I just can't figure it out from the context. $\endgroup$ – Acapulco Feb 12 '14 at 3:19
  • 7
    $\begingroup$ @Acapulco lmgtfy.com/?q=zfc&l=1 $\endgroup$ – Sasho Nikolov Feb 12 '14 at 3:27
  • $\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 '14 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 '14 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 '16 at 22:10

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.

  • 4
    $\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 '14 at 8:54
  • 2
    $\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 '14 at 9:12

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.

  • 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 '14 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 '14 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 '14 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 '14 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 '14 at 17:22

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.