Detailed Analysis of the Oct 2000 Marxen-Buntrock BB₆ Record-Setter 'q'

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.

Notation and Definitions

This discussion concerns a 5-tuple, 6-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 6 pairs of 5-tuples (a pair for each state); each 5-tuple specifies a trigger value (state and tape symbol) 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 letters A through F, plus the special symbol h for the halted state.

The specific machine in question for this discussion, which will be called "machine q", is 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

right

left

right

left

right

left

halt

right

left

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:

step 1 B: 10

The B: represents 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):

step 2 C: 100
step 3 D: 1010
step 4 E: 1011
step 5 D: 1001
step 6 E: 1101

As we continue this discussion the step-number will often not be shown.

Long runs of repeating symbols will be represented by an exponential notation. For example, the machine state:

D: 1111111110

can be appreviated:

D: 1⁵11³0

Repeated patterns are abbreviated by enclosing the repeated form in parentheses, with an exponent. In this way, the machine state:

E: 011110110110110110101

could be abbreviated:

E: 0^⸂1^⸃4×^⸂011^⸃4×^⸂01^⸃2×

The above are partial-tape machine states; usually we'll just assume that the rest is all 0's — but it could be stated explicitly:

E: ...000 0^⸂1^⸃4×^⸂011^⸃4×^⸂01^⸃2× 000... or E: ^⸂0^⸃inf× 0 ^⸂1^⸃4×^⸂011^⸃4×^⸂01^⸃2×^⸂0^⸃inf×

Finally, variables and simple arithmetic expressions with variables can appear in repetition-counts. For example, if the tape has N 1's in a row (with N greater than 1), it might be shown like this:

B: ^⸂0^⸃inf×1̯^⸂1^⸃N-1×^⸂0^⸃inf×

Notice that the first 1 is displayed differently because it is under the head, then there are N-1 more, for a total of N 1's.

Canonical Machine-States

The machine state:

B: 1^X0

(with X greater than or equal to 0) will be called L(X).

The machine states:

B: 01^X01^Y
B: 01^X01^Y01^Z
(etc.)

(with X, Y, etc. greater than 0) will be called B(X,Y), B(X,Y,Z), and so on for B(...) states with greater numbers of terms.

The variable S inside a B(...) abbreviation will stand for any string of consecutive numbers separated by commas. For example, if B(X,Y,S) is being used as an abbreviation for B(X,Y,2,2,2,2,1,1), then B(Y,S) should be understood in that context to represent B(Y,2,2,2,2,1,1). Usually S will be unspecified and will simply mean any arbitrary non-null sequence.

Also, terms inside a B(...) abbreviation will sometimes be shown with exponents to represent multiple consecutive identical terms. For example, B(4,2,2,2,2,2,1,1) can be abbreviated B(4,2⁵,1,1). An exponent can be zero: B(4,2⁰,1,1) is the same as B(4,1,1).

Finally, any halted state that has the same tape pattern as a B(...) state, regardless of the actual head position, will be called an H(...) pattern using the same numbers/variables inside the parentheses. For example, a H(2,2,1,1) pattern is any halted state with 110110101 on the tape, with any number of additional 0's on either side but no other 1's, such as:

h: 110110101

or:

h: 011011010100

This is a Non-Formal Proof

In this analysis, the halting of machine q is proven, and the number of steps and number of 1's written are calculated, but without the full formality, precision and rigor of a true mathematical proof. Here's an example: in a formal proof, we would have to prove (or assume as an axiom) statements like the following:

if S₁, S₂ and S₃ are machine states,
and if S₁ becomes S₂ in X steps,
and if S₂ becomes S₃ in Y steps,
then S₁ becomes S₃ in X+Y steps.

(0)

Seems rather obvious, right? But you have to prove it, and many other similar statements that are even more seemingly trivial. Alternatively, you could rely on someone else's proofs, in which case you end up with a lot of precisely-defined jargon that would be difficult for most readers to understand, all explained only in obscure journals that probably aren't available at your library.

So, this analysis doesn't do that. It just shows what the machine does and how to calculate the important numbers. If you want to translate this into a real proof, be my guest! Just make sure to provide a reference back to this page so people can benefit from both types of explanation.

The First L(N) State

As shown in the first example above, machine q enters state L(1) after one step. Before looking at where it goes next, we'll define the behavior for all the cases L(N).

The Fate of L(N) for N=0 mod 3

Here are two hypothetical machine states (not necessarily part of the actual history of machine q) along with the results if executed for a few steps according to the rules of machine q. (Note: I used this perl program to run tests and produce all machine state listings in this analysis.)

step	L(3)	L(6)
	L(1×3)	L(2×3)
0	2: 1110	2: 1111110
1	3: 11100	3: 11111100
2	4: 111010	4: 111111010
3	5: 111011	5: 111111011
4	4: 111001	4: 111111001
.
5	5: 111101	5: 111111101
6	4: 110101	4: 111110101
7	6: 110101	6: 111110101
(8)		5: 111110101
(9)		4: 110110101
(10)		6: 110110101
.
N+5	5: 0110101	5: 0110110101
N+6	1: 01110101	1: 01110110101
N+7	2: 11110101	2: 11110110101
N+8	2: 11110101	2: 11110110101
N+9	2: 011110101	2: 011110110101
	B(4,1,1)	B(4,2,1,1)

Thus, L(3) becomes B(4,1,1) after 12 steps, and L(6) becomes B(4,2,1,1) after 15 steps. The first 4 steps are always going to be the same because all L(N) states have all 0's to the right. Then it does the central portion, which is moving to the left across a row of 1's. As long as N is greater than zero, and a multiple of 3, the central portion will be similar to the two examples shown here, just with more copies of the steps 5, 6 and 7. It has to be a multiple of 3 because of the way the state goes from 5 to 4 to 6 and then back to 5, and it has to land on a 0 in step 5 in order for the last 5 steps to agree with those shown here. Those last 5 will be the same every time, again because there are always 0's to the left of any L(N) pattern.

Thus it is shown that:

Rule 1

L(3+3X) becomes B(4,2^X,1,1) after 3X+12 steps,
for integer X and 3+3X > 0.

(1)

The Fate of L(N) for N=1 mod 3

This time we'll consider three states L(N) for positive integers N that are 1 more than a multiple of 3:

step	L(1)	L(4)	L(7)
	L(1 + 0×3)	L(1 + 1×3)	L(1 + 2×3)
0	2: 10	2: 11110	2: 11111110
1	3: 100	3: 111100	3: 111111100
2	4: 1010	4: 1111010	4: 1111111010
3	5: 1011	5: 1111011	5: 1111111011
4	4: 1001	4: 1111001	4: 1111111001
.
5	5: 1101	5: 1111101	5: 1111111101
(6)		4: 1110101	4: 1111110101
(7)		6: 1110101	6: 1111110101
(8)		5: 1110101	5: 1111110101
(9)			4: 1110110101
(10)			6: 1110110101
(11)			5: 1110110101
.
N+5	4: 00101	4: 00110101	4: 00110110101
N+6	5: 010101	5: 010110101	5: 010110110101
N+7	1: 0110101	1: 0110110101	1: 0110110110101
N+8	2: 1110101	2: 1110110101	2: 1110110110101
N+9	2: 1110101	2: 1110110101	2: 1110110110101
N+10	2: 01110101	2: 01110110101	2: 01110110110101
	B(3,1,1)	B(3,2,1,1)	B(3,2,2,1,1)

L(1) becomes B(3,1,1) after 11 steps, L(4) becomes B(3,2,1,1) after 14 steps, and L(7) becomes B(3,2,2,1,1) after 17 steps.

This is very similar to the previous example. The first 4 steps and the last 5 steps are just like the previous examples, and so is the central portion; the only difference is that the central portion includes an extra step in state E, immediately followed by an extra step in state D and then the E steps we saw before. So, as long as N-1 is a multiple of 3, the machine will behave in the manner shown here, and more precisely:

Rule 2

L(1+3X) becomes B(3,2^X,1,1) after 3X+11 steps,
for integer X and 1+3X > 0.

(2)

The Fate of L(N) for N=2 mod 3

Then we consider states L(N) where N is greater than 0 and is 2 more than a multiple of 3:

step	L(2)	L(5)	L(8)
	L(2 + 0×3)	L(2 + 1×3)	L(2 + 2×3)
