1RB1RA 1LC1LE 1RE0LD 1LC0LF 1RZ0RA 0RA0LB: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
(Added "halt" to bbch-link)
(Added "halt" to bbch-link of sister machine)
 
Line 3: Line 3:


== Analysis by @poppuncher ==
== Analysis by @poppuncher ==
Most of the initial analysis was done on its sister machine {{TM|1RB0RF_1LC0RA_1RZ0LD_1LE1LD_1RB1RC_0LD0RE}} which has identical behavior but with different starting conditions. The sister machine halts with a smaller, though still enormous, sigma score of roughly <math>10 \uparrow \uparrow 5.77573</math>. The following explanation describes this sister machine, but aside from the starting conditions and states, it applies to the larger machine as well.
Most of the initial analysis was done on its sister machine {{TM|1RB0RF_1LC0RA_1RZ0LD_1LE1LD_1RB1RC_0LD0RE|halt}} which has identical behavior but with different starting conditions. The sister machine halts with a smaller, though still enormous, sigma score of roughly <math>10 \uparrow \uparrow 5.77573</math>. The following explanation describes this sister machine, but aside from the starting conditions and states, it applies to the larger machine as well.


<pre>
<pre>

Latest revision as of 18:29, 16 August 2025

1RB1RA_1LC1LE_1RE0LD_1LC0LF_1RZ0RA_0RA0LB (bbch) is a tetrational halting BB(6) TM first discovered and analyzed by @poppuncher. It was shared on Discord on 5 Jun 2025 (Discord Link). It is a translated counter that halts with a final sigma score of roughly .

Analysis by @poppuncher

Most of the initial analysis was done on its sister machine 1RB0RF_1LC0RA_1RZ0LD_1LE1LD_1RB1RC_0LD0RE (bbch) which has identical behavior but with different starting conditions. The sister machine halts with a smaller, though still enormous, sigma score of roughly . The following explanation describes this sister machine, but aside from the starting conditions and states, it applies to the larger machine as well.

basically, there is a unary counter on one side and a weird binary counter on the other side.

the weird binary counter behaves as if counting the number of bit flips required to increment a binary number (let's call it A) of a given length n, until it reaches 2^n. the number of flips are written to the unary counter, which then resets, and the process starts again with a new binary string.

For example, let n = 6 and A = 48, which is 110000 in binary, then it will count up to 1000000. there is a formula for the number of bit flips required, which is  2^(n+1) - 2*A - 1 + pop_count(A), where pop_count is the number of '1's in the binary representation of A. In this example
it evaluates to 2^7-2*48-1+2 = 33.

Note that leading zeroes are  allowed, so if n = 9 and A = 48, then
we are counting 000110000 until it reaches 1000000000, and the count will be 2^10-2*48-1+2 = 417.

now for the halting part, i can prove that the following rules:
A> 0 1^(5n+0) -> (10 110)^n <D 01
A> 0 1^(5n+1) -> (10 110)^n 10 <D 01
A> 0 1^(5n+2) -> (10 110)^n 110 <D 01
A> 0 1^(5n+3) -> (10 110)^n 10 10 10 <D 01
A> 0 1^(5n+4) -> Halt(3n+3)

the binary counter encodes the binary string such that "10" on the tape corresponds to 0, and "110" corresponds to 1, (also the most significant bit is on the right, so we need to flip it)

for example at t = 159, the tape is 0^inf 10 10 10 10 110 110 <D 01 0^inf, which corresponds to 110000 (this is also the example earlier, with n = 6 and A = 48). 
with this in mind, i got the following rules:
A(n) is the numerical value of the binary string, L(n) is the length of the string, P(n) is the count of '1's in the string, and R(n) is the amount of increments made on the unary counter, counting the number of bit flips before it resets
initial conditions: A(1) = 0, L(1) = 2
P(n) := pop_count(A(n))
R(n) := 2^(1 + L(n))  - 2*A(n) - 1 + P(n)
k(n) := R(n)//5 (division without remainder)
r(n) := R(n) % 5, (so R(n) = 5*k(n) + r(n))

then we have P(1) = 0, R(1) = 7;

the rules:
if R(n) mod 5 == 4 then halt 
otherwise
let a(r) = {0, 1, 1, 3} (for 0 <= r < 4)
then
L(n+1) = L(n) + 1 + 2 * k(n) + a(r(n))
A(n+1) = 2 ^ (2 + L(n)) * ( 2^(2*k(n)) - 1 ) / 3 + (if r(n) = 2 then 2 ^ ( L(n)+1 + 2*k(n) ) otherwise 0)
P(n+1) = pop_count(A(n+1)) = k(n) + (if r(n) = 2 then 1 otherwise 0) 

Analysis by Katelyn Doucette

The machine follows these rules:

Let s = 2^{b+2} - 2 + 2^{b+2}((4^k - 1)/3) + k

START = A(1, 3)

A(5k + 0, b) -> A(s + 1, b + 2k + 1)

A(5k + 1, b) -> A(s + 1 + 2^{(b+2k+1)+1}, b + 2k + 2)

A(5k + 2, b) -> A(s + 2, b + 2k + 2)

A(5k + 3, b) -> A(s + 1 + 2^{b+2k+2}(7), b + 2k + 4)

A(5k + 4, b) -> Halt(b + 3k + 4)

And runs through seven of these resets before reaching and halting.

These configurations are identifiable as the transition of this form: 1^(5k+r) 01 <B (01)^b

Evaluation

Both @poppuncher and Katelyn Doucette's rules were evaluated on both machines and line up with one another providing high confidence that the analyses and final sigma scores are correct.

@poppuncher's rules were evaluated by Shawn Ligocki.