Detailed Analysis of the 1997 MarxenBuntrock BB_{6} RecordSetter
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 BB_{6} >= 95,524,079. It is a 6state candidate discovered by Marxen and Buntrock in 1997.
Notation and Definitions
This discussion concerns a 5tuple, Nstate 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 5tuples; each 5tuple 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 6state (N=6) machine given by the following twelve 5tuples:
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 lowprobability, 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 bruteforce iteration is not going to work as the simulator would need to iterate over 8×10^{15} 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 stepnumber 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 N_{i} to N_{i+1}, it will take some number of steps, and the value of N_{i+1} will depend in some way on N_{i}. To determine precise formulas for this, we can try a lot of small values of N_{i} and note the resulting values of N_{i+1} and the number of steps taken:

There is a clear pattern that repeats every 4 rows, so the number of steps and the N_{i+1} or Σ values both depend on N_{i} 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 N_{i} 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 N_{i} are increasing 4 at a time, we need to take this 40 and divide by 4^{2}×2! to get the coefficient of N_{i}^{2} for the general formula, which tuens out to be 5/4. Subtracting 5N_{i}^{2}/4 from each value in the 2^{nd} row gives the remainders in the last row, which is then easily seen to be 9N_{i}+7:

and so the total number of steps is (5N_{i}^{2}+36N_{i}+28)/4. A similar technique shows that for N_{i}=7, 11, 15, 19 the number of steps is (5N_{i}^{2}+26N_{i}+36)/4; and for N_{i}=4, 8, 12, 16, 20 the number of steps is (5N_{i}^{2}+28N_{i}+12)/4. It's also to see that in the halting cases the halt happens after (N_{i}+3)/2 steps and leaves Σ=(N_{i}+5)/2 1's on the tape.
So, the value of N_{i+1} depends on the value of N_{i} modulo 4 (the remainder of N_{i} when divided by 4). But the value of N_{i+1} modulo 4 is not the same as N_{i} modulo 4. Though it starts at a nonhalting value (N_{0} = 3, which is 3 modulo 4), it might eventually lead to an N_{i} 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 mod4 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 N_{i} ones. In addition we specify that the head is on the 2^{nd} 1 from the left. This condition occurs at steps 4, 37, 259, and several more times as listed below.
After it reaches the righthand 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 N_{i} modulo 4. Here is what the tape will end up looking like for each of the 4 possibilities:
N_{i} = 0 mod 4 (4, 8, 12, etc.): 1(10)^{M}11
N_{i} = 1 mod 4 (5, 9, 13, etc.): Halts with 1(10)^{M}11 on the tape
N_{i} = 2 mod 4 (6, 10, 14, etc.): 111(10)^{M}11
N_{i} = 3 mod 4 (7, 11, 15, etc.): 111(10)^{M}11
(Where M is equal to N_{i}/2, rounded down.)
As you can see, only values of N_{i} 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×N_{i}^{2}/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 N_{i} for this new, longer string of 1's is different for each of the three nonhalting cases.
We can collect together the formulas we have worked out above with this table:

Starting with the initial N_{i} value, which we will call N_{0}=3, we can use this table to work out all the N_{i} 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 N_{i} 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 mod4 value and the value of M. Notice in particular the fairly erratic pattern of mod4 values.
Starting with the initial N_{i} value, which we will call N_{0}=3, we can use this table to work out all the N_{i} 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 N_{i} 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 mod4 value and the value of M. Notice in particular the fairly erratic pattern of mod4 values.
i  N_{i}  N_{i} mod 4  steps  N_{i+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 recordholder 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 RecordSetter
Notice that the formula for N_{i+1} involves a division by 2, and adds either 3 or 5. Because of the division by 2, N_{i+1} modulo 4 depends on N_{i} modulo 8:
N_{i} = 0 mod 8: N_{i+1} = 3 mod 4
N_{i} = 1 mod 8: (machine will have halted)
N_{i} = 2 mod 8: N_{i+1} = 2 mod 4
N_{i} = 3 mod 8: N_{i+1} = 2 mod 4
N_{i} = 4 mod 8: N_{i+1} = 1 mod 4
N_{i} = 5 mod 8: (machine will have halted)
N_{i} = 6 mod 8: N_{i+1} = 0 mod 4
N_{i} = 7 mod 8: N_{i+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(m_{i}^{.}x / d) + X_{i}, where d=4, i such that x = i mod d, m_{i} = {10,0,10,10}, X_{i} = {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