BB(6, 2) > 10^78913

In late April, I restarted a search through the 6-state, 2-symbol Busy Beaver domain. Compared to the Beeping Busy Beaver and other newer variations, this is well trodden ground. So, I was not expecting to immediately find any new results. Instead I was in search of some more tricky to find machines, such as the Mother of Giants I recently discovered in the Beeping Busy Beaver competition.

Last week, I flew out to California for my brother’s wedding. In between festivities, I took a peek at the search results and was surprised to find what appeared to be a new BB(6, 2) champion which runs for \(> 9 \times 10^{78913}\) steps and leaves \(> 6 \times 10^{39456}\) non-blank symbols upon halting. If this analysis is accurate, that would be over twice as many digits (for both metrics) as Pavel Kropitz’s current reigning champion, announced almost 12 years ago.

This BB(6, 2) enumeration has required about 35,000 CPU-hours of computation so far and was run in parallel on the spare cycles of a 40-node (500 core) compute cluster over the course of a couple weeks using my father and my Python and C++ busy-beaver codebase.

The Machine

1RB1RC_1LC0RF_1RA0LD_0LC0LE_1LD0RA_1RE1RZ

	0	1
A	1RB	1RC
B	1LC	0RF
C	1RA	0LD
D	0LC	0LE
E	1LD	0RA
F	1RE	1RZ

This TM runs for over \(9 \times 10^{78913}\) steps before halting in the configuration:

0^∞ 1010^N 11101 Z> 1 0^∞

where \(N = \frac{3}{4} \cdot 2^{2^{17}} - 2\)

This machine can be analyzed in a similar way to the BBB(3, 3) champion

Common Configuration

This analysis will be built around a common configuration:

C(a, b, c, d) = 0^∞ 1 <E 0101^a 1^b 0^c 1^d 0^∞

which appears again and again as this TM runs.

Level 1

If you simulate this TM using tape compression and chain steps you will probably start noticing the following pattern repeat over and over again:

Step #	Left tape	State	Right tape
0	001	<E	0101^a 11 …
1	000	A>	0101^a 11 …
4a+ 1	000 1010^a	A>	11 …
4a+ 2	000 1010^a 1	C>	1 …
4a+ 3	000 1010^a 1	<D	0 …
4a+ 4	000 1010^a	<E	00 …
8a+ 4	000	<E	0101^a 00 …
8a+ 5	00	<D	1 0101^a 00 …
8a+ 6	0	<C	01 0101^a 00 …
8a+ 7	1	A>	0101^a 01 00 …
12a+ 7	1 1010^a	A>	01 00 …
12a+ 8	1 1010^a 1	B>	100 …
12a+ 9	1 1010^a 10	F>	00 …
12a+10	1 1010^a 101	E>	0 …
12a+11	1 1010^a 101	<D	1 …
12a+12	1 1010^a 10	<E	01 …
16a+14	1	<E	0101^a 0101 …

This is our first rule:

Rule 1: C(a, b+2, c, d) -> C(a+1, b, c, d) in \(16a + 14\) steps.

Repeated Application

Now, we can keep repeating this rule over and over again as long as we still have \(b >= 2\).

Rule 1x: C(a, 2k + r, c, d) -> C(a + k, r, c, d) in steps:

\[\sum_{i=0}^{k-1}(16 a_i + 14) = \sum_{i=0}^{k-1}(16 (i + k) + 14) = 8 k^2 + (16a + 6) k\]

See my recursive relations post for an explanation of how to evaluate the number of steps.

Level 2

First a small helper rule will turn out to be useful:

Rule 2: 01 <E 00 -> <E 00 11 in 10 steps
Rule 2x: 01ⁿ <E 00 -> <E 00 11ⁿ in \(10n\) steps

