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

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

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

CC BY-SA 3.0
2014-02-12T03:19:31.780Z
ZFC? What does ZFC mean? I just can't figure it out from the context.
Acapulco
CC BY-SA 3.0
2014-02-12T03:27:06.767Z
@Acapulco http://lmgtfy.com/?q=zfc&l=1
Sasho Nikolov
CC BY-SA 3.0
2014-02-12T05:05:25.793Z
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? :)
Acapulco
CC BY-SA 3.0
2014-02-12T05:22:44.913Z
@Acapulco, please see [about] and [help/on-topic]. Any theoretical computer scientist would know what ZFC stands for so there is not really a need for a clarification.
Kaveh
CC BY-SA 3.0
2016-06-29T22:10:41.633Z
In particular, note the recently discovered $2$-symbol machines with ZFC-independent halting problem, discussed [here](http://www.scottaaronson.com/blog/?p=2725) (7918 states), [here](http://www.scottaaronson.com/blog/?p=2741) and [here](https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm) (1919 states). The number of states is almost certain to be decreased further.
r.e.s.
CC BY-SA 4.0
2024-07-12T10:06:47.297Z
"Sometimes proofs don't even exist"..  Really?  Aren't there are other valid kinds of proofs, other than those in ZFC?  Didn't someone prove that mathematics is not axiomatizable?  :-)
Neal Young
CC BY-SA 3.0
2014-02-11T13:00:57.257Z
2014-02-11T17:39:33.880Z
2014-02-11T17:39:33.880Z
Denis
<p><strong>Overview of Turing Machine decidability starting on the a blank tape (Busy Beaver style)</strong></p>
<p>For the blank tape input only (as opposed to the more traditional Busy Beaver statement which asks decidability for every single possible input configuration):</p>
<ul>
<li><p>4-state machines: <a href="https://www.jstor.org/stable/2007539" rel="nofollow noreferrer">all decided in 1983</a></p>
</li>
<li><p>5-state machines: in 2024 a Coq proof was published deciding all 5-state machines:</p>
<ul>
<li><a href="https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/" rel="nofollow noreferrer">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</a></li>
<li><a href="https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237" rel="nofollow noreferrer">https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237</a></li>
</ul>
<p>A good human readable summary of machine classification towards the end of the process can be found at: <a href="https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3" rel="nofollow noreferrer">https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3</a></p>
</li>
<li><p>6-state machines: might quite possibly remain forever open however. <a href="https://wiki.bbchallenge.org/wiki/Antihydra" rel="nofollow noreferrer">A difficult looking problem called Antihydra has been spotted for it</a> in June 2024. See also the BB(6) section below. I think antihydra is equivalent to the following program in arbitrary-precision integer arithmetic pseudocode:</p>
<pre><code>int a = 8
int b = 0
while (true) {
  if (a % 2 == 0) {
    a = (a/2)*3
    b += 2
  } else {
    if (b == 0)
      break
    a = ((a - 1)/2)*3 + 1
    b -= 1
  }
}
</code></pre>
</li>
</ul>
<p>The best overview of &quot;unproven small machines which are likely hard&quot; is: <a href="https://wiki.bbchallenge.org/wiki/Cryptids" rel="nofollow noreferrer">https://wiki.bbchallenge.org/wiki/Cryptids</a> maintained by the &quot;The Busy Beaver Challenge&quot; (bbchallenge). <a href="https://bbchallenge.org/story#skelets-43-undecided-machines" rel="nofollow noreferrer">https://bbchallenge.org/story#skelets-43-undecided-machines</a> is another good similar summary by the same project.</p>
<p>As of 2023 The bbchallenge was the most visible ongoing project to calculate BB(5), the <a href="https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_function_S" rel="nofollow noreferrer">Busy Beaver &quot;shift&quot; function</a> of 5 AKA <code>s(5)</code> 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.</p>
<p>As highlighted by the bbchallenge, it also depends a lot on what you consider &quot;verified&quot;, ranging from manual proof, to unverified programmatic checks, to formal proofs.</p>
<p>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 &quot;search depth like parameters&quot;, 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.</p>
<p>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 &quot;most likely unproven/hardest to prove ones&quot;.</p>
<p>Then more recently and independently, bbproject contributors also managed to decide all machines except 34 with deciders, but with much better review/verification procedures: <a href="https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3" rel="nofollow noreferrer">https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3</a></p>
<p>So it is interesting to see that both approaches found about ~30-40 machines that were not &quot;easily&quot; 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 &quot;complex theorems worthy of mathematician's brain time&quot;, see also: &quot;&quot;Real&quot; open conjectures reduced to Turing Machines below.&quot;</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Life,_the_Universe_and_Everything" rel="nofollow noreferrer">Life, the Universe and Everything</a>. Some however will hold deeper meaning of course.</p>
<p><strong>Skelet's 43 holdouts</strong></p>
<p>Skelet's holdouts were initially published at: <a href="https://skelet.ludost.net/bb/nreg.html" rel="nofollow noreferrer">https://skelet.ludost.net/bb/nreg.html</a></p>
<p>Dan Briggs manage to prove some of Skelet's 43 never halt circa 2021: <a href="https://github.com/danbriggs/Turing/blob/master/paper/HNRs.pdf" rel="nofollow noreferrer">https://github.com/danbriggs/Turing/blob/master/paper/HNRs.pdf</a></p>
<p>The BB challenge also solved some with their own deciders: <a href="https://bbchallenge.org/skelet" rel="nofollow noreferrer">https://bbchallenge.org/skelet</a></p>
<p>The &quot;individual machines&quot; section of the bbchalenge Discuss is likely best way to find an publish state of the art, it is basically the &quot;Journal of BB(5) Research&quot; if you will! <a href="https://discuss.bbchallenge.org/c/individual-machines/7" rel="nofollow noreferrer">https://discuss.bbchallenge.org/c/individual-machines/7</a> Some  early movements occasionally also happen on Discord, go figure: <a href="https://discord.com/channels/960643023006490684/1026577255754903572" rel="nofollow noreferrer">https://discord.com/channels/960643023006490684/1026577255754903572</a>
Notably, #1 and #34 also fell:</p>
<ul>
<li>#1 <a href="https://www.sligocki.com/2023/03/13/skelet-1-infinite.html" rel="nofollow noreferrer">https://www.sligocki.com/2023/03/13/skelet-1-infinite.html</a> | <a href="https://discuss.bbchallenge.org/t/skelet-1-is-a-translated-cycler-coq-agrees/166" rel="nofollow noreferrer">https://discuss.bbchallenge.org/t/skelet-1-is-a-translated-cycler-coq-agrees/166</a></li>
<li><a href="https://www.sligocki.com/2023/02/02/skelet-34.html" rel="nofollow noreferrer">https://www.sligocki.com/2023/02/02/skelet-34.html</a></li>
</ul>
<p>#1 was particularly epic, a shifted cycle with cycle of about ~8 billion steps.</p>
<p>It seems likely that the bbproject managed to resolve all of the holdouts as mentioned at: <a href="http://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/4?u=cirosantilli" rel="nofollow noreferrer">http://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/4?u=cirosantilli</a> and surrounding posts.</p>
<p><strong>BB(6)</strong></p>
<p>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!</p>
<p>On June 2024,a hard looking &quot;Collataz-like&quot; 6-state halting problem was found. The associated machine was named &quot;Antihydra&quot; and is described at: <a href="https://wiki.bbchallenge.org/wiki/Antihydra" rel="nofollow noreferrer">https://wiki.bbchallenge.org/wiki/Antihydra</a></p>
<p>Another good argument we think BB(6) might never be known is that <span class="math-container">$BB(6) \ge 10 \uparrow \uparrow 15$</span>, overview: <a href="https://www.sligocki.com/2022/06/21/bb-6-2-t15.html" rel="nofollow noreferrer">https://www.sligocki.com/2022/06/21/bb-6-2-t15.html</a> (Pavel Kropitz, 2022) i.e. Pavel came up with a machine he managed to prove halts after that time/many 1's written.</p>
<p>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.</p>
<p>Here's a <a href="https://en.wikipedia.org/w/index.php?title=GNU_Multiple_Precision_Arithmetic_Library" rel="nofollow noreferrer">GMP</a> simulation of the equivalent antihydra problem with some performance diagnostics added:</p>
<p>antihydra.c</p>
<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdint.h&gt;
#include &lt;inttypes.h&gt;
#include &lt;time.h&gt;

