32
$\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?

$\endgroup$
5
  • 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$ 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$ 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$ 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
37
$\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).

$\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$ 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$ Feb 12 '14 at 20:56
  • 1
    $\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 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 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$ Jan 15 at 20:23
32
$\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.

$\endgroup$
5
  • $\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$ 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
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.

$\endgroup$
2
  • 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$ 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$ Feb 11 '14 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.

$\endgroup$
6
  • 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$ 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$ 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$ 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.