Step #	Left tape	State	Right tape
0	0001	<E	0101^a 1000
1	0000	A>	0101^a 1000
4a+ 1	0000 1010^a	A>	1000
4a+ 2	0000 1010^a 1	C>	000
4a+ 3	0000 1010^a 11	A>	00
4a+ 4	0000 1010^a 111	B>	0
4a+ 5	0000 1010^a 111	<C	1
4a+ 6	0000 1010^a 11	<D	01
4a+ 7	000 01^2a+1	<E	00 1
24a+17	000	<E	00 11^2a+1 1
24a+18	00	<D	100 1^4a+3
24a+19	0	<C	0100 1^4a+3
24a+20	1	A>	0100 1^4a+3
24a+21	11	B>	100 1^4a+3
24a+22	110	F>	00 1^4a+3
24a+23	1101	E>	0 1^4a+3
24a+24	1101	<D	1 1^4a+3
24a+25	110	<E	01 1^4a+3
24a+26	11	<D	101 1^4a+3
24a+27	1	<E	0101 1^4a+3

Rule 3: C(a, 1, c+3, d) -> C(1, 4a+3, c, d) in \(24a + 27\) steps

Then applying Rule 1x we get:

Rule 4: C(a, 1, c+3, d) -> C(2a+2, 1, c, d) in steps:

\[8 (2a + 1)^2 + (16 + 6) (2a + 1) + (24a + 27) = 32 a^2 + 100 a + 57\]

Repeated Application

Since Rule 4 has the same start and end configuration, it can be applied repeatedly as long as \(c \ge 3\).

Rule 4x: C(a, 1, 3k+r, d) -> C((a + 2) 2^k - 2, 1, r, d) in steps:

\[\begin{array}{rcl} \sum_{i=0}^{k-1}(32 a_i^2 + 100 a_i + 57) &=& \sum_{i=0}^{k-1}(32 ((a + 2) 2^i - 2)^2 + 100 ((a + 2) 2^i - 2) + 57) \\ &=& 32 (a + 2)^2 \sum 4^i + (100 - 128) (a + 2) \sum 2^i + (128 - 200 + 57) k \\ &=& 32/3 (a + 2)^2 (4^k - 1) - 28 (a + 2) (2^k - 1) - 15 k \end{array}\]

See my recursive relations post for an explanation of how to evaluate the number of steps.

Remainder Behavior

Finally, once we’ve applied Rule 4x, we will end up in situations where c < 3. I do not fully explore all these cases, only the ones necessary to model this machine’s behavior on a blank tape.

`C(a, 1, 2, 1)`

Rule 5: C(a, 1, 2, 1) -> C(1, 1, 4a+6, 1) in \(8a + 40\) steps

Proof:

Step #	Left tape	State	Right tape
0	00001	<E	0101^a 10010000
1	00000	A>	0101^a 10010000
4a+ 1	00000 1010^a	A>	10010000
4a+ 2	00000 1010^a 1	C>	0010000
4a+ 3	00000 1010^a 11	A>	010000
4a+ 4	00000 1010^a 111	B>	10000
4a+ 5	00000 1010^a 1110	F>	0000
4a+ 6	00000 1010^a 11101	E>	000
4a+ 7	00000 1010^a 11101	<D	100
4a+ 8	00000 1010^a 1110	<E	0100
4a+ 9	00000 1010^a 111	<D	10100
4a+10	00000 1010^a 11	<E	010100
4a+11	00000 1010^a 10	A>	0101 00
4a+15	00000 1010^a 10 1010	A>	00
4a+16	00000 1010^a 1010101	B>	0
4a+17	0000 01^2a+4	<C	1
8a+25	0000	<C	00^2a+4 1
8a+26	0001	A>	0^4a+8 1
8a+27	00011	B>	0^4a+7 1
8a+28	00011	<C	1 0^4a+6 1
8a+29	0001	<D	01 0^4a+6 1
8a+30	000	<E	001 0^4a+6 1
8a+31	00	<D	1001 0^4a+6 1
8a+32	0	<C	01001 0^4a+6 1
8a+33	1	A>	01001 0^4a+6 1
8a+34	11	B>	1001 0^4a+6 1
8a+35	110	F>	001 0^4a+6 1
8a+36	1101	E>	01 0^4a+6 1
8a+37	1101	<D	11 0^4a+6 1
8a+38	110	<E	011 0^4a+6 1
8a+39	11	<D	1011 0^4a+6 1
8a+40	1	<E	0101 1 0^4a+6 1

