At the end up my previous post on Wednesday, I guessed that there was “pentation-level” TM in the 3x4 domain. Meanwhile, Pavel was already searching for one and on Friday (19 May 2023), he shared a 2-state, 6-symbol TM which I analyze as scoring > 10↑↑10↑↑10↑↑3 or > 10↑↑↑3!

I am calling this a “pentation-level” TM because its score cannot be expressed using only one tetration operation. As far as I know this is the first pentation-level TM discovered through search.1

The Machine

Let’s call this TM p3. It is:

1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA

  0 1 2 3 4 5
A 1RB 3RB 5RA 1LB 5LA 2LB
B 2LA 2RA 4RB 1RZ 3LB 2LA

I calculate that this TM halts with a score of precisely:

\[\begin{array}{l} \sigma(\text{p3}) & = & 2 g^B(6) + 6 \\ B & = & \frac{2 g^A(6) + 3}{5} \\ A & = & \frac{2 g^3(6) - 2}{5} \\ g(n) & = & 6 \cdot 2^n \\ \end{array}\]

Which is approximated by:

\[\sigma(\text{p3}) > 10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^{115}}\]

Analysis

Level 1

These rules can all be verified by direct simulation:

\[\begin{array}{l} 00 & <A & 212 & 22^n & 55 & & && \to & <A & 212 & 22^{n+2} \\ \\ 00 & <A & 212 & 22^n & & 2 & 55 && \to & <A & 212 & & 55^{n+2} & 2 \\ \\ 0^5 & <A & 212 & 22^n & & 52 & 5555 && \to & <A & 212 & & 55 & 2 & 55^{n+3} & 52 \\ 00 & <A & 212 & 22^n & & 2 & 52 & 5 &\to & <A & 212 & & 55^{n+2} & 52 \\ \end{array}\]

Level 2

Repeating the first rule above we get:

\[\begin{array}{l} 0^\infty & <A & 212 & 22^n & 55^k & \to & 0^\infty & <A & 212 & 22^{n+2k} \\ \end{array}\]

which let’s us prove Rule 2:

\[\begin{array}{l} 0^\infty & <A & 212 & 22^n && 2 & 55 & \to & 0^\infty & <A & 212 & & 55^{n+2} & 2 \\ & & & && & & \to & 0^\infty & <A & 212 & 22^{2n+4} & & 2 \\ \end{array}\]

Level 3

Repeating Rule 2 we get:

\[\begin{array}{l} 0^\infty & <A & 212 & 22^n && 2 & 55^k & \to & 0^\infty & <A & 212 & 22^{(n+4) 2^k - 4} && 2 \\ \end{array}\]

which let’s us prove Rule 3:

\[\begin{array}{l} 0^\infty & <A & 212 & 22^n && 52 & 5^5 & \to & 0^\infty & <A & 212 & & 55 & 2 & 55^{n+3} & 52 & 5 \\ & & & && & & \to & 0^\infty & <A & 212 & 22^2 && 2 & 55^{n+3} & 52 & 5 \\ & & & && & & \to & 0^\infty & <A & 212 & 22^{6 \cdot 2^{n+3} - 4} && 2 && 52 & 5 \\ & & & && & & \to & 0^\infty & <A & 212 & & 55^{6 \cdot 2^{n+3} - 2} & 52 \\ & & & && & & \to & 0^\infty & <A & 212 & 22^{6 \cdot 2^{n+4} - 4} && 52 \\ \end{array}\]

Level 4

Let

\[f(n) = 6 \cdot 2^{n+4} - 4\]

Repeating Rule 3 we get the Tetration Rule:

\[\begin{array}{l} 0^\infty & <A & 212 & 22^n && 52 & 5^{5k} & \to & 0^\infty & <A & 212 & 22^{f^k(n)} && 52 \\ \end{array}\]

This rule will be the main contributor to the score since \(f^k(n) > 2 \uparrow\uparrow k\). In fact, this rule will apply 3 times, which is how we end up with 3 tetrations in the final score (\(> 10 \uparrow\uparrow 10 \uparrow\uparrow 10\uparrow\uparrow 3\)).

Halting Trajectory

With these high-level rules, we are now ready to describe the halting trajectory for this TM starting from a blank tape:

\[\begin{array}{l} 0^\infty & <A & 0^\infty & \xrightarrow{191} & 0^\infty & <A & 212 & 22^2 & 52 & 5^{13} & 2 & 0^\infty \end{array}\]

This is our first application of the Tetration Rule. Here calculating the remainder is trivial:

\[\begin{array}{l} A_1 & = & 13 & = & 5 k_1 + r_1 \\ r_1 & = & 3 \\ k_1 & = & \frac{A_1 - r_1}{5} & = & 2 \\ \end{array}\]

continuing the trajectory:

\[\begin{array}{l} \dots & \to & 0^\infty & <A & 212 & 22^{f^2(2)} & & 52 & 5^{3} & 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & & 55 & 2 & 55^{f^2(2) + 4} & 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^2 & & 2 & 55^{f^2(2) + 4} & 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^{6 \cdot 2^{f^2(2) + 4} - 4} && 2 & & 2 & 0^\infty \\ & = & 0^\infty & <A & 212 & 22^{f^3(2) + 1} && & & & 0^\infty \\ & \to & 0^\infty & <A & 212 & & 55 & 52 & 5^{2 f^3(2) + 5} & 2 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^2 & & 52 & 5^{2 f^3(2) + 5} & 2 2 & 0^\infty \\ \end{array}\]

This is our second application of the Tetration Rule. Here calculating the remainder requires using Euler’s totient theorem (as described in BB(6, 2) > 10↑↑15):

