First page . . . Back to page 4 . . . Forward to page 6 . . . Last page (page 8)
Analysis of the Oct 2000 Marxen-Buntrock BB6 Record-Setter 'q'
This is a high-level description of an old BB(6) candidate champion, discovered in October 2000 and later surpassed on March 2001. It writes over 6×10462 ones before halting. For a more thorough and rigorous analysis read this page.
This machine operates on similar principles to the one just discussed, but instead of iterating a process of multiplying the number of 1's by 5/2, it iterates a process of raising 2 to the power of the number of 1's! Yes, that's right, iterated exponents. Combined with the modulo dependency mechanism (this time on a modulo-3 test rather than modulo-4) it's easy to see how it gets up to 10462 ones.
To analyze, we use the same method as before of finding a simple "canonical" state (like a run of 1's) and looking at what it produces when the number of 1's changes. In this case, the simplest such state is when the head is in state 2, positioned on a 0 cell, with N consecutive 1's just to the left of the head, and nothing else. Call such a state C(N).
Looking at the fates of the first few C(N)'s, we find:
C(0) becomes C(10) after 86 steps.
C(1) becomes C(24) after 408 steps.
C(2) halts after 8 steps, leaving 4 1's on the tape.
C(3) becomes C(28) after 544 steps.
C(4) becomes C(56) after 2098 steps.
C(5) halts after 11 steps, leaving 6 1's on the tape.
C(6) becomes C(64) after 2730 steps.
C(7) becomes C(120) after 9548 steps.
C(8) halts after 14 steps, leaving 8 1's on the tape.
C(9) becomes C(136) after 12260 steps.
C(10) becomes C(248) after 40806 steps.
C(11) halts after 17 steps, leaving 10 1's on the tape.
C(12) becomes C(280) after 52030 steps.
C(13) becomes C(504) after 168832 steps.
C(14) halts after 20 steps, leaving 12 1's on the tape.
C(15) becomes C(568) after 214488 steps.
It is clear right away that there is a modulo-3 effect going on. A general formula is only evident for the case of N=2 modulo 3:
C(3N+2) halts after 3N+8 steps, leaving (2(N+1)/3)+2 1's on the tape.
For the others, we have to consider another "canonical" state; this one is a bit more complex. It consists of bunch of groups of 1's separated by single 0's, with the head in state 2 and positioned just to the left of the leftmost 1. I will represent such a state as D(a,b,c,...) where the a, b, c etc. are numbers giving the number of 1's in each group. Each of the C(N)'s above (except the ones that halt) leads to one of these D(...) states, which then passes through one or more additional D(...) states and ultimately becomes another C() state. Here is the first D(...) state for each C() state:
C(0) becomes 111_1 which we call D(3,1)
C(1) becomes 111_1_1 which we call D(3,1,1)
C(3) becomes 1111_1_1 which we call D(4,1,1)
C(4) becomes 111_11_1_1 which we call D(3,2,1,1)
C(6) becomes D(4,2,1,1)
C(7) becomes D(3,2,2,1,1)
C(9) becomes D(4,2,2,1,1)
C(10) becomes D(3,2,2,2,1,1)
C(12) becomes D(4,2,2,2,1,1)
C(13) becomes D(3,2,2,2,2,1,1)
C(15) becomes D(4,2,2,2,2,1,1)
and in general:
C(3N) becomes D(4,X,1,1) where X is a string of N-1 2's in a row
C(3N+1) becomes D(3,X,1,1) where X is a string of N 2's in a row
Then we can look at each of the D's and see what happens:
D(3,1) becomes C(10)
D(3,1,1) becomes D(10,1)
D(10,1) becomes C(24)
D(4,1,1) becomes D(12,1)
D(12,1) becomes C(28)
D(3,2,1,1) becomes D(11,1,1)
D(11,1,1) becomes D(26,1)
D(26,1) becomes C(56)
D(4,2,1,1) becomes D(13,1,1)
D(13,1,1) becomes D(28,1)
D(28,1) becomes C(60)
The pattern that emerges is:
D(N,1) becomes C(2N+4)
D(N,1,1) becomes D(2N+4,1)
D(N,2,1,1) becomes D(2N+5,1,1)
and in general:
D(N,2,X) becomes D(2N+5,X)
where X is any sequence of groups.
So, to figure out how far this machine goes before halting, we have to find the first occurance of a C(N) state, then apply these rules to find each subsequent C(N) state until we get to one with N=2 modulo 3. Since the transition from each C(N) to the next higher C(N) involves approximately N/3 steps iterating 2N+4 or 2N+5 each step, it amounts to calculating (approximately) 2N/3 each time. If you count each C(N) as a "step", the machine only takes three "steps" to produce the huge number 6×10462.
C(1) occurs at step 1 of the machine's operation.
C(1) becomes D(3,1,1) which becomes C(24) at step 409.
C(24) = C(8×3), becomes D(4,2,2,2,2,2,2,2,1,1), which becomes C(4600).
C(4600) = C(1533×3+1), becomes D(3,X,1,1) where "X" is a string of 1533 2's in a row, which becomes C(B) where B is calculated by the following BASIC code:
B = 3 FOR X = 1 to 1533 B = 2 * B + 5 NEXT X B = 2 * B + 4 B = 2 * B + 4 PRINT 2 * (B+1) / 3 + 2or the following equivalent code for the bc tool in Unix:
b = 3 x = 1533 while (x > 0) { x = x - 1 b = 2 * b + 5 } b = 2 * b + 4 b = 2 * b + 4 2 * (b + 1) / 3 + 2The first few values of B are: 3, 11, 27, 59, 123, 251, ... It gets doubled another 1530 times, which produces a final value of B around 9×10462. As luck would have it, this value of B is equal to 2 modulo 3, so this C(N) is the last. The machine proceeds to cut the number of 1's by 2/3 and halt.
The final line of the sample-code prints the number of 1's that the machine will leave on the tape just before halting. That value is:
64274998051227535695469776160755043010989153278551705369591334375073\ 53044244808535117560064286256132435863376749034679434299778610119888\ 86658563463437539907054723557168433393272208554111381733247158811503\ 30341868202595889544122642918970323255986879066608417102461351403452\ 62280750979809098117770580762320987650584291257578514811285364167355\ 86688154556760240264990637942260439101648404017014632900048602801665\ 8647567729882589366735582198403287964952012694238177960References:
Heiner Marxen, table of record setters
Heiner Marxen, table of BB(6) candidates found by a search in 2000
Robert Munafo, Detailed Analysis of the Oct 2000 Marxen-Buntrock BB(6) Record-Setter 'q'.
First page . . . Back to page 4 . . . Forward to page 6 . . . Last page (page 8)
s.30