#include &lt;gmp.h&gt;

static uint64_t get_milis(void) {
    struct timespec ts;
    timespec_get(&amp;ts, TIME_UTC);
    return (uint64_t)(ts.tv_sec * 1000 + ts.tv_nsec/1000000);
}

int main(int argc, char **argv) {
    char *as, *bs;
    mpz_t a, aq, ar, b;
    uint64_t i, time, newtime;

    /* CLI and init. */
    if (argc &gt; 1) {
        as = argv[1];
    } else {
        as = &quot;8&quot;;
    }
    if (argc &gt; 2) {
        bs = argv[2];
    } else {
        bs = &quot;0&quot;;
    }
    mpz_init_set_str(a, as, 10);
    mpz_init_set_str(b, bs, 10);
    mpz_init(aq);
    mpz_init(ar);
    i = 0;
    time = get_milis();

    /* Run. */
    while (1) {
        /* aq = a / 2
         * ar = a % 2 */
        mpz_fdiv_qr_ui(aq, ar, a, 2);
        if (
            /* odd */
            mpz_cmp_ui(ar, 0)
        ) {
            /* b == 0 */
            if (!mpz_cmp_ui(b, 0)) break;
            /* a = aq * 3 + 1 */
            mpz_mul_ui(a, aq, 3);
            mpz_add_ui(a, a, 1);
            /* b -= 1 */
            mpz_sub_ui(b, b, 1);
        } else {
            /* a = aq * 3 */
            mpz_mul_ui(a, aq, 3);
            /* b += 2 */
            mpz_add_ui(b, b, 2);
        }
        i++;
        if (i % 100000 == 0) {
            newtime = get_milis();
            gmp_printf(&quot;%&quot; PRIu64 &quot; ms=%&quot; PRIu64 &quot; log10(a)=%ju log10(b)=%ju\n&quot;,
                       i/100000, newtime - time, mpz_sizeinbase(a, 10), mpz_sizeinbase(b, 10));
            time = newtime;
        }
    }

    /* Cleanup if we ever reach it. */
    mpz_clear(a);
    mpz_clear(aq);
    mpz_clear(ar);
    mpz_clear(b);
    return 0;
}
</code></pre>
<p>Compile and run:</p>
<pre><code>gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out
</code></pre>
<p>Tested on Tested on GMP 6.3.0, Ubuntu 24.04.</p>
<p><strong>&quot;Real&quot; open conjectures reduced to Turing Machines</strong></p>
<p>Some mathematical problems can be reduced to deciding the halting problem of a specific Turing machine. The best example of this is perhaps <a href="https://en.wikipedia.org/wiki/Goldbach%27s_conjecture" rel="nofollow noreferrer">Goldbach conjecture</a>, 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.</p>
<p>Such Turing machines serve therefore as examples of &quot;known hard to prove problems&quot;. Going down that route also allows to show that certain Turing machines are undecidable in a certain proof system, e.g. <a href="https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory" rel="nofollow noreferrer">ZF</a>. This is done by modelling the logic system itself with a Turing machine.</p>
<p><a href="https://bbchallenge.org/story#what-is-known-about-bb" rel="nofollow noreferrer">https://bbchallenge.org/story#what-is-known-about-bb</a> is the best list available as of 2023:</p>
<ul>
<li>BB(15) is at least as hard as Erdős' conjecture on powers of 2: &quot;<a href="https://mathoverflow.net/questions/33942/do-the-base-3-digits-of-2n-avoid-the-digit-2-infinitely-often-what-is-the">for n &gt; 8, there is at least one digit 2 in the base-3 representation of 2n</a>&quot;. [Stérin and Woods, 2021] (smallest TM for an open mathematical problem)</li>
<li>BB(27) is at least as hard as <a href="https://en.wikipedia.org/wiki/Goldbach%27s_conjecture" rel="nofollow noreferrer">Goldbach conjecture</a>: “for n &gt; 2, every even integer is the sum of two primes” unverified construction [Aaronson, 2020] (smallest TM for a famous open mathematical problem)</li>
<li>BB(744) is at least as hard as <a href="https://en.wikipedia.org/wiki/Riemann_hypothesis" rel="nofollow noreferrer">Riemann Hypothesis</a> [Matiyasevich and O’Rear and Aaronson, unpublished] (smallest TM for a mega-famous open mathematical problem)</li>
<li>BB(748) is independent of [ZF] (<a href="https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory</a>) [O’Rear, unpublished] (smallest value we currently know we can never know for sure)</li>
<li>BB(5,372) is at least as hard as Riemann Hypothesis [Yedidia and Aaronson, 2016]</li>
<li>BB(7, 910) is independent of ZFC [Yedidia and Aaronson, 2016]</li>
</ul>
<p>Most/all of these proofs involved compiling down simple programming languages to Turing machines programmatically, see also: <a href="https://cs.stackexchange.com/questions/50815/compiler-that-compiles-to-a-turing-machine">https://cs.stackexchange.com/questions/50815/compiler-that-compiles-to-a-turing-machine</a></p>
<p>It is worth noting however that not all mathematical problems can be directly reduced to a &quot;simpler halting problem&quot; (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: <a href="https://mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur">https://mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur</a> Goldbach is fundamentally different from Collatz in that you can just try every smaller number and be done for each integer.</p>
<p>Some real cool but mostly philosophical aspects of such reductions are:</p>
<ul>
<li>they allow us to estimate how hard a conjecture might be to prove: the more states in the Turing machine the harder</li>
<li>they might allow for automated proofs to be carried out via deciders. In this way, they can be seen as a sort of &quot;normal form&quot; for large chunks of mathematics, much like <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Conjunctive_normal_form" rel="nofollow noreferrer">3SAT</a> is a kind of normal form for <a href="https://en.wikipedia.org/wiki/NP-completeness" rel="nofollow noreferrer">NP</a>.</li>
</ul>
<p><strong>Blank tapes vs arbitrary tapes</strong></p>
<p>As <a href="https://cstheory.stackexchange.com/questions/20978/what-is-the-smallest-turing-machine-where-it-is-unknown-if-it-halts-or-not/20980#20980">highlighted by Marzio</a>, the question of &quot;decide every N-state Turing machine for every possible input&quot; has already reached the wall basically:</p>
<ul>
<li>3 states: decidable</li>
<li>4 states: unknown believed to be decidable</li>
<li>5 states: a <a href="https://math.stackexchange.com/questions/4305972/what-exactly-is-a-collatz-like-problem/4773230#4773230">Collatz-like problem</a></li>
<li>10 states: Collatz itself</li>
<li>15 states: Turing machine simulation (Universal Turing machine)</li>
</ul>
<p>These numbers were extracted from the following answers which give their references:</p>
<ul>
<li><a href="https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine/10390#10390">What&#39;s the simplest noncontroversial 2-state universal Turing machine?</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful/11614#11614">What is the &quot;nearest&quot; problem to the Collatz conjecture that has been successfully resolved?</a></li>
</ul>
<img src="https://i.sstatic.net/rHRtV.png" width="700" />
<img src="https://i.sstatic.net/DlnUG.jpg" width="700" />
<p>Also note that the second image is already outdated:</p>
<ul>
<li>as we have a 15-state universal machine as per first image, just it simulates slower than the previously known 19-state one</li>
<li>BB(5, 2) was settled by the Busy Beaver Challenge project, actual Collatz-like is at BB(6, 2)</li>
</ul>
<p>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.</p>
<p>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.</p>
<p>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).</p>

CC BY-SA 4.0
2023-09-21T14:34:06.397Z
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.
sligocki
CC BY-SA 4.0
2023-09-21T14:36:43.553Z
Another reason that BB(6) or BB(7) may require serious Math advances to be solved is https://www.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.
sligocki
CC BY-SA 4.0
2023-09-21T18:34:50.413Z
@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!
Ciro Santilli OurBigBook.com
CC BY-SA 4.0
2023-09-22T19:15:56.320Z
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 :)
sligocki
CC BY-SA 4.0
2024-07-15T14:53:50.177Z
BB(5) has now been computed: https://bbchallenge.org/6137696
Denis
CC BY-SA 4.0
2024-07-15T15:00:24.167Z
@Denis yes, I had already recently updated the answer with this info
Ciro Santilli OurBigBook.com
CC BY-SA 4.0
2023-09-17T21:15:04.780Z
2024-07-11T08:56:19.703Z
2024-07-11T08:56:19.703Z
Ciro Santilli OurBigBook.com
<p>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 <a href="http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine" rel="nofollow noreferrer">smallest is a 2-state 3-symbol universal Turing</a> machine which was found by Alex Smith for which he won a prize of $25,000.</p>

CC BY-SA 3.0
2014-02-11T08:54:10.937Z
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.
David Richerby
CC BY-SA 3.0
2014-02-11T09:12:37.590Z
@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".
Marzio De Biasi
CC BY-SA 3.0
2014-02-11T07:35:01.803Z
2014-02-11T08:02:02.790Z
2014-02-11T08:02:02.790Z
Mohammad Al-Turkistany
<p>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).</p>

<p>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.</p>

<p>this new paper <a href="http://arxiv.org/pdf/1311.1029v1.pdf" rel="nofollow">Problems in number theory from busy beaver competition</a> 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.</p>

CC BY-SA 3.0
2014-02-12T16:05:09.427Z
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....
vzn
CC BY-SA 3.0
2014-02-12T16:54:25.437Z
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$.
David Richerby
CC BY-SA 3.0
2014-02-12T16:57:34.417Z
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).
vzn
CC BY-SA 3.0
2014-02-12T17:22:10.787Z
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.
David Richerby
CC BY-SA 3.0
2014-02-12T10:58:44.007Z
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.
David Richerby
CC BY-SA 3.0
2014-02-12T03:21:50.500Z
2014-02-12T03:21:50.500Z
vzn
<p>The largest Turing machines for which the halting problem is decidable are: </p>

<p>$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).</p>

