Pavel Kropitz found a 3-state, 4-symbol 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 Up-arrow 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 up-arrow notation).

Not Collatz-like Behavior

Note that this TMs behavior is not really “Collatz-like” 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 “tower-level” 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).

Pentation-level 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 Collatz-like behavior (and which gets lucky enough to iterate it’s “tower-level” rule a large number of times) then that TM will be “pentation-level”.

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 “pentation-level” machine, I think there is a strong chance that one is lurking in the 3x4 domain!

Footnotes

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