`C(a, 1, 1, 1)`

Rule 6: C(a, 1, 1, 1) -> C(1, 1, 4a+4, 3) in \(24a + 54\) steps

Proof:

Step #	Left tape	State	Right tape
0	0000001	<E	0101^a 101000
1	0000000	A>	0101^a 101000
4a+ 1	0000000 1010^a	A>	101000
4a+ 2	0000000 1010^a 1	C>	01000
4a+ 3	0000000 1010^a 11	A>	1000
4a+ 4	0000000 1010^a 111	C>	000
4a+ 5	0000000 1010^a 1111	A>	00
4a+ 6	0000000 1010^a 11111	B>	0
4a+ 7	0000000 1010^a 11111	<C	1
4a+ 8	0000000 1010^a 1111	<D	01
4a+ 9	0000000 1010^a 111	<E	001
4a+10	0000000 1010^a 110	A>	001
4a+11	0000000 1010^a 1101	B>	01
4a+12	0000000 1010^a 1101	<C	11
4a+13	0000000 1010^a 110	<D	011
4a+14	0000000 1010^a 11	<C	0011
4a+15	0000000 1010^a 1	<D	00011
4a+16	0000000 1010^a	<E	000011
8a+16	0000000	<E	0101^a 000011
8a+17	000000	<D	1 0101^a 000011
8a+18	00000	<C	01 0101^a 000011
8a+19	00001	A>	0101^a 01 000011
12a+19	00001 1010^a	A>	01 000011
12a+20	00001 1010^a 1	B>	1000011
12a+21	00001 1010^a 10	F>	000011
12a+22	00001 10^2a+1 1	E>	00011
12a+23	00001 10^2a+1 1	<D	10011
12a+24	00001 10^2a+1	<E	010011
16a+26	00001	<E	01^2a+1 010011
16a+27	00000	A>	0101^a+1 0011
20a+31	00000 1010^a+1	A>	0011
20a+32	00000 1010^a+1 1	B>	011
20a+33	00000 1010^a+1 1	<C	111
20a+34	00000 1010^a+1	<D	0111
24a+38	00000	<D	0000^a+1 0111
24a+39	0000	<C	0 0^4a+5 111
24a+40	0001	A>	00 0^4a+4 111
24a+41	00011	B>	0 0^4a+4 111
24a+42	00011	<C	1 0^4a+4 111
24a+43	0001	<D	01 0^4a+4 111
24a+44	000	<E	001 0^4a+4 111
24a+45	00	<D	1001 0^4a+4 111
24a+46	0	<C	01001 0^4a+4 111
24a+47	1	A>	01001 0^4a+4 111
24a+48	11	B>	1001 0^4a+4 111
24a+49	110	F>	001 0^4a+4 111
24a+50	1101	E>	01 0^4a+4 111
24a+51	1101	<D	11 0^4a+4 111
24a+52	110	<E	011 0^4a+4 111
24a+53	11	<D	1011 0^4a+4 111
24a+54	1	<E	0101 1 0^4a+4 111

`C(a, 1, 2, d+2)`

Rule 7: C(a, 1, 2, d+2) -> 0^∞ 1010^a 11101 Z> 1^d 0^∞ (Halting with score \(2a+d+4\)) in \(4a + 6\) steps

Proof:

