BB(3, 3) is Hard
I’m excited to share a 3 state, 3 symbol Turing Machine that cannot be proven to halt or not (when starting on a blank tape) without solving a Collatz-like problem. Therefore, solving the \(BB(3, 3)\) problem is at least as hard as solving this Collatz-like problem, a class of problem for which Paul Erdős famously said: “Mathematics may not be ready for such problems.”
Last year, in Mother of Giants, I described a family of TMs which require efficient simulation or complete solution of a Collatz-like problem in order to prove if they “quasihalt” or not. These were found in the search for “Beeping” Busy Beavers, a variant of the Busy Beavers introduced by Scott Aaronson in his 2020 Busy Beaver survey article. Since then I have been looking for an example in the normal Busy Beaver game.
There have been many wonderful TMs produced by hand over the years which provide such results for the Busy Beaver game. For example, proving:
- \(BB(745)\) requires proving the consistency of ZFC
- \(BB(27)\) requires proving the Goldbach Conjecture
- \(BB(15)\) and \(BB(5, 4)\) require proving an Erdős conjecture (that for all \(n > 8\), the base 3 representation of \(2^n\) has at least one digit 2).
However, none of these Busy Beaver values are really within reach of us mere mortals yet. In the last 60 years, we have only been able to prove values \(BB(2), BB(3), BB(4)\) and \(BB(2, 3)\) and it is known that \(BB(6) > 10 \uparrow\uparrow 15\). Until I analyzed this TM, I thought that we might have a chance to prove \(BB(3, 3)\)!
The Machine
I’ll call this TM “Bigfoot” (I’ll explain the name at the end of the article). It is defined by the transition table:
1RB2RA1LC_2LC1RB2RB_---2LA1LA (on bbchallenge)
| 0 | 1 | 2 | |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
It is one of the remaining 160 informal \(BB(3, 3)\) holdouts that Justin Blanchard recently shared on the bbchallenge.org Discord channel. This specific TM was first shared and analyzed by @savask on 14 Oct 2023 on that same Discord channel.
Analysis
Consider the general configuration:
\[A(a, b, c) = 0^\infty \; 12^a \; 11^b \; \text{ <A } \; 11^c \; 0^\infty\]We can prove the following rules:
\[\begin{array}{l} A(a, & 6k, & c) & \to & A(a, & 8k+c-1, & 2) & \text{if} & 8k+c \ge 1 \\ A(a, & 6k+1, & c) & \to & A(a+1, & 8k+c-1, & 3) & \text{if} & 8k+c \ge 1 \\ A(a, & 6k+2, & c) & \to & A(a-1, & 8k+c+3, & 2) & \text{if} & a \ge 1 \\ A(a, & 6k+3, & c) & \to & A(a, & 8k+c+1, & 5) \\ A(a, & 6k+4, & c) & \to & A(a+1, & 8k+c+3, & 2) \\ A(a, & 6k+5, & c) & \to & A(a, & 8k+c+5, & 3) \\ \end{array}\] \[A(0, 6k+2, c) \to \text{Halt}(16k+2c+7)\]In fact, these rules are exhaustive. Once Bigfoot enters such a \(A(a, b, c)\) config (with \(c \ge 1\)), these rules describe the exact behavior it will follow forever (or until it halts).
Looking at the rules above we can see that they are iterating a Collatz-like function on parameters \(b\) and \(c\) while \(a\) keeps a sort of running total. Every time \(b \equiv 1 \pmod{6}\) or \(b \equiv 4 \pmod{6}\), \(a\) is incremented and every time \(b \equiv 2 \pmod{6}\), \(a\) is decremented. Bigfoot only ever halts if \(a\) would be decremented below 0.
Trajectory from Blank Tape
Starting from a blank tape, Bigfoot reaches config \(A(2, 1, 2)\) at step 69. Simulating this forward, \(a\) appears to grow steadily over time. After 24 million iterations, we have \(a = 3\,999\,888\).
Pseudo-Random Walk
Let’s consider the sequence of remainders of \(b\) mod 6. If we imagine that this sequence is uniformly randomly distributed, then this process is simulating a biased random walk on the number line where (for each step) the chance of stepping right is \(\frac{2}{3}\) and the chance of stepping left is \(\frac{1}{3}\).
This is a famous problem in the theory of Markov chains and it can be proven that if you are at position \(a = n\), there is a \((\frac{1}{2})^{n+1}\) chance you will ever reach the position \(a = -1\) in the future.
Of course, the sequence of remainders of \(b\) are not random, they are completely deterministic. (In fact, they even follow the consistent pattern of odd, odd, even, even, …) However, on a broad scale they do appear to follow a trajectory roughly like the random Markov chain. We can see that in the trajectory listed above where after 24 million steps, the Markov chain would be expected to move to the right 8 million times and to the left 4 million leading to a value very close to the actual \(a\) around 4 million.
Probviously Not Halting
As mentioned above, the random Markov chain would have about a \((\frac{1}{2})^{4\,000\,000}\) chance of ever reaching \(a = -1\) at this point which is a number so small that any scientist would happily declare this guaranteed to fail. Likewise, this is where I will say that Bigfoot “probviously” never halts (using the words of John Conway). Meaning that if it operates anything close to the Markov Chain it will never halt.
Of course, this sort of statement says nothing in a rigorous Mathematical sense. Instead it is sort of an experimental heuristic which I am using to guide my intuition in this case. There is always the chance that after a googolplex iterations Bigfoot will halt. In fact, Conway coined this term to describe the heuristic argument for why the Collatz conjecture should be “probviously” true and yet a proof of Collatz is nowhere in sight.
Two Worlds
We live in one of two worlds, either Bigfoot halts or it runs forever. If it halts, then that could be proven by accelerating iterations of this Collatz-like function enough that it is tractable to simulate it to completion. If it runs forever, then proving that requires proving that this Collatz-like function will never reach the \(a = 0\) halting transition.
Based on the Markov chain argument above, I believe we are living in this second world and it seems to me that this is the much harder case to prove.
Cryptids
What do we call these sorts of machines? Ones whose behavior has been distilled into a relatively simple Mathematical rule that falls into a class of open Mathematical problems. These machines seem to be a sort of legendary creature, rumors have it that they either halt or do not, but nobody has been able to provide any concrete evidence to support either conclusion. I propose calling them “Cryptids”, drawing parallels to the legendary creatures like the Loch Ness Monster or Chupacabra. And well, since this TM appears to randomly walk about, I thought Bigfoot would be an apt name.
Is This Collatz-like Behavior Really Hard?
I imagine that some of you might be wondering: Is the behavior of this specific Collatz-like function really hard to analyze? Am I overselling this behavior simply by it’s association with the famously difficult Collatz problem? I think it is safe to say that nobody aside from me has ever looked at the dynamics of this specific problem. So perhaps with a little bit of number theory and elbow grease, someone will be able to find a clever Mathematical property that applies to this problem (but not to the broader set of Collatz-like problems). This is certainly possible and I am excited to hear if anyone has any ideas as to how to attack this problem. It would be lovely to know that proving \(BB(3, 3)\) remains within reach!
However, in my (limited) experience analyzing and reading about Collatz-like problems there seem to be only two types of questions that one can ask: (1) Ones that are relatively trivial to prove and (2) Ones which no Mathematician knows how to prove. In the first category we have patterns like the fact that \(b\) repeats consistently through the pattern (odd, odd, even, even, …) in Bigfoot’s Collatz iterations or that every time you apply the traditional \(3n+1\) Collatz rule you always end up with an even number which will then be divided by 2 on the next step. Examples of the second category include basically all other questions we might ask about the behavior of these Collatz systems.
Alternative Representation
This section was added on 18 Oct 2023
The Collatz-like behavior I described above has a few annoying characteristics:
- It interweaves \(b\) and \(c\) parameters,
- The input modulo (6) and output modulo (8) share a common factor (of 2) and
- The \(b\) parameter follows a consistent repeating pattern odd-odd-even-even.
Shortly after I posted this article, Matthew House (@LegionMammal978 on Discord) pointed out that if you define a new configuration as:
\[B(a, b) = A(a, 2b+1, 2)\]consider \(b = 81k + r\) and apply 4 of the original transitions as one transition, then you can derive the following alternative representation of the Collatz-like behavior of this TM:
Full 81 Cases
$$ \begin{array}{l} B(a, & 81k + 0) & \to & B(a + 1, & 256k + 4) \\ B(a, & 81k + 1) & \to & B(a , & 256k + 8) \\ B(a, & 81k + 2) & \to & B(a + 1, & 256k + 10) \\ B(a, & 81k + 3) & \to & B(a , & 256k + 14) \\ B(a, & 81k + 4) & \to & B(a - 1, & 256k + 18) \\ B(a, & 81k + 5) & \to & B(a - 2, & 256k + 22) \\ B(a, & 81k + 6) & \to & B(a + 2, & 256k + 22) \\ B(a, & 81k + 7) & \to & B(a + 1, & 256k + 26) \\ B(a, & 81k + 8) & \to & B(a , & 256k + 30) \\ B(a, & 81k + 9) & \to & B(a + 4, & 256k + 30) \\ B(a, & 81k + 10) & \to & B(a - 2, & 256k + 38) \\ B(a, & 81k + 11) & \to & B(a + 2, & 256k + 38) \\ B(a, & 81k + 12) & \to & B(a + 1, & 256k + 42) \\ B(a, & 81k + 13) & \to & B(a , & 256k + 46) \\ B(a, & 81k + 14) & \to & B(a + 1, & 256k + 48) \\ B(a, & 81k + 15) & \to & B(a , & 256k + 52) \\ B(a, & 81k + 16) & \to & B(a + 2, & 256k + 54) \\ B(a, & 81k + 17) & \to & B(a , & 256k + 58) \\ B(a, & 81k + 18) & \to & B(a + 2, & 256k + 60) \\ B(a, & 81k + 19) & \to & B(a + 1, & 256k + 64) \\ B(a, & 81k + 20) & \to & B(a , & 256k + 68) \\ B(a, & 81k + 21) & \to & B(a + 1, & 256k + 70) \\ B(a, & 81k + 22) & \to & B(a , & 256k + 74) \\ B(a, & 81k + 23) & \to & B(a - 1, & 256k + 78) \\ B(a, & 81k + 24) & \to & B(a + 3, & 256k + 78) \\ B(a, & 81k + 25) & \to & B(a , & 256k + 84) \\ B(a, & 81k + 26) & \to & B(a + 1, & 256k + 86) \\ B(a, & 81k + 27) & \to & B(a , & 256k + 90) \\ B(a, & 81k + 28) & \to & B(a - 1, & 256k + 94) \\ B(a, & 81k + 29) & \to & B(a + 3, & 256k + 94) \\ B(a, & 81k + 30) & \to & B(a + 2, & 256k + 98) \\ B(a, & 81k + 31) & \to & B(a + 1, & 256k + 102) \\ B(a, & 81k + 32) & \to & B(a , & 256k + 106) \\ B(a, & 81k + 33) & \to & B(a + 1, & 256k + 108) \\ B(a, & 81k + 34) & \to & B(a + 3, & 256k + 110) \\ B(a, & 81k + 35) & \to & B(a - 1, & 256k + 116) \\ B(a, & 81k + 36) & \to & B(a + 3, & 256k + 116) \\ B(a, & 81k + 37) & \to & B(a , & 256k + 122) \\ B(a, & 81k + 38) & \to & B(a + 1, & 256k + 124) \\ B(a, & 81k + 39) & \to & B(a , & 256k + 128) \\ B(a, & 81k + 40) & \to & B(a - 1, & 256k + 132) \\ B(a, & 81k + 41) & \to & B(a , & 256k + 134) \\ B(a, & 81k + 42) & \to & B(a - 1, & 256k + 138) \\ B(a, & 81k + 43) & \to & B(a + 1, & 256k + 140) \\ B(a, & 81k + 44) & \to & B(a + 2, & 256k + 142) \\ B(a, & 81k + 45) & \to & B(a + 1, & 256k + 146) \\ B(a, & 81k + 46) & \to & B(a , & 256k + 150) \\ B(a, & 81k + 47) & \to & B(a - 1, & 256k + 154) \\ B(a, & 81k + 48) & \to & B(a + 3, & 256k + 154) \\ B(a, & 81k + 49) & \to & B(a + 2, & 256k + 158) \\ B(a, & 81k + 50) & \to & B(a + 1, & 256k + 162) \\ B(a, & 81k + 51) & \to & B(a + 2, & 256k + 164) \\ B(a, & 81k + 52) & \to & B(a - 1, & 256k + 170) \\ B(a, & 81k + 53) & \to & B(a , & 256k + 172) \\ B(a, & 81k + 54) & \to & B(a + 2, & 256k + 174) \\ B(a, & 81k + 55) & \to & B(a + 1, & 256k + 178) \\ B(a, & 81k + 56) & \to & B(a + 2, & 256k + 180) \\ B(a, & 81k + 57) & \to & B(a + 1, & 256k + 184) \\ B(a, & 81k + 58) & \to & B(a , & 256k + 188) \\ B(a, & 81k + 59) & \to & B(a - 1, & 256k + 192) \\ B(a, & 81k + 60) & \to & B(a , & 256k + 194) \\ B(a, & 81k + 61) & \to & B(a + 2, & 256k + 196) \\ B(a, & 81k + 62) & \to & B(a - 2, & 256k + 202) \\ B(a, & 81k + 63) & \to & B(a + 2, & 256k + 202) \\ B(a, & 81k + 64) & \to & B(a - 1, & 256k + 208) \\ B(a, & 81k + 65) & \to & B(a , & 256k + 210) \\ B(a, & 81k + 66) & \to & B(a - 1, & 256k + 214) \\ B(a, & 81k + 67) & \to & B(a - 2, & 256k + 218) \\ B(a, & 81k + 68) & \to & B(a + 2, & 256k + 218) \\ B(a, & 81k + 69) & \to & B(a + 1, & 256k + 222) \\ B(a, & 81k + 70) & \to & B(a , & 256k + 226) \\ B(a, & 81k + 71) & \to & B(a + 1, & 256k + 228) \\ B(a, & 81k + 72) & \to & B(a + 3, & 256k + 230) \\ B(a, & 81k + 73) & \to & B(a + 2, & 256k + 234) \\ B(a, & 81k + 74) & \to & B(a + 1, & 256k + 238) \\ B(a, & 81k + 75) & \to & B(a + 2, & 256k + 240) \\ B(a, & 81k + 76) & \to & B(a + 1, & 256k + 244) \\ B(a, & 81k + 77) & \to & B(a , & 256k + 248) \\ B(a, & 81k + 78) & \to & B(a + 1, & 256k + 250) \\ B(a, & 81k + 79) & \to & B(a + 1, & 256k + 254) \\ B(a, & 81k + 80) & \to & B(a - 1, & 256k + 258) \\ \end{array}$$Note: Some of these rules depend upon \(a \ge 2\).
This representation addresses all 3 of the listed characteristics of \(A\) and appears more akin to the classic Collatz problem. But, of course, it is also a bit unwieldy with its 81 cases!