BB(3, 4) > 10↑↑2048
Pavel Kropitz found a 3state, 4symbol TM which scores > 10↑↑2048! (originally shared on bbchallenge.org Discord on 5 May 2023). And, in fact, the analysis is surprisingly simple, so I thought it would be fun to share it.
The Machine
Let’s call this TM t2048
. It is:
1RB0LB1RZ3LA_0LC3RB3RC1LB_2RB2LA3RA1LC
0  1  2  3  

A  1RB  0LB  1RZ  3LA 
B  0LC  3RB  3RC  1LB 
C  2RB  2LA  3RA  1LC 
And the precise number of nonzeros it leaves on the tape are:
\[\sigma(\text{t2048}) = g^{2^{11}}(19) + 2\]where
\[g(n) = 2^n + 2\]and where \(g^{2^{11}}(19)\) means repeatedly applying the function \(g\), starting with 19 and iterating \(2^{11} = 2048\) times.
or, alternatively this can be written (using my Extending Uparrow Notation) as:
\[\sigma(\text{t2048}) = 4 (16 \uparrow\uparrow (2^{11}  1) [\uparrow 2^{17}]) + 4\]Since 16 and \(2^{17}\) are both > 10, we can see that
\[\sigma(\text{t2048}) > 10 \uparrow\uparrow 2^{11} = 10 \uparrow\uparrow 2048\]Analysis
Consider the general config:
\[B(a, b, c, d) = \;\; 0^\infty \;\; 33^a \;\; \text{ B> } \;\; 33^b \;\; 2 \;\; 1^c \;\; 3^d \;\; 2 \;\; 0^\infty\]Level 1
Once this TM enters a config like this it never leaves. Specifically we can prove by direct TM simulation the following rules (for all \(a, b, c, d \ge 0\)):
\[\begin{array}{l} B(a, b+1, c, d) & \to & B(a+2, b, c, d) \\ B(a, 0, c+1, d) & \to & B(1, a, c, d) \\ B(a, 0, 0, d+2) & \to & B(1, 1, 2a+1, d) \\ B(a, 0, 0, 0) & \to & B(1, 1, 16, 4a+3) \\ B(a, 0, 0, 1) & \to & \text{Halt}(2a+6) \\ \end{array}\]Level 2
Now, as usual, we can iterate the above rules to prove that:
\[\begin{array}{l} B(a, b, c, d) & \to & B(a+2b, 0, c, d) \\ B(a, 0, c+1, d) & \to & B(2a+1, 0, c, d) \\ \end{array}\]because if \(h(a) = a+2\) then \(h^b(a) = a+2b\)
Level 3
\[\begin{array}{l} B(a, 0, c, d) & \to & B((a+1) 2^c  1, 0, 0, d) \\ B(a, 0, 0, d+2) & \to & B(4 \cdot 2^{2a+1}  1, 0, 0, d) \\ \end{array}\]because if \(h(a) = 2a+1\) then \(h^c(a) = (a+1) 2^c  1\)
Level 4
\[\begin{array}{l} B(a, 0, 0, 2k+r) & \to & B(f^{k}(a), 0, 0, r) \\ \end{array}\]Where
\[f(n) = 4 \cdot 2^{2n+1}  1 = 2^{2n+3}  1\]Halting Trajectory
Finally, This TM enters config \(B(1, 1, 8, 0)\) at step 103. So we can see that the trajectory from this is:
\[\begin{array}{l} B(1, 1, 8, 0) & \to & B(3, 0, 8, 0) \\ & \to & B(4 \cdot 2^{8}  1, 0, 0, 0) \\ & \to & B(1, 1, 16, 16 \cdot 2^{8}  1) \\ & \to & B(3, 0, 16, 16 \cdot 2^{8}  1) \\ & \to & B(4 \cdot 2^{16}  1, 0, 0, 16 \cdot 2^{8}  1) \\ & \to & B(f^{8 \cdot 2^{8}  1}(4 \cdot 2^{16}  1), 0, 0, 1) \\ & \to & \text{Halt}(2 f^{8 \cdot 2^{8}  1}(4 \cdot 2^{16}  1) + 6) \\ \end{array}\]Simplifying a bit we get: \(\text{Halt}(2 f^{2^{11}  1}(2^{18}  1) + 6)\)
Simplified Notation
Iterating \(f(n) = 2^{2n+3}  1\) is a bit cumbersome, we can simplify things in a couple different ways:
Let \(g(n) = 2^n + 2\), then note that \(g(2n+4) = 2 f(n) + 4\), so \(g^k(2n+4) = 2 f^k(n) + 4\) for all \(k\) and thus:
\[\sigma(\text{t2048}) = 2 f^{2^{11}  1}(2^{18}  1) + 6 = g^{2^{11}  1}(2^{19} + 2) + 2 = g^{2^{11}}(19) + 2\]This \(g\) gives us insight into what the power tower looks like. Specifically:
\[\sigma(\text{t2048}) = g^{2^{11}}(19) + 2 = 2 + 2 + 2^{2 + 2^{2 + 2^{.^{.^{.^{2 + 2^{19}}}}}}}\]Tower Notation
Alternatively, let \(h(n) = 16^n\), then \(4 h(n) + 2 = g(4n+2)\), so \(4 h^k(n) + 2 = g^k(4n+2)\) and so we get:
\[\sigma(\text{t2048}) = g^{2^{11}  1}(2^{19} + 2) + 2 = 4 h^{2^{11}  1}(2^{17}) + 4 = 4 (16 \uparrow\uparrow (2^{11}  1) [\uparrow 2^{17}]) + 4\]Which has the advantage that we can express the value without need for defining a new custom function (only using “standard” extended uparrow notation).
Not Collatzlike Behavior
Note that this TMs behavior is not really “Collatzlike” in the sense that we can definitively prove that all configurations \(B(a, b, c, d)\) eventually halt!
Specifically, note that:
\[\begin{array}{l} B(a, b, c, 2k+1) & \to & B(a+2b, 0, c, 2k+1) \\ & \to & B((a+2b+1) 2^c  1, 0, 0, 2k+1) \\ & \to & B(f^{k}((a+2b+1) 2^c  1), 0, 0, 1) \\ & \to & \text{Halt}(2 f^{k}((a+2b+1) 2^c  1) + 6) \\ \end{array}\]and
\[\begin{array}{l} B(a, b, c, 2k) & \to & B(a+2b, 0, c, 2k) \\ & \to & B((a+2b+1) 2^c  1, 0, 0, 2k) \\ & \to & B(f^{k}((a+2b+1) 2^c  1), 0, 0, 0) \\ & \to & B(1, 1, 16, 4 f^{k}((a+2b+1) 2^c  1) + 3) \\ \end{array}\]And since \(4 f^{k}((a+2b+1) 2^c  1) + 3\) is guaranteed to be odd, that also halts.^{1}
In fact, no matter what starting configurations \(B(a, b, c, d)\) we can apply the “towerlevel” rule \(B(a, 0, 0, 2k+r) \to B(f^{k}(a), 0, 0, r)\) at most twice (once if \(d\) is odd, twice if \(d\) is even).
Pentationlevel TM
If this TM could have applied that rule even one more time it would have produced a score like \(2 \uparrow\uparrow 2 \uparrow\uparrow n\), if 4 times, then something like \(2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow n\), if 100 times, then something like \(2 \uparrow\uparrow\uparrow 100\).
In other words, if we can find a TM with behavior similar to this one but which actually has Collatzlike behavior (and which gets lucky enough to iterate it’s “towerlevel” rule a large number of times) then that TM will be “pentationlevel”.
Given the fact that t2048
has such a simple analysis and the fact that neither Pavel nor I have the ability to detect such a “pentationlevel” machine, I think there is a strong chance that one is lurking in the 3x4 domain!
Footnotes

Note: This is similar to the behavior for my shortreigning BB(6, 2) > \(10^{78913}\) champion, but with one extra “level” of rule iteration. ↩