0	2: 110	2: 111110	2: 111111110
1	3: 1100	3: 1111100	3: 1111111100
2	4: 11010	4: 11111010	4: 11111111010
3	5: 11011	5: 11111011	5: 11111111011
4	4: 11001	4: 11111001	4: 11111111001
.
5	5: 11101	5: 11111101	5: 11111111101
6	4: 10101	4: 11110101	4: 11111110101
(7)		6: 11110101	6: 11111110101
(8)		5: 11110101	5: 11111110101
(9)		4: 10110101	4: 11110110101
(10)			6: 11110110101
(11)			5: 11110110101
(12)			4: 10110110101
.
N+5	6: 010101	6: 010110101	6: 010110110101
N+6	h: 110101	h: 110110101	h: 110110110101
	H(2,1,1)	H(2,2,1,1)	H(2,2,2,1,1)

L(2) halts after 8 steps, leaving a (2,1,1) pattern for a total of 4 ones. L(5) halts after 11 steps, leaving a (2,2,1,1) pattern for a total of 6 ones. L(8) halts after 14 steps, leaving a (2,2,2,1,1) pattern for a total of 8 ones. The first 4 steps and the last 2 always amount to the same thing, and as long as N-2 is a multiple of 3, the central portion will be similar to the examples shown here. Thus it is shown that:

Rule 3

L(2+3X) halts after 8+3X steps, leaving a (2,2^X,1,1) pattern for a total of 4+2X ones,
for integer X and 2+3X > 0.

(3)

The First B(...) State

Now that we've defined all the L(N) cases, and knowing that machine q is in state L(1) at step 1, we can use rule (2) above to conclude that it will be in state B(3,1,1) after another 11 steps. In other words, at step 12 the machine is in this state:

12 2: 01110101

It now makes sense to look at the various B(...) cases.

The Case B(A)

This is by far the simplest case of the D's — a D state with just a single run of 1's. Unlike the C states, there is no dependency on modulo 3 or any other modulus. Here are the first three B(A) cases:

step	B(1)	B(2)	B(3)
0	2: 01	2: 011	2: 0111
1	3: 01	3: 011	3: 0111
2	1: 00	1: 001	1: 0011
3	2: 10	2: 101	2: 1011
(4)		3: 101	3: 1011
(5)		1: 100	1: 1001
(6)		2: 110	2: 1101
(7)			3: 1101
(8)			1: 1100
(9)			2: 1110
3A	L(1)	L(2)	L(3)

Look at the three steps in the B(1) column. It's in state B with the head on a 0 and a 1 to the right. In three steps, it reverses the 0 with the 1 and moves one to the right, ending up back in state B. If there is another 1 to the right of that (as is the case for B(2) and B(3)), it can take another three steps and do the same thing again. This works for any continuous length of 1's. Thus, it is clear that:

Rule 4

B(A) becomes L(A) after 3A steps, for any A > 0.

(4)

The Reducing B(1,B,...) Case

Next we consider B(...) cases with two or more numbers in the parentheses.

Since the B(...) states have the head at the left end of the symbols on the tape, it makes sense to look at different combinations of the values of the first two numbers, since these are the parts of the pattern that the machine will manipulate first. Also, it should be clear from the case B(A) just covered that the machine in any B(A,B,...) state will always start by proceeding across the initial run of A ones (and taking 3A steps in the process), then encounter the leftmost part of the B run, and what happens next should depend on B.

As it turns out (and this will be made clear by the following examples), in all cases the machine reverses direction on encountering the first one in the set of B and ends up in another B(...) state. This means that everything we discover for the cases B(A,B) will also apply to the cases B(A,B,S) for any S. This will be stated again as rule 7 after all the B(A,B) cases are shown.

We start with B(1,B). Here are the cases B(1,2) and B(1,3) as examples:

step	B(1,2)	B(1,3)
0	2: 010110	2: 0101110
1	3: 010110	3: 0101110
2	1: 000110	1: 0001110
3	2: 100110	2: 1001110
4	3: 100110	3: 1001110
5	4: 101110	4: 1011110
6	6: 101110	6: 1011110
7	5: 101110	5: 1011110
8	1: 111110	1: 1111110
9	2: 0011110	2: 00111110
10	3: 0011110	3: 00111110
11	4: 0111110	4: 01111110
12	6: 0111110	6: 01111110
13	5: 0111110	5: 01111110
14	1: 01111110	1: 011111110
15	2: 11111110	2: 111111110
16	2: 11111110	2: 111111110
17	2: 011111110	2: 0111111110
final state	B(7) = B(5+B)	B(8) = B(5+B)

As you can see, the two-term D state B(1,B) becomes a one-term state B(A) where A = 5+B, and it always takes 17 steps. Furthermore, the head never moves further right than the leftmost one in the B block, so this works for any value of B. (Remember, from the definition of B(...), B can be any integer greater than 0, but as we will have seen by the end of this discussion, the case B(1,1,...) never happens in the history of machine q). So, we have the rule:

Rule 5

B(1,B) becomes B(5+B) after 17 steps,
for any B greater than 1.

(5)

The Non-Reducing B(A,B,...) Case

Examples with B=3 and A=2,3,4 are shown here:

step	B(2,3)	B(3,3)	B(4,3)
0	2: 01101110	2: 011101110	2: 0111101110
.
1	3: 01101110	3: 011101110	3: 0111101110
2	1: 00101110	1: 001101110	1: 0011101110
3	2: 10101110	2: 101101110	2: 1011101110
4	3: 10101110	3: 101101110	3: 1011101110
5	1: 10001110	1: 100101110	1: 1001101110
6	2: 11001110	2: 110101110	2: 1101101110
(7)		3: 110101110	3: 1101101110
(8)		1: 110001110	1: 1100101110
(9)		2: 111001110	2: 1110101110
(10)			3: 1110101110
(11)			1: 1110001110
(12)			2: 1111001110
.
3A+1	3: 11001110	3: 111001110	3: 1111001110
3A+2	4: 11011110	4: 111011110	4: 1111011110
3A+3	6: 11011110	6: 111011110	6: 1111011110
3A+4	5: 11011110	5: 111011110	5: 1111011110
3A+5	1: 11111110	1: 111111110	1: 1111111110
3A+6	2: 10111110	2: 110111110	2: 1110111110
.

			3A+7 2: 1110111110
		3A+7 2: 110111110	3A+8 2: 1110111110
	3A+5+A 2: 010111110	3A+5+A 2: 0110111110	3A+5+A 2: 01110111110
final state 4A+5	B(1,5) = B(A-1,B+2)	B(2,5) = B(A-1,B+2)	B(3,5) = B(A-1,B+2)

This is the most complicated case we've seen so far, but it's not that hard. The machine in state B(A,B) takes 3A steps (just as in the B(A) case that produced rule 4) to move past the run of A ones. In the process it shifts that entire row of ones to the left by one space. Then it spends 6 steps adding two ones to the run of B and removing one from the run of A. Finally, it takes A-1 steps to move back across the run of A-1 ones that remain at the left end of the tape pattern. This leaves the tape in state B(A-1,B+2) after 4A+5 steps:

Rule 6

B(A,B) for A>1 becomes B(A-1,B+2) after 4A+5 steps.

(6)

Extension from B(A,B) to B(A,B,S)

You can now see from each of the B(...) examples above that the machine never gets past the first 1 in a group of 1's in any B(A,B) configuration until such time as that configuration is reduced to a single-run B(C) for some C that depends on A and B. This means that everything we have discovered so far about the state transitions and necessary number of steps can be extended to longer patterns B(A,B,S) where S (as defined above) stands for any string of additional numbers.

Rule 7

For any A>0 and B>1,
if B(A,B) becomes B(S₁) after X steps,
(where B(S₁) represents the result of either rule 5 or rule 6 above),
then B(A,B,S₂) becomes B(S₁,S₂) after X steps

(7)

Reduction of B(A,B,S) Through Iteration

In order to follow machine q through its entire history, we need a quicker way to reduce the B(A,B,...) states. So, the next step is to iterate the above non-reducing B(A,B,...) case, and combine it with the final reducing B(1,B,...) case to produce a formula that can reduce any B(A,B,S) to a form B(C,S) where C is some function of A and B. Since the existing rule 6 reduces the first term while increasing the second, until the first term is small enough to allow using rule 5, we can get an idea for what the iterated formula might be by comparing some different small values of A:

