View source for 1RB1RC 1LC1RE 1LD0LB 1RE1LC 1LE0RF 1RZ1RA

{{machine|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}

{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}} is a long running Halting [[BB(6)]] TM analyzed by Racheline on 25 Nov 2024 ([https://discord.com/channels/960643023006490684/1239205785913790465/1310651468881334394 Discord Link]). It runs for over <math>10 \uparrow\uparrow 7</math> steps. It is a halting [[shift overflow counter]].

Analysis by Racheline:
<pre>
a_1 = (2^179+1)/3+179
a_2 = (2^a_1+1)/3+a_1
a_3 = (2^a_2+1)/3+a_2
a_4 = (2^a_3+1)/3+a_3-1
a_5 = (2^a_4+1)/3+a_4

the tapes after overflow:
0^∞ <B 0 (10)^17 11 (10)^5 11 (10)^3 11 (10)^2 1111 0^∞
0^∞ <B 0 (10)^513 11 (10)^17 11 (10)^5 11 (10)^3 11 10 1111 0^∞
0^∞ <B 0 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^4 1111 0^∞
0^∞ <B 0 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^3 1111 0^∞
0^∞ <B 0 (10)^(2^a_2+1) 11 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^3 11 0^∞
0^∞ <B 0 (10)^(2^a_3+1) 11 (10)^(2^a_2+1) 11 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^2 11 0^∞
0^∞ <B 0 (10)^(2^a_4+1) 11 (10)^(2^a_3+1) 11 (10)^(2^a_2+1) 11 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^4 111111 10 11 0^∞

halt at roughly 2^a_5 ≈ 2^2^2^2^2^(2^179/3) ≈ 10^10^10^10^10^10^52.8
</pre>
Between overflows, the right side of the TM is a binary counter, whose bits are either <math>(101010\ |\ 111111)</math>, <math>(10101110\ |\ 11111011)</math>, <math>(1011101010\ |\ 1110111111)</math> or <math>(11101010\ |\ 10111111)</math>, except for the least significant bit which is <math>(1010\ |\ 1111)</math>, where <math>(x\ |\ y)</math> means the bit looks like <math>x</math> when it represents a 0 on the counter, and it looks like <math>y</math> when it represents a 1. The counter is split into bits in a greedy way from left to right. For example, when the tape is <math>0^\infty\! <\!\!B\ 0\ (10)^{17}\ 11\ (10)^5\ 11\ (10)^3\ 11\ (10)^2\ 1111\ 0^\infty</math>, the counter is split into bits as <math>(1010)\ (101010)^5\ (11101010)\ (10101110)^2</math>, and we have <math>101111\ 0^\infty</math> left over at the right end.

The left side is simply a bouncer, which expands leftwards by 2 cells each time the counter increases by 1. To accelerate the TM, we can skip from one overflow to the next by splitting the counter into bits, setting all the bits to represent 1 instead of 0, running the TM (and accelerating its passes through the bits) until it reaches the left end again (which it will do in state B), and then changing the <math>0^\infty\! <\!\!B\ 0\ (10)^2\ 11</math> on the left end into <math>0^\infty\! <\!\!B\ 0\ (10)^{2^n+1}\ 11</math> where <math>n</math> is the number of bits, because the bouncer's size would have increased by <math>2\cdot(2^n-1)</math> cells during the counting we skipped.

Splitting the counter into bits is simple even for very large tapes like <math>0^\infty\! <\!\!B\ 0\ (10)^{2^{a_3}+1}\ 11\ (10)^{2^{a_2}+1}\ 11\ (10)^{2^{a_1}+1}\ 11\ (10)^{2^{179}+1}\ 11\ (10)^{513}\ 11\ (10)^{17}\ 11\ (10)^5\ 11\ (10)^2\ 11\ 0^\infty</math>, because almost all bits are <math>(101010\ |\ 111111)</math>, so we only need to compute the remainders modulo 3 of the amounts of <math>10</math>s between each pair of consecutive <math>11</math>s, and <math>2^n\ (\text{mod}\ 3)</math> only depends on the parity of <math>n</math>.