<p>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.</p>

<p>See also <a href="https://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful">my answer on cstheory about Collatz-like Turing machines</a> and "<a href="http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf" rel="noreferrer">Small Turing machines and generalized busy beaver competition</a>" by P. Michel (2004) (in which it is conjectured that $TM(4,2)$ is also decidable).</p>

<p>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. <a href="http://arxiv.org/abs/1110.2230" rel="noreferrer">The complexity of small universal Turing machines: a survey</a> (Rule 110 TMs are weakly universal).</p>

CC BY-SA 3.0
2014-02-12T20:25:42.387Z
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.
Sophie Swett
CC BY-SA 3.0
2014-02-12T20:56:43.330Z
@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).
Marzio De Biasi
CC BY-SA 4.0
2021-01-15T19:12:23.477Z
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.
Brent
CC BY-SA 4.0
2021-01-15T19:19:06.813Z
I dug a little more and found a comment to another question that pegged the size of one example at 1919 states. https://cstheory.stackexchange.com/questions/29244/simple-example-of-halting-unprovable-turing-machine#comment80398_29251
Brent
CC BY-SA 4.0
2021-01-15T20:23:37.597Z
@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 ;-)
Marzio De Biasi
CC BY-SA 3.0
2014-02-11T08:18:55.870Z
2014-02-12T11:11:25.107Z
2017-04-13T12:32:28.053Z
Marzio De Biasi
<p>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?</p>