B(1,B,S) becomes B(B+(2)+3,S) after 17 steps.	(by rule 5)
.
B(2,B,S) becomes B(1,B+(2),S) after (4×2+5) steps.	(by rule 6)
. . . which becomes B(B+(2+2)+3,S) after 4×2+5+17 steps.	(by rule 5)
.
B(3,B,S) becomes B((3-1),B+(2),S) after (4×3+5) steps.	(by rule 6)
. . . which becomes B((3-2),B+(2+2),S) after (4×3+5) + (4×2+5) steps.	(by rule 6)
. . . which becomes B(B+(2+2+2)+3,S) after (4×3+5) + (4×2+5)+ (4×1+5) + 8 steps.	(by rule 5)

Note that for X>0, 1+2+3+...+X = X (X+1)/2. So, the terms involving "4" in the number of steps expressions can be combined, and it would appear that:

B(A,B,S) becomes B(2A+B+3,S) after 4 (A (A+1)/2) + 5 A + 8 steps.

Reducing the second expression thus:

4 (A (A-1)/2) + 5 A + 8	= 2 A (A+1) + 5 A + 8
	= 2 A² + 2 A + 5 A + 8
	= 2 A² + 7 A + 8

gives us our hypothetical rule 8:

B(A,B,S) becomes B(2A+B+3,S) after 2 A² + 7 A + 8 steps.

(hyp. 8)

which we will now show by mathematical induction over A:

To prove:

B(A,B,S) becomes B(2A+B+3,S) after 2 A² + 7 A + 8 steps.

Step 1. The statement is true when A is 1: B(A,B,S) becomes B(2A+B+3,S) after 2A² + 7A + 8 steps, if A = 1.

Proof: With A = 1, 2 A + B + 3 is B + 5, and 2 A² + 7 A + 8 = 2 + 7 + 8 = 17. By rule 5, B(1,B,S) becomes B(B+5,S) after 17 steps. Since the formulas agree, this case is verified.

Step 2. When A is greater than or equal to 1, show that:

		if for all B>0, B(A,B,S) becomes B(2A+B+3,S) after 2 A² + 7 A + 8 steps,	(h1)
		then it follows that for all B>0, B(A+1,B,S) becomes B(2(A+1)+B+3,S) after 2 (A+1)² + 7 (A+1) + 8 steps.	(h2)