Step #	Left tape	State	Right tape
0	00001	<E	0101^a 10011
1	00000	A>	0101^a 10011
4a+ 1	00000 1010^a	A>	10011
4a+ 2	00000 1010^a 1	C>	0011
4a+ 3	00000 1010^a 11	A>	011
4a+ 4	00000 1010^a 111	B>	11
4a+ 5	00000 1010^a 1110	F>	1
4a+ 6	00000 1010^a 11101	Z>

Behavior

Collecting together the relevant rules:

Rule 4x: C(a, 1, 3k+r, d) -> C((a + 2) 2^k - 2, 1, r, d) in \(32/3 (a + 2)^2 (4^k - 1) - 28 (a + 2) (2^k - 1) - 15 k\) steps
Rule 5: C(a, 1, 2, 1) -> C(1, 1, 4a+6, 1) in \(8a + 40\) steps
Rule 6: C(a, 1, 1, 1) -> C(1, 1, 4a+4, 3) in \(24a + 54\) steps
Rule 7: C(a, 1, 2, d+2) -> 0^∞ 1010^a 11101 Z> 1^d 0^∞ (Halting with score \(2a+d+4\)) in \(4a + 6\) steps

Orbit from a blank tape

Starting a blank tape, this TM reaches configuration C(1, 1, 8, 1) at step 85, from which we get:

Config	By Rule	Steps Since Last	Step At
`C(1, 1, 8, 1)`			85
`C(10, 1, 2, 1)`	Rule 4x	1,158	1,243
`C(1, 1, 46, 1)`	Rule 5	120	1,363
`C(3·2¹⁵ - 2, 1, 1, 1)`	Rule 4x	96·4¹⁵ - 84·2¹⁵ - 15·15 - 12
`C(1, 1, 12·2¹⁵ - 4, 3)`	Rule 6	72·2¹⁵ + 6
`C(3·2^{4·2¹⁵ - 2} - 2, 1, 2, 3)`	Rule 4x	96·4^k - 84·2^k - 15·k - 12 (with k = 4·2¹⁵ - 2)
`Halt(6·2^{4·2¹⁵ - 2} + 1) = Halt(3/2·2^2¹⁷ + 1)`	Rule 7	12·2^{4·2¹⁵ - 2} - 2	6·4^2¹⁷ - 18·2^2¹⁷ + 6·4¹⁷ - 18·2¹⁷ + 1148

Proving that this TM has:

a Busy Beaver “score” of \(\frac{3}{2} \cdot 2^{2^{17}} + 1\) and
a step count of \(6 \cdot 4^{2^{17}} - 18 \cdot 2^{2^{17}} + 6 \cdot 4^{17} - 18 \cdot 2^{17} + 1148\)

Is this really Collatz-like behavior?

I’m not quite sure if it’s appropriate to call this behavior “Collatz-like”.

For one thing, we have not fully specified the function. In fact, not all configurations stay in this general config C. For example, C(a, 0, c+2, d) -> 0^∞ 1 <E 0101¹ 1 0^4a 1 0^c 1^d 0^∞.

Furthermore, we can actually see that by the rules I’ve listed above, a large class of configurations can all be proven to lead to halts. For example, all configurations C(1, 1, 3k+2, 1) lead to halt:

Config	By Rule
`C(1, 1, 3k+2, 1)`
`C(3·2^k - 2, 1, 2, 1)`	Rule 4x
`C(1, 1, 12·2^k - 2, 1) = C(1, 1, 3 (2^k+2 - 1) + 1, 1)`	Rule 5
`C(3·2^{2^k+2 - 1} - 2, 1, 1, 1)`	Rule 4x
`C(1, 1, 12·2^{2^k+2 - 1} - 4, 3) = C(1, 1, 3 (2^(2^k+2 + 1) - 2) + 2, 3)`	Rule 6
`C(3·2^{2^{2^k+2 + 1} - 2} - 2, 1, 2, 3)`	Rule 4x
`Halt(6·2^{2^{2^k+2 + 1} - 2} + 1) = Halt(3/2·2^{2^{2^k+2 + 1}} + 1)`	Rule 7