\[\begin{array}{l} A_2 & = & 2 f^3(2) + 5 & = & 5 k_2 + r_2 \\ r_2 & = & 4 \\ k_2 & = & \frac{A_2 - r_2}{5} & = & \frac{2 f^3(2) + 1}{5} \\ \end{array}\]

continuing the trajectory:

\[\begin{array}{l} \dots & \to & 0^\infty & <A & 212 & 22^{f^{k_2}(2)} & & 52 & 5^{4} & & 2 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & & 55 & 2 & 55^{f^{k_2}(2)+3} & 52 & 2 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^2 & & 2 & 55^{f^{k_2}(2)+3} & 52 & 2 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^{6 \cdot 2^{f^{k_2}(2)+3} - 4} && 2 & & 52 & 2 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & & 55^{6 \cdot 2^{f^{k_2}(2)+3} - 1} & 52 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^{6 \cdot 2^{f^{k_2}(2)+4} - 2} & & 52 & 0^\infty \\ & = & 0^\infty & <A & 212 & 22^{f^{k_2 + 1}(2) + 2} & & 52 & 0^\infty \\ & \to & 0^\infty & <A & 212 & & 55 & 52 & 5^{2 f^{k_2 + 1}(2) + 13} & 2 & 0^\infty \\ & \to & 0^\infty & <A & 212 & 22^2 & & 52 & 5^{2 f^{k_2 + 1}(2) + 13} & 2 & 0^\infty \\ \end{array}\]

This is our third and final application of the Tetration Rule. Here calculating the remainder requires a minor arithmetic miracle (see next section):

\[\begin{array}{l} A_3 & = & 2 f^{k_2 + 1}(2) + 13 & = & 5 k_3 + r_3 \\ r_3 & = & 2 \\ k_3 & = & \frac{A_3 - r_3}{5} & = & \frac{2 f^{k_2 + 1}(2) + 11}{5} \\ \end{array}\]

finishing the trajectory:

\[\begin{array}{l} 0^\infty & <A & 212 & 22^{f^{k_3}(2)} & 52 & 5^{2} & 2 & 0^\infty & \to & 0^\infty & 141 & Z> & 2^{2 f^{k_3}(2) + 8} & 152 & 0^\infty \\ \end{array}\]

And we see that it halts with a score of

\[\sigma(\text{p3}) = 2 f^{k_3}(2) + 14\]

Remainder Miracle

Calculating the remainder

\[2 f^{k_2 + 1}(2) + 13 \pmod{5}\]

is no simple task given that this is a power tower with height \(k_2 > 10^{10^{100}}\) (a googolplex) and that the Euler’s totient theorem method for computing remainders is worse than linear on power tower heights!

But, as it turns out, there is a miraculous shortcut to this computation in this specific case!

The miracle can be summarized succinctly by the following two facts:

\[4 | f(n) \;\; \text{ and } \;\; 2^4 \equiv 1 \pmod{5}\]

Specifically:

\[\begin{array}{l} f^2(n) & = & 6 \cdot 2^{f(n)+4} - 4 \\ & = & 6 \cdot 2^{4x} - 4 \\ & \equiv & 6 - 4 \equiv 2 \pmod{5} \\ \end{array}\]

and since this is true for all \(n\), we have:

\[f^{k_2 + 1}(2) \equiv 2 \pmod{5}\]

and this remainder becomes trivial to compute!

Halting Score

Collecting together all the relevent definitions, we have the precise number of non-zero symbols on the tape at halting time expressed by this formula:

\[\begin{array}{l} \sigma(\text{p3}) & = & 2 f^{k_3}(2) + 14 \\ k_3 & = & \frac{2 f^{k_2 + 1}(2) + 11}{5} \\ k_2 & = & \frac{2 f^3(2) + 1}{5} \\ f(n) & = & 6 \cdot 2^{n+4} - 4 \\ \end{array}\]

But we can simplify this notation a bit. First of all, we can define:

\[g(n) = 6 \cdot 2^n\]

and notice that

\[g(n+4) = f(n) + 4 \implies g^k(n+4) = f^k(n) + 4\]

rewriting we get

\[\begin{array}{l} \sigma(\text{p3}) & = & 2 g^B(6) + 6 \\ B = k_3 & = & \frac{2 g^A(6) + 3}{5} \\ A = k_2 + 1 & = & \frac{2 g^3(6) - 2}{5} \\ g(n) & = & 6 \cdot 2^n \\ \end{array}\]

In fact, we could even rewrite it as:

\[h(n) = 2^{6n} = 64^n\]

and notice

\[g^k(6) = 6 h^k(1) = 6 (64 \uparrow\uparrow k)\]

so, we can rewrite the score again to:

\[\begin{array}{l} \sigma(\text{p3}) & = & 12 (64 \uparrow\uparrow B) + 6 \\ B & = & \frac{12 (64 \uparrow\uparrow A) + 3}{5} \\ A & = & \frac{12 (64 \uparrow\uparrow 3) - 2}{5} \\ \end{array}\]

and thus we can compute this lower bound (which appears pretty tight):

\[\sigma(\text{p3}) > 64 \uparrow\uparrow 64 \uparrow\uparrow 64 \uparrow\uparrow 3\]

and we can directly compute that \(64^{64} > 10^{115}\) so:

\[\sigma(\text{p3}) > 10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^{115}}\]

Footnotes

  1. Although there are certainly previous examples of hand-designed pentation-level TMs. For example, Milton Green’s \(BB(11, 2) > 3 \uparrow\uparrow\uparrow 3^{31}\)) and Daniel Nagaj’s BB(16, 2) > Graham’s number. ↩