1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA
1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA (bbch) is a long running halting BB(6) TM analyzed by Racheline on 25 Nov 2024 (Discord Link). It runs for over steps. It is a halting shift overflow counter.
Analysis by Racheline:
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
Between overflows, the right side of the TM is a binary counter, whose bits are either , , or , except for the least significant bit which is , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x\ |\ y)} means the bit looks like Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} when it represents a 0 on the counter, and it looks like Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\! <\!\!B\ 0\ (10)^{17}\ 11\ (10)^5\ 11\ (10)^3\ 11\ (10)^2\ 1111\ 0^\infty} , the counter is split into bits as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1010)\ (101010)^5\ (11101010)\ (10101110)^2} , and we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 101111\ 0^\infty} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\! <\!\!B\ 0\ (10)^2\ 11} on the left end into Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\! <\!\!B\ 0\ (10)^{2^n+1}\ 11} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is the number of bits, because the bouncer's size would have increased by cells during the counting we skipped.
Splitting the counter into bits is simple even for very large tapes like Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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} , because almost all bits are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (101010\ |\ 111111)} , so we only need to compute the remainders modulo 3 of the amounts of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10} s between each pair of consecutive Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11} s, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n\ (\text{mod}\ 3)} only depends on the parity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .