1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL

From BusyBeaverWiki
Jump to navigation Jump to search

1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL (bbch) is a former BB(13) champion. This machine was found by Racheline using an 8-state fω-level mechanism (in the Fast-Growing Hierarchy) shared by the previous BB(13) champion and BB(14) champion. Instead of using the 5 extra states to build a large input to which fω would be applied once before halting, this machine applies fω repeatedly with Collatz-like rules, which allows it to halt with over fω(fω(fω(fω(70)))) ones on the tape.

Analysis

The fω mechanism operates on lists of numbers, and simulates the rule

B(a0,0k,a1+1,a2,a3,,am)B(0k,a0+3,a1,a2,a3,,am)

where 0k denotes k consecutive zeroes in the list, using configurations of the form B(a0,a1,a2,,am)=01B>1a0101a1101a210101am100.
This computes a slightly modified Fast-Growing Hierarchy. In particular, letting

h0(n)=n+3hk+1(n)=hkn(1)

one can prove by induction on k that

B(a04,0k,a1+1,a2,a3,,am)B(hk(a0)4,0k,a1,a2,a3,,am)

for a04. This motivates the use of B(a0,a1,,am)=A(a04,a1,,am) instead, so that

B(a0,0k,a1+1,a2,a3,,am)B(hk(a0),0k,a1,a2,a3,,am)

and by applying this repeatedly,

B(a0,a1,a2,,ak)B(hk1ak((h2a2(h1a1(a0)))),0k)
This leaves only the case B(n,0k), which we write as D(n,k). The machine then simulates the Collatz-like rules

D(n,3k)Halt(n+4k)D(n,3k+1)B(4,n+1,(0,2)k,1)D(h2k+1(h2k2(h2k22((h22(h0n+1(4)))))),2k+2)D(n,3k+2)B(7,0g(n)1,(2,0)k,2,1)D(hg(n)+2k(hg(n)+2k12(hg(n)+2k32((hg(n)+12(hg(n)12(7)))))),g(n)+2k+1)

where (x,y)k denotes k consecutive copies of x,y (2k total entries), g(n)=n+12, and Halt(x) means that the machine halts with x ones on the tape.

Trajectory

This machine reaches the configuration D(13,1) after 89 steps, and then follows this trajectory:

D(13,1)D(139,2)D(n0,71)D(n1,n02+47)D(n2,n0+983)D(n3,2n0+2089)D(n4,n32+4n0+40727)D(n5,n42+27n3+8n0+78781)D(n6,81n4+54n3+16n0+1898243)Halt(n6+324n4+216n3+64n0+7592243)

where n6n5fω(n4)fω2(n3)fω2(n2)fω2(n1)fω3(n0)fω3(h70(h69(h69(7))))>fω4(70).

The trajectory can be computed in the following way.
First, note that hk(n)n+1(mod2) can be proven by induction on k. Next, note that D(n,3k+2)D(n,k) where n is obtained by applying 2k+1 functions of the form hm to the input 7, so n7+2k+10(mod2), and D(2n,3k+1)D(n,k) where n is obtained by applying 2k+1+n+1 functions of the form hm to the input 4, so n4+2k+1+n+10(mod2). This means that after the first application of the D(n,3k+2) rule, n will always be even, and thus for n appearing after this point, we have g(n)=n+12=n2.
Now the only modular arithmetic left is finding the values of the first arguments of D modulo large powers of 3, so that we know the values of the second arguments of D modulo 3, and thus know which rules to apply. We have h1(n)=h0n(1)=1+3+3++3+3n=1+3n and h2(n)=h1n(1)=1+3(1+3((1+3(1))))n=1+3+32++3n1+3n=3n+112. Since the computation of hk(n) for any k>2 ends with something of the form h2(m), all first arguments of D starting from n0=h70(h69(h69(7))) are of the form 3m12 for large m, and thus are 3i12(mod3i) for i<h69(7) (note: This upper bound is much larger than what we need and significantly smaller than the exact maximum of i for which this statement holds).
With this, we can easily compute each second argument of D modulo 3 just from its expression as a linear combination (with relatively simple coefficients) of the previous first arguments of D, and thus we can compute the linear combination of first arguments that is equal to the second argument in the next step. Repeating this allows us to compute the whole trajectory.

Related machines

The analysis section applies to all machines obtained from this machine by varying the A0 transition and the starting state. If the search didn't miss any of these machines, this machine takes the longest to halt out of all machines in this family. This family is part of a larger family of machines obtained by additionally varying the C0 transition, but the Collatz-like rules depend on the C0 transition. Furthermore, we can change the order of the last 5 states to get 1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1LJ1LJ_0LK0LI_1LL1LK_1RF1LM_0LI1RZ (bbch), which also forms a family of similar size by varying the transitions A0,C0 and the starting state. Perhaps even more families can be obtained by changing the G0 transition from 1RB to 0RB, but these also differ in the fω part of their behavior, so they compute a different variant of the Fast-Growing Hierarchy (in particular, they simulate B(a0,0k,a1+1,a2,a3,,am)B(0k,a0+2,a1,a2,a3,,am)).

The second place so far (not counting machines that also reach D(13,1)) is taken by 1RL1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL (bbch), which reaches D(7,2) and halts with more than fω4(4) ones on the tape, so it's a close competition. The search of these families for higher scores is ongoing.