Detailed Analysis of the 1997 Marxen-Buntrock BB6 Record-Setter
This page gives a more complete analysis (almost a proof, but without the precise language) of the behavior of the Busy Beaver candidate described here. Found in 1997, is set a record for BB6 >= 95,524,079. It is a 6-state candidate discovered by Marxen and Buntrock in 1997.
Notation and Definitions
This discussion concerns a 5-tuple, N-state Turing Machine with an initially blank tape that is infinite in both directions and has a single mark value (i.e. each cell on the tape may be a blank '0' or marked '1'). The machine's behaviour is specified by a list of (at most) 2N 5-tuples; each 5-tuple specifies a trigger value (state and head value) and the response (new state, what to write and which way to move). The machine always both writes and moves at each step. The states are given by numbers 1 through N, plus the special symbol h for the halted state.
The specific machine in question for this discussion is a 6-state (N=6) machine given by the following twelve 5-tuples:
| if in state | reading | go to state | and write | and move | if in state | reading | go to state | and write | and move | |||
| A | 0 | B | 1 | right | A | 1 | 2 | 1 | right | |||
| B | 0 | C | 1 | left | B | 1 | 2 | 1 | left | |||
| C | 0 | F | 0 | right | D | 1 | 1 | 1 | left | |||
| D | 0 | A | 1 | right | E | 1 | 6 | 0 | left | |||
| E | 0 | halt | 1 | left | F | 1 | 4 | 1 | left | |||
| F | 0 | A | 0 | left | C | 1 | 5 | 0 | left |
Analysis
The machine's operation lends itself easily to analysis, which reveals a beautiful combination of a few simple processes that interact in just the right way. The machine implements an iterated function that grows at an exponential rate and uses a test condition based on a low-probability, deterministic, and statistically random condition to determine when to stop growing. As a result, it grows to a very large size, so large that it takes a really sophisticated Turing machine simulator to show that it halts — direct brute-force iteration is not going to work as the simulator would need to iterate over 8×1015 steps.
The machine starts in state A, and the tape is all 0's. So, after the first step it has written a 1, gone to state B and moved 1 to the right. I will use the following format to show the machine state and tape:
1 B: 10
The italic 1 indictes that the machine has completed one step. Then there is a B representing the machine's state, then the tape symbols (a 1 and a 0) with the head on the 0 (shown by boldface). The 1 was just written, the 0 under the head is a tape cell that has not yet been written; it is a 0 because the whole tape is initially 0's (i.e. "blank"). Here are the next few steps (you can verify them from the table above if you want):
2 C: 11
3 D: 011
4 E: 111
5 D: 111
6 E: 1110
As we continue this discussion the step-number will often not be shown.
To analyze, we start by finding an example of a simple state that the machine enters over and over again. I call such a state "canonical" because it has a simple pattern and recurs multiple times during the machine's history.
Further simulation past these first few steps shows that it repeatedly creates a single row of 1's with no 0's (first seen in step 4 above), each time expanding it to a row of 1's about 2.5 times longer. The time taken to do this, and the resulting length of the next row of 1's, depends on the length of the previous row of 1's.
Each time it increases the length of the row of 1's, say from Ni to Ni+1, it will take some number of steps, and the value of Ni+1 will depend in some way on Ni. To determine precise formulas for this, we can try a lot of small values of Ni and note the resulting values of Ni+1 and the number of steps taken:
|
There is a clear pattern that repeats every 4 rows, so the number of steps and the Ni+1 or Σ values both depend on Ni modulo 4. For the latter, it's easy to see the formula is linear. For the number of steps column, it's not linear but one can use the method of finite differences to look for a polynomial function. For example, for the values of Ni that are 2 more than a multiple of 4, we have the values 106, 222, 378, 574; taking differences twice we get a row of the constant 40. Because the Ni are increasing 4 at a time, we need to take this 40 and divide by 42×2! to get the coefficient of Ni2 for the general formula, which tuens out to be 5/4. Subtracting 5Ni2/4 from each value in the 2nd row gives the remainders in the last row, which is then easily seen to be 9Ni+7:
|
and so the total number of steps is (5Ni2+36Ni+28)/4. A similar technique shows that for Ni=7, 11, 15, 19 the number of steps is (5Ni2+26Ni+36)/4; and for Ni=4, 8, 12, 16, 20 the number of steps is (5Ni2+28Ni+12)/4. It's also to see that in the halting cases the halt happens after (Ni+3)/2 steps and leaves Σ=(Ni+5)/2 1's on the tape.
So, the value of Ni+1 depends on the value of Ni modulo 4 (the remainder of Ni when divided by 4). But the value of Ni+1 modulo 4 is not the same as Ni modulo 4. Though it starts at a non-halting value (N0 = 3, which is 3 modulo 4), it might eventually lead to an Ni that is 1 modulo 4. This allows the row of 1's to multiply by 2.5× several times before the machine halts. Furthermore, the process of performing the mod-4 test is combined with the process of performing the division by 2 (which is then followed by a multiplication by 5). This combination of functions — accomplishing two things simultaneously with the same code — is part of what makes this much complexity possible in a Turing machine with only 6 states.
As already discussed, we have chosen a "canonical state" for this machine that is a single continuous set of Ni ones. In addition we specify that the head is on the 2nd 1 from the left. This condition occurs at steps 4, 37, 259, and several more times as listed below.
After it reaches the right-hand end of the row of 1's, it adds two more 1's to the right and reverses direction, then plows through the rest of the 1's changing them into a "...101010..." pattern (this is easy to see in the machine's state table: it cycles through states A,B,C,D, each time moving to the left and writing alternating 1 and 0). When the head reaches the left end, what happens next depends on the value of Ni modulo 4. Here is what the tape will end up looking like for each of the 4 possibilities:
Ni = 0 mod 4 (4, 8, 12, etc.): 1(10)M11
Ni = 1 mod 4 (5, 9, 13, etc.): Halts with 1(10)M11 on the tape
Ni = 2 mod 4 (6, 10, 14, etc.): 111(10)M11
Ni = 3 mod 4 (7, 11, 15, etc.): 111(10)M11
(Where M is equal to Ni/2, rounded down.)
As you can see, only values of Ni that are 1 more than a multiple of 4 will result in a halt. In the remaining cases the machine begins a process that takes about 5×Ni2/4 steps, during which it repeatedly shuttles back and forth turning each copy of '10' into '11' and then appending a '111' to the left, thereby adding a total of 3M 1's to the left. When this is done the tape is once again a single solid row of 1's, with the machine in state A. The new value of Ni for this new, longer string of 1's is different for each of the three non-halting cases.
We can collect together the formulas we have worked out above with this table:
|
Starting with the initial Ni value, which we will call N0=3, we can use this table to work out all the Ni values and the number of steps taken to get to each one. For the first 14 cases the step number was also found by simulation confirming that a row of Ni 1's is first seen at the times indicated here. (The precise number of steps is not important for answering the halting question or finding the Σ() value, but it is needed for getting the S() value). Also given are the mod-4 value and the value of M. Notice in particular the fairly erratic pattern of mod-4 values.
Starting with the initial Ni value, which we will call N0=3, we can use this table to work out all the Ni values and the number of steps taken to get to each one. For the first 14 cases the step number was also found by simulation confirming that a row of Ni 1's is first seen at the times indicated here. (The precise number of steps is not important for answering the halting question or finding the Σ() value, but it is needed for getting the S() value). Also given are the mod-4 value and the value of M. Notice in particular the fairly erratic pattern of mod-4 values.
| i | Ni | Ni mod 4 | steps | Ni+1 |
| 0 | 3 | 3 | 33 | 10 |
| 1 | 10 | 2 | 222 | 30 |
| 2 | 30 | 2 | 1402 | 80 |
| 3 | 80 | 0 | 8563 | 203 |
| 4 | 203 | 3 | 52833 | 510 |
| 5 | 510 | 2 | 329722 | 1280 |
| 6 | 1280 | 0 | 2056963 | 3203 |
| 7 | 3203 | 3 | 12844833 | 8010 |
| 9 | 8010 | 2 | 80272222 | 20030 |
| 10 | 20030 | 2 | 501681402 | 50080 |
| 11 | 50080 | 0 | 3135358563 | 125203 |
| 12 | 125203 | 3 | 19595552833 | 313010 |
| 13 | 313010 | 2 | 122471892222 | 782530 |
| 14 | 782530 | 2 | 765448543902 | 1956330 |
| 15 | 1956330 | 2 | 4784051443102 | 4890830 |
| 16 | 4890830 | 2 | 29900316628602 | 12227080 |
| 17 | 12227080 | 0 | 186876942247563 | 30567703 |
| 18 | 30567703 | 3 | 1167980782060333 | 76419260 |
| 19 | 76419260 | 0 | 7299879658619323 | 191048153 |
| 20 | 191048153 | 1 | 382096309 | halts, Σ=95524079 |
| total steps | 8690333381690951 |
It might seem a little disappointing to some readers to note that this machine, which for some time was the record-holder for the number of 1's produced, actually produces as many as twice that record, only to cut the number almost in half just before halting.
What Makes This a Record-Setter
Notice that the formula for Ni+1 involves a division by 2, and adds either 3 or 5. Because of the division by 2, Ni+1 modulo 4 depends on Ni modulo 8:
Ni = 0 mod 8: Ni+1 = 3 mod 4
Ni = 1 mod 8: (machine will have halted)
Ni = 2 mod 8: Ni+1 = 2 mod 4
Ni = 3 mod 8: Ni+1 = 2 mod 4
Ni = 4 mod 8: Ni+1 = 1 mod 4
Ni = 5 mod 8: (machine will have halted)
Ni = 6 mod 8: Ni+1 = 0 mod 4
Ni = 7 mod 8: Ni+1 = 0 mod 4
As you can see, out of the 6 possible cases, only one of them leads to an N=1 mod 4 value (the 'halting' value) for the new N. This is an example of a generalized Collatz mapping, described here. (The parameters are: #T(x) = floor(mi.x / d) + Xi, where d=4, i such that x = i mod d, mi = {10,0,10,10}, Xi = {3,1,5,3}#, and initial value x=3).
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Aug 14.
s.27