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.