For this step, we are temporarily assuming the first part (the if part) is true (review "proof by mathematical induction" if you're getting lost at this point).

Applying rule 6 to the left part of (h2), we get:

B(A+1,B,S) becomes B(A+1-1,B+2,S) after 4(A+1)+5 steps.

(h3)

using our temporary assumption (h1), and substituting B+2 for B (since the assumption is true for all B>0) it would then follow that:

B(A+1-1,B+2,S) becomes B(2A+B+2+3,S) after another 2 A² + 7 A + 8 steps.

(h4)

Thus (by [rule 0#rule0] if it isn't directly obvious) it would follow that:

B(A+1,B,S) becomes B(2A+B+2+3,S) after 4(A+1)+5 + 2 A² + 7 A + 8 steps.

(h5)

If (h5) agrees with (h2), then we've proven the validity of the combined assertion "if (h1) then (h2)".

The first part checks out, since:

2A + B + 2 + 3 = 2(A+1) + B + 3.

And the second part checks out, since:

4(A+1)+5 + 2 A² + 7 A + 8	= 4A + 4 + 5 + 2 A² + 7 A + 8
	= 2 A² + 4A + 2 + 2 + 5 + 7 A + 8
	= (2 A² + 4A + 2) + (7 + 7 A) + 8
	= 2 (A² + 2A + 1) + 7(1 + A) + 8
	= 2 (A+1)² + 7(A+1) + 8

Thus (h5) agrees with (h2) and step 2 is proven: we have demonstrated that the formula (hyp. 8) is valid for A+1 whenever it is valid for A.

Step 3. By mathematical induction, the assertion (hyp. 8) holds for all A greater than or equal to 1.

Q. E. D.

We now have Rule 8:

B(A,B,S) becomes B(2A+B+3,S) after 2 A² + 7 A + 8 steps,
for all A>0 and B>1.

(8)

Rule 9

As it turns out, it will also be useful later to have this corollary, which follows directly from the case of B=2:

B(A,2,S) becomes B(2A+5,S) after 2 A² + 7 A + 8 steps,
for all A>0.

(9)

The Next Few States of the Machine

At this point it makes sense to carry the machine a bit further. We have already established that it reaches B(3,1,1) by step 12. Now:

By rule 8, it arrives at state B(6+1+3,1) after another 2×3²+7×3+8 steps, which is B(10,1) at step 59:

59 2: 0111111111101

By rule 8 again, it then proceeds to state B(20+1+3) after another 2×10²+7×10+8 steps, which is B(24) at step 337:

337 2: 0111111111111111111111111

Then by rule 4 it then proceeds to state L(24) after another 3×24 steps:

409 2: 1111111111111111111111110

Iterating to the Third L(N) State

We've made it back to a L(N) state — our second (the first was L(1) at step 1, remember?)

What happens next (whether to apply rule 1, rule 2 or rule 3) depends on N modulo 3. In this case N is 24, and 24 is 0 modulo 3, so we apply rule 1. To apply rule 1 we express 24 in the form 3+3X, giving X=7, so the machine proceeds to state B(4,2⁷,1,1) after 3×7+12 steps, which is state B(4,2,2,2,2,2,2,2,1,1) at step 442:

442 2: 011110110110110110110110110101 = 01⁴(011)⁷(01)²

What follows next is a process of iterated application of rule 8 and rule 9 formulas:

B(4,2,2⁶,1,1) becomes B(8+2+3,2⁶,1,1) after 2×16+7×4+8 steps, which is
B(13,2,2⁵,1,1) at step 510.

B(13,2,2⁵,1,1) becomes B(2×13+2+3,2⁵,1,1) after 2×13²+7×13+8 steps, which is
B(31,2,2⁴,1,1) at step 947.

B(31,2,2⁴,1,1) becomes B(2×31+2+3,2⁴,1,1) after 2×31²+7×31+8 steps, which is
B(67,2,2³,1,1) at step 3094.

B(67,2,2³,1,1) becomes B(2×67+2+3,2³,1,1) after 2×67²+7×67+8 steps, which is
B(139,2,2²,1,1) at step 12549.

B(139,2,2²,1,1) becomes B(2×139+2+3,2²,1,1) after 2×139²+7×139+8 steps, which is
B(283,2,2,1,1) at step 52172.

B(283,2,2,1,1) becomes B(2×283+2+3,2,1,1) after 2×283²+7×283+8 steps, which is
B(571,2,1,1) at step 214339.

B(571,2,1,1) becomes B(2×571+2+3,1,1) after 2×571²+7×571+8 steps, which is
B(1147,1,1) at step 870426.

B(1147,1,1) becomes B(2×1147+1+3,1) after 2×1147²+7×1147+8 steps, which is
B(2298,1) at step 3509681.

B(2298,1) becomes B(2×2298+1+3) after 2×2298²+7×2298+8 steps, which is
B(4600) at step 14087383.

and then, by rule 4:

B(4600) becomes L(4600) after another 3×4600 steps, at step 14101183.

Iterating to the Fourth L(N) State

What happens next depends, as before, on 4600 mod 3, which is 1 — so this time we get to apply rule 2. Expressing 4600 as 1+3X makes X=1533 so we have

L(4600) becomes B(3,2¹⁵³³,1,1) after another 3×1533+11 steps, at step 14105793.

Now what? One thing's for sure, I'm not going to fill this web page with another 1535 lines showing the gradual reduction of B(3,2¹⁵³³,1,1) one term at a time until we get to the next L(N).

Perhaps we could derive a general formula for B(A,2^X,1,1) using induction as above — but this does not look too promising. The calculation of the A's is actually pretty easy. Here's the start of it:

step	A
0	A
1	2A+5 = 2¹ A + (2¹-1)×5
2	2(2A+5)+5 = 4A+15 = 2² A + (2²-1)×5
3	2(4A+15)+5 = 8A+35 = 2³ A + (2³-1)×5

The general formula, once the last two steps with B=1 are taken care of, is:

L(1+3X) becomes L(8×(2^X+2 - 1)) after ??? steps

The problem is with the calculation of the number of steps. It would need to come from an iteration of 2 A² + 7 A + 8, and the result gets rapidly hopeless — a polynomial with twice as many terms at each iteration, and no general form. Since calculating the number of steps and comparing to the original Marxen and Buntrock results is an essential part of verifying that the analysis is correct, I cannot simply skip over this calculation.

Also notice that with 1535 steps, doubling each time, we're going get into a really large number of digits. I did the above steps by hand, typing in the numbers and cutting and pasting the answers. This next L(N) demands a more automated approach, including a way to calculate numbers with hundreds of digits.

The Program

To overcome any possible errors in the above steps, and to accomplish the calculation of the fourth L(N) state, I wrote a program. It uses the arbitrary-precision calculator bc to emulate the q machine from its initial state all the way to halting.

The bc tool is available on most UNIX and Linux systems, and on MacOS in the Terminal. Here is the program:

define nextc(n) { # Starting with a L(N). Find out N mod 3 m = n % 3 if (m == 0) { # Apply rule 1 x = (n-3) / 3 a = 4 steps += (3*x) + 12 } else if (m == 1) { # Apply rule 2 x = (n-1) / 3 a = 3 steps += (3*x) + 11 } else { # Apply rule 3 (and halt) x = (n-2) / 3 a = 2 + (2*x) + 2 steps += (3*x) + 8 print "wrote\n\n", a, "\n\nones and halted after\n\n", steps, "\n\nsteps\n" return(0) } # Now (unless we halted) we have B(a,2^x,1,1). We have to reduce # this one term at a time by rules 8 and 9 # First get rid of all the 2's (rule 9) while(x>0) { x = x - 1 # Apply rule 8 b = 2*a + 2 + 3 steps += (2*a*a)+(7*a)+8 a = b } # Apply two more steps of rule 8 to get from B(a,1,1) to B(N) b = 2*a + 1 + 3 steps += (2*a*a)+(7*a)+8 a = b b = 2*a + 1 + 3 steps += (2*a*a)+(7*a)+8 a = b # go from B(N) to C(N) by rule 4 steps += 3*a # Return our new C(N) value return(a) } steps = 1 # 1 step to get to C(1) nextc(1) # calculate and print 24 nextc(.) # calculate and print 4600 nextc(.) # calculate and print the monster C(N) nextc(.) # this time it halts

If you are running Linux or MacOS, you can probably just select this program text and paste it into a window running bc. You'll get this output:

steps = 1 # 1 step to get to C(1) nextc(1) # calculate and print 24 24 nextc(.) # calculate and print 4600 4600 nextc(.) # calculate and print the monster C(N) 96412497076841303543204664241132564516483729917827558054387001562610\ 29566367212802676340096429384198653795065123552019151449667915179833\ 29987845195156309860582085335752650089908312831167072599870738217254\ 95512802303893834316183964378455484883980318599912625653692027105178\ 93421126469713647176655871143481481475876436886367772216928046251033\ 80032231835140360397485956913390658652472606025521949350072904202498\ 7971351594823884050103373297604931947428019041357266936 nextc(.) # this time it halts wrote 64274998051227535695469776160755043010989153278551705369591334375073\ 53044244808535117560064286256132435863376749034679434299778610119888\ 86658563463437539907054723557168433393272208554111381733247158811503\ 30341868202595889544122642918970323255986879066608417102461351403452\ 62280750979809098117770580762320987650584291257578514811285364167355\ 86688154556760240264990637942260439101648404017014632900048602801665\ 8647567729882589366735582198403287964952012694238177960 ones and halted after 61969130617279552670501360355248793287327735214537549191055852291063\ 50646396917574119825114168659634401414568271979218606923231567509383\ 59644041138366616789443425241568686986543365317438832173568026108352\ 75112665543783259093590451498416899940069571118519560309810878855927\ 74135187282111540065396884400545421966126420857370470726807018839317\ 54693065873967802692534965807954900011107885732115305618405501219642\ 26728857241663093342609533141900998046213816438484306270817017360536\ 82110717167957182284513500453219230981744907711440646999487680967635\ 17254316940225473934200517589328420136536089028278167049716739728351\ 53235718518861299352034588843419386337260004783558196143727964210676\ 95603413994052957132810134878540458242145066355633142069434590768582\ 09828255657357644746932064567059089677898385919381664736771065192258\ 40131946676547993275187162640707027514176923887087198763458715992600\ 276829587319770232224396046057929934270855 steps 0

Conclusion

The behavior of machine q discovered by Marxen and Buntrock in October 2000 and first published here, is hereby confirmed.

- Robert Munafo, 2000 November 30

Back to Busy Beaver discussion.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Aug 15.

s.27

Detailed Analysis of the Oct 2000 Marxen-Buntrock BB6 Record-Setter 'q'

Detailed Analysis of the Oct 2000 Marxen-Buntrock BB₆ Record-Setter 'q'