View source for 1RB3RB5RA1LB5LA2LB 2LA2RA4RB1RZ3LB2LA

{{Machine|1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA}}
{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA|halt}} is the current [[BB(2,6)]] [[champion]]. It was discovered on the 19th of May 2023 by Pavel Kropitz. It halts with a score > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>.
==Analysis by [[User:Sligocki|Shawn Ligocki]]==
https://www.sligocki.com/2023/05/20/bb-2-6-p3.html
<pre>
Analysis
Level 1
These rules can all be verified by direct simulation:
00 <A 212 22^n 55 → <A 212 22^n+2

00 <A 212 22^n 2 55 → <A 212 55^n+2 2

0^5 <A 212 22^n 52 5555 → <A 212 55 2 55^n+3 52
00 <A 212 22^n 2 52 5 → <A 212 55^n+2 52

Level 2
Repeating the first rule above we get:
0^∞ <A 212 22^n 55^k → 0^∞ 212 22^n+2k

which let's us prove Rule 2:
0^∞ <A 212 22^n 2 55 → 0^∞ <A 212 55^n+2 2
                     → 0^∞ <A 212 22^2n+4 2

Level 3
Repeating Rule 2 we get:
0^∞ <A 212 22^n 2 55^k → 0^∞ <A 212 22^(n+4)*((2^k)-4) 2

which let's us prove Rule 3:
0^∞ <A 212 22^n 52 5^5 → 0^∞ <A 212 55 2 55^n+3 52 5
                       → 0^∞ <A 212 22^2 2 55^n+3 52 5
                       → 0^∞ <A 212 22^(6*2^(n+3)-2) 52 5
                       → 0^∞ <A 212 55^(6*2^(n+3)-2) 52
                       → 0^∞ <A 212 22^(6*2^(n+4)-4) 52

Level 4
Let
f(n) = 6*2^(n+4)-4

Repeating Rule 3 we get the Tetration Rule:
0^∞ <A 212 22^n 52 5^5k → 0^∞ <A 212 22^f^k(n) 52

This rule will be the main contributor to the score since f^k(n) > 2^^k. In fact, this rule will apply 3 times, which is how we end up with 3 tetrations in the final score (>10^^10^^10^^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:
          191
0^∞ <A 0^∞ → 0^∞ <A 212 22^2 52 5^13 2 0^∞

This is our first application of the Tetration Rule. Here calculating the remainder is trivial:
A1 = 13 = 5k1 + r1
r1 = 3
k1 = (A1 - r1)/5 = 2

continuing the trajectory:
...→ 0^∞ <A 212 22^f^2(2) 52 5^3 2 0^∞
   → 0^∞ <A 212 55 2 55^f^2(2)+4 2 0^∞
   → 0^∞ <A 212 22^2 2 55^f^2(2)+4 2 0^∞
   → 0^∞ <A 212 22^(6*2^(f^2(2)+4)-4) 2 2 0^∞
   = 0^∞ <A 212 22^f^3(2)+1 0^∞
   → 0^∞ <A 212 55 52 5^(2*f^3(2)+5) 22 0^∞
   → 0^∞ <A 212 22^2 52 5^(2*f^3(2)+5) 22 0^∞

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):
A2 = 2*f^3(2)+5 = 5k2 + r2
r2 = 4
k2 = (A2 - r2)/5 = (2f^3(2)+1)/5

continuing the trajectory:
...→ 0^∞ <A 212 22^f^k2(2) 52 5^4 22 0^∞
   → 0^∞ <A 212 55 2 55^(f^k2(2))+3 52 22 0^∞
   → 0^∞ <A 212 22^2 2 55^(f^k2(2))+3 52 22 0^∞
   → 0^∞ <A 212 22^(6*(2^(f^k2(2))+3)-4) 2 52 22 0^∞
   → 0^∞ <A 212 55^(6*(2^(f^k2(2))+3)-1) 52 0^∞
   → 0^∞ <A 212 22^(6*(2^(f^k2(2))+4)-2) 52 0^∞
   = 0^∞ <A 212 22^f^k2+1(2)+2 52 0^∞
   → 0^∞ <A 212 55 52 5^(2*(f^k2+1(2))+13) 2 0^∞
   → 0^∞ <A 212 22^2 52 5^(2*(f^k2+1(2))+13) 2 0^∞

This is our third and final application of the Tetration Rule. Here calculating the remainder requires a minor arithmetic miracle (see next section):
A3 = 2*f^k2+1(2)+13 = 5k3 + r3
r3 = 2
k3 = (A3 - r3)/5 = (2*f^k2+1(2)+11)/5

finishing the trajectory:
0^∞ <A 212 22^f^k3(2) 52 5^2 2 0^∞ → 0^∞ 141 Z> 2^(2*f^k3(2)+8) 152 0^∞

And we see that it halts with a score of
Sigma(p3) = 2*f^k3(2)+14

Remainder Miracle

Calculating the remainder
2*f^k2+1(2)+13 (mod 5)
is no simple task given that this is a power tower with height k2 > 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) and 2^4 ≡ 1 (mod 5)

Specifically:
f^2(n) = 6*2^(f(n)+4)-4
       = 6*2^(4x)-4
       ≡ 6 - 4 ≡ 2 (mod 5)

and since this is true for all n, we have:
f^k2+1(2) ≡ 2 (mod 5)

and this remainder becomes trivial to compute!

Halting Score

Collecting together all the relevant definitions, we have the precise number of non-zero symbols on the tape at halting time expressed by this formula:
Sigma(p3) = 2*f^k3(2)+14
k3 = (2*f^k2+1(2)+11)/5
k2 = (2*f^3(2)+1)/5
f(n) = 6*2^(n+4)-4

But we can simplify this notation a bit. First of all, we can define:
g(n) = 6*2^n

and notice that
g(n+4) = f(n+4) ⇒ g^k(n+4) = f^k(n)+4

rewriting we get
Sigma(p3) = 2*g^B(6)+6
B = k3 = (2*g^A(6)+3)/5
A = k2+1 = (2*g^3(6)-2)/5
g(n) = 6*2^n

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^^k)

so, we can rewrite the score again to:
Sigma(p3) = 12*(64^^B)+6
B = (12*(64^^A)+3)/5
A = (12*(64^^3)-2)/5

and thus we can compute this lower bound (which appears pretty tight):
Sigma(p3) > 64^^64^^64^^3

and we can directly compute that 64^64 > 10^115 so:
Sigma(p3) > 10^^10^^10^10^115
</pre>