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 -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 would be applied once before halting, this machine applies repeatedly with Collatz-like rules, which allows it to halt with over ones on the tape.

Analysis

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

where denotes consecutive zeroes in the list, using configurations of the form .
This computes a slightly modified Fast-Growing Hierarchy. In particular, letting

one can prove by induction on that

for . This motivates the use of instead, so that

and by applying this repeatedly,


This leaves only the case , which we write as . The machine then simulates the Collatz-like rules

where denotes consecutive copies of ( total entries), , and means that the machine halts with ones on the tape.

Trajectory

This machine reaches the configuration after 89 steps, and then follows this trajectory:

where .

The trajectory can be computed in the following way.
First, note that can be proven by induction on . Next, note that where is obtained by applying functions of the form to the input 7, so , and where is obtained by applying functions of the form to the input 4, so . This means that after the first application of the rule, will always be even, and thus for appearing after this point, we have .
Now the only modular arithmetic left is finding the values of the first arguments of modulo large powers of 3, so that we know the values of the second arguments of modulo 3, and thus know which rules to apply. We have and . Since the computation of for any ends with something of the form , all first arguments of starting from are of the form for large , and thus are for (note: This upper bound is much larger than what we need and significantly smaller than the exact maximum of for which this statement holds).
With this, we can easily compute each second argument of modulo 3 just from its expression as a linear combination (with relatively simple coefficients) of the previous first arguments of , 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 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 transition, but the Collatz-like rules depend on the 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 and the starting state. Perhaps even more families can be obtained by changing the transition from 1RB to 0RB, but these also differ in the part of their behavior, so they compute a different variant of the Fast-Growing Hierarchy (in particular, they simulate ).

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