CC BY-SA 3.0
2014-02-11T07:32:34.523Z
The answer depends on the specifics of the machine model (number of symbols, etc.). According to Wikipedia article on [Busy Beaver](http://en.wikipedia.org/wiki/Busy_beaver) there is 2-symbol 5-sate machine that is not known whether it halts or not.
Kaveh
CC BY-SA 3.0
2014-02-11T23:02:57.763Z
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?
Michaël Cadilhac
CC BY-SA 3.0
2014-02-12T10:48:02.623Z
@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?"
David Richerby
CC BY-SA 3.0
2014-02-12T11:07:58.263Z
@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.
Michaël Cadilhac
<halting-problem>
What is the smallest Turing machine where it is unknown if it halts or not?
Aaron
# What is the smallest Turing machine where it is unknown if it halts or not?

(Asked by: username_0 on 2014-02-11)

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?

**Tags:** halting-problem
> **Comments:**
> **username_1**: The answer depends on the specifics of the machine model (number of symbols, etc.). According to Wikipedia article on [Busy Beaver](http://en.wikipedia.org/wiki/Busy_beaver) there is 2-symbol 5-sate machine that is not known whether it halts or not.  
> **username_2**: 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?  
> **username_3**: @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?"  
> **username_2**: @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.  

---

## 5 answers

### Answer by username_12 on 2014-02-11. Score: 46 | Accepted answer

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](https://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful) and "[Small Turing machines and generalized busy beaver competition](http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf)" 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](http://arxiv.org/abs/1110.2230) (Rule 110 TMs are weakly universal).

> **Comments:**
> **username_14**: 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.  
> **username_12**: @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).  
> **username_15**: 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.  
> **username_15**: I dug a little more and found a comment to another question that pegged the size of one example at 1919 states. https://cstheory.stackexchange.com/questions/29244/simple-example-of-halting-unprovable-turing-machine#comment80398_29251  
> **username_12**: @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 ;-)  

---

### Answer by username_4 on 2014-02-11. Score: 34

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.

> **Comments:**
> **username_5**: ZFC? What does ZFC mean? I just can't figure it out from the context.  
> **username_6**: @Acapulco http://lmgtfy.com/?q=zfc&l=1  
> **username_5**: 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? :)  
> **username_1**: @Acapulco, please see [about] and [help/on-topic]. Any theoretical computer scientist would know what ZFC stands for so there is not really a need for a clarification.  
> **username_7**: In particular, note the recently discovered $2$-symbol machines with ZFC-independent halting problem, discussed [here](http://www.scottaaronson.com/blog/?p=2725) (7918 states), [here](http://www.scottaaronson.com/blog/?p=2741) and [here](https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm) (1919 states). The number of states is almost certain to be decreased further.  
> **username_8**: "Sometimes proofs don't even exist"..  Really?  Aren't there are other valid kinds of proofs, other than those in ZFC?  Didn't someone prove that mathematics is not axiomatizable?  :-)  

---

### Answer by username_9 on 2023-09-17. Score: 15

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

4-state machines: all decided in 1983

5-state machines: in 2024 a Coq proof was published deciding all 5-state machines:

https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237

A good human readable summary of machine classification towards the end of the process can be found at: https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3

6-state machines: might quite possibly remain forever open however. A difficult looking problem called Antihydra has been spotted for it in June 2024. See also the BB(6) section below. I think antihydra is equivalent to the following program in arbitrary-precision integer arithmetic pseudocode:
int a = 8
int b = 0
while (true) {
  if (a % 2 == 0) {
    a = (a/2)*3
    b += 2
  } else {
    if (b == 0)
      break
    a = ((a - 1)/2)*3 + 1
    b -= 1
  }
}



The best overview of "unproven small machines which are likely hard" is: https://wiki.bbchallenge.org/wiki/Cryptids maintained by the "The Busy Beaver Challenge" (bbchallenge). https://bbchallenge.org/story#skelets-43-undecided-machines is another good similar summary by the same project.
As of 2023 The bbchallenge was 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 https://www.sligocki.com/2023/03/13/skelet-1-infinite.html | https://discuss.bbchallenge.org/t/skelet-1-is-a-translated-cycler-coq-agrees/166
https://www.sligocki.com/2023/02/02/skelet-34.html

#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!
On June 2024,a hard looking "Collataz-like" 6-state halting problem was found. The associated machine was named "Antihydra" and is described at: https://wiki.bbchallenge.org/wiki/Antihydra
Another 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.
Here's a GMP simulation of the equivalent antihydra problem with some performance diagnostics added:
antihydra.c
#include 
#include 
#include 
#include 

#include 

static uint64_t get_milis(void) {
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    return (uint64_t)(ts.tv_sec * 1000 + ts.tv_nsec/1000000);
}

int main(int argc, char **argv) {
    char *as, *bs;
    mpz_t a, aq, ar, b;
    uint64_t i, time, newtime;

    /* CLI and init. */
    if (argc > 1) {
        as = argv[1];
    } else {
        as = "8";
    }
    if (argc > 2) {
        bs = argv[2];
    } else {
        bs = "0";
    }
    mpz_init_set_str(a, as, 10);
    mpz_init_set_str(b, bs, 10);
    mpz_init(aq);
    mpz_init(ar);
    i = 0;
    time = get_milis();

    /* Run. */
    while (1) {
        /* aq = a / 2
         * ar = a % 2 */
        mpz_fdiv_qr_ui(aq, ar, a, 2);
        if (
            /* odd */
            mpz_cmp_ui(ar, 0)
        ) {
            /* b == 0 */
            if (!mpz_cmp_ui(b, 0)) break;
            /* a = aq * 3 + 1 */
            mpz_mul_ui(a, aq, 3);
            mpz_add_ui(a, a, 1);
            /* b -= 1 */
            mpz_sub_ui(b, b, 1);
        } else {
            /* a = aq * 3 */
            mpz_mul_ui(a, aq, 3);
            /* b += 2 */
            mpz_add_ui(b, b, 2);
        }
        i++;
        if (i % 100000 == 0) {
            newtime = get_milis();
            gmp_printf("%" PRIu64 " ms=%" PRIu64 " log10(a)=%ju log10(b)=%ju\n",
                       i/100000, newtime - time, mpz_sizeinbase(a, 10), mpz_sizeinbase(b, 10));
            time = newtime;
        }
    }

    /* Cleanup if we ever reach it. */
    mpz_clear(a);
    mpz_clear(aq);
    mpz_clear(ar);
    mpz_clear(b);
    return 0;
}

Compile and run:
gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out

Tested on Tested on GMP 6.3.0, Ubuntu 24.04.
"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:

What's the simplest noncontroversial 2-state universal Turing machine?
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?



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
BB(5, 2) was settled by the Busy Beaver Challenge project, actual Collatz-like is at BB(6, 2)

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

> **Comments:**
> **username_10**: 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.  
> **username_10**: Another reason that BB(6) or BB(7) may require serious Math advances to be solved is https://www.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.  
> **username_9**: @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!  
> **username_10**: 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 :)  
> **username_4**: BB(5) has now been computed: https://bbchallenge.org/6137696  
> **username_9**: @Denis yes, I had already recently updated the answer with this info  

---

### Answer by username_11 on 2014-02-11. Score: 4

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](http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine) machine which was found by Alex Smith for which he won a prize of $25,000.

> **Comments:**
> **username_3**: 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.  
> **username_12**: @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".  

---

### Answer by username_13 on 2014-02-12. Score: -5

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](http://arxiv.org/pdf/1311.1029v1.pdf) 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.

> **Comments:**
> **username_3**: 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.  
> **username_13**: 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....  
> **username_3**: 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$.  
> **username_13**: 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).  
> **username_3**: 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.  

---

