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×1078913 steps and leaves >6×1039456 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

  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×1078913 steps before halting in the configuration:

0 1010N 11101 Z> 1 0

where N = 3/4 * 2217 - 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 0101a 1b 0c 1d 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 0101a 11 …
1 000 A> 0101a 11 …
4a+ 1 000 1010a A> 11 …
4a+ 2 000 1010a 1 C> 1 …
4a+ 3 000 1010a 1 <D 0 …
4a+ 4 000 1010a <E 00 …
8a+ 4 000 <E 0101a 00 …
8a+ 5 00 <D 1 0101a 00 …
8a+ 6 0 <C 01 0101a 00 …
8a+ 7 1 A> 0101a 01 00 …
12a+ 7 1 1010a A> 01 00 …
12a+ 8 1 1010a 1 B> 100 …
12a+ 9 1 1010a 10 F> 00 …
12a+10 1 1010a 101 E> 0 …
12a+11 1 1010a 101 <D 1 …
12a+12 1 1010a 10 <E 01 …
16a+14 1 <E 0101a 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

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: 01n <E 00 -> <E 00 11n in 10n steps
Step # Left tape State Right tape
0 0001 <E 0101a 1000
1 0000 A> 0101a 1000
4a+ 1 0000 1010a A> 1000
4a+ 2 0000 1010a 1 C> 000
4a+ 3 0000 1010a 11 A> 00
4a+ 4 0000 1010a 111 B> 0
4a+ 5 0000 1010a 111 <C 1
4a+ 6 0000 1010a 11 <D 01
4a+ 7 000 012a+1 <E 00 1
24a+17 000 <E 00 112a+1 1
24a+18 00 <D 100 14a+3
24a+19 0 <C 0100 14a+3
24a+20 1 A> 0100 14a+3
24a+21 11 B> 100 14a+3
24a+22 110 F> 00 14a+3
24a+23 1101 E> 0 14a+3
24a+24 1101 <D 1 14a+3
24a+25 110 <E 01 14a+3
24a+26 11 <D 101 14a+3
24a+27 1 <E 0101 14a+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 8 (2a + 1)2 + (16 + 6) (2a + 1) + (24a + 27) = 32 a2 + 100 a + 57 steps.

Repeated Application

Since Rule 4 has the same start and end configuration, it can be applied repeatedly as long as c >= 3.

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

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 0101a 10010000
1 00000 A> 0101a 10010000
4a+ 1 00000 1010a A> 10010000
4a+ 2 00000 1010a 1 C> 0010000
4a+ 3 00000 1010a 11 A> 010000
4a+ 4 00000 1010a 111 B> 10000
4a+ 5 00000 1010a 1110 F> 0000
4a+ 6 00000 1010a 11101 E> 000
4a+ 7 00000 1010a 11101 <D 100
4a+ 8 00000 1010a 1110 <E 0100
4a+ 9 00000 1010a 111 <D 10100
4a+10 00000 1010a 11 <E 010100
4a+11 00000 1010a 10 A> 0101 00
4a+15 00000 1010a 10 1010 A> 00
4a+16 00000 1010a 1010101 B> 0
4a+17 0000 012a+4 <C 1
8a+25 0000 <C 002a+4 1
8a+26 0001 A> 04a+8 1
8a+27 00011 B> 04a+7 1
8a+28 00011 <C 1 04a+6 1
8a+29 0001 <D 01 04a+6 1
8a+30 000 <E 001 04a+6 1
8a+31 00 <D 1001 04a+6 1
8a+32 0 <C 01001 04a+6 1
8a+33 1 A> 01001 04a+6 1
8a+34 11 B> 1001 04a+6 1
8a+35 110 F> 001 04a+6 1
8a+36 1101 E> 01 04a+6 1
8a+37 1101 <D 11 04a+6 1
8a+38 110 <E 011 04a+6 1
8a+39 11 <D 1011 04a+6 1
8a+40 1 <E 0101 1 04a+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 0101a 101000
1 0000000 A> 0101a 101000
4a+ 1 0000000 1010a A> 101000
4a+ 2 0000000 1010a 1 C> 01000
4a+ 3 0000000 1010a 11 A> 1000
4a+ 4 0000000 1010a 111 C> 000
4a+ 5 0000000 1010a 1111 A> 00
4a+ 6 0000000 1010a 11111 B> 0
4a+ 7 0000000 1010a 11111 <C 1
4a+ 8 0000000 1010a 1111 <D 01
4a+ 9 0000000 1010a 111 <E 001
4a+10 0000000 1010a 110 A> 001
4a+11 0000000 1010a 1101 B> 01
4a+12 0000000 1010a 1101 <C 11
4a+13 0000000 1010a 110 <D 011
4a+14 0000000 1010a 11 <C 0011
4a+15 0000000 1010a 1 <D 00011
4a+16 0000000 1010a <E 000011
8a+16 0000000 <E 0101a 000011
8a+17 000000 <D 1 0101a 000011
8a+18 00000 <C 01 0101a 000011
8a+19 00001 A> 0101a 01 000011
12a+19 00001 1010a A> 01 000011
12a+20 00001 1010a 1 B> 1000011
12a+21 00001 1010a 10 F> 000011
12a+22 00001 102a+1 1 E> 00011
12a+23 00001 102a+1 1 <D 10011
12a+24 00001 102a+1 <E 010011
16a+26 00001 <E 012a+1 010011
16a+27 00000 A> 0101a+1 0011
20a+31 00000 1010a+1 A> 0011
20a+32 00000 1010a+1 1 B> 011
20a+33 00000 1010a+1 1 <C 111
20a+34 00000 1010a+1 <D 0111
24a+38 00000 <D 0000a+1 0111
24a+39 0000 <C 0 04a+5 111
24a+40 0001 A> 00 04a+4 111
24a+41 00011 B> 0 04a+4 111
24a+42 00011 <C 1 04a+4 111
24a+43 0001 <D 01 04a+4 111
24a+44 000 <E 001 04a+4 111
24a+45 00 <D 1001 04a+4 111
24a+46 0 <C 01001 04a+4 111
24a+47 1 A> 01001 04a+4 111
24a+48 11 B> 1001 04a+4 111
24a+49 110 F> 001 04a+4 111
24a+50 1101 E> 01 04a+4 111
24a+51 1101 <D 11 04a+4 111
24a+52 110 <E 011 04a+4 111
24a+53 11 <D 1011 04a+4 111
24a+54 1 <E 0101 1 04a+4 111

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

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

Proof:

Step # Left tape State Right tape
0 00001 <E 0101a 10011
1 00000 A> 0101a 10011
4a+ 1 00000 1010a A> 10011
4a+ 2 00000 1010a 1 C> 0011
4a+ 3 00000 1010a 11 A> 011
4a+ 4 00000 1010a 111 B> 11
4a+ 5 00000 1010a 1110 F> 1
4a+ 6 00000 1010a 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 (4k - 1) - 28 (a + 2) (2k - 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 1010a 11101 Z> 1d 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·215 - 2, 1, 1, 1) Rule 4x 96·415 - 84·215 - 15·15 - 12  
C(1, 1, 12·215 - 4, 3) Rule 6 72·215 + 6  
C(3·24·215 - 2 - 2, 1, 2, 3) Rule 4x 96·4k - 84·2k - 15·k - 12 (with k = 4·215 - 2)  
Halt(6·24·215 - 2 + 1) = Halt(3/2·2217 + 1) Rule 7 12·24·215 - 2 - 2 6·4217 - 18·2217 + 6·417 - 18·217 + 1148

Proving that this TM has:

  • a Busy Beaver “score” of 3/2·2217 + 1 and
  • a step count of 6·4217 - 18·2217 + 6·417 - 18·217 + 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 01011 1 04a 1 0c 1d 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·2k - 2, 1, 2, 1) Rule 4x
C(1, 1, 12·2k - 2, 1) = C(1, 1, 3 (2k+2 - 1) + 1, 1) Rule 5
C(3·22k+2 - 1 - 2, 1, 1, 1) Rule 4x
C(1, 1, 12·22k+2 - 1 - 4, 3) = C(1, 1, 3 (2^(2k+2 + 1) - 2) + 2, 3) Rule 6
C(3·222k+2 + 1 - 2 - 2, 1, 2, 3) Rule 4x
Halt(6·222k+2 + 1 - 2 + 1) = Halt(3/2·222k+2 + 1 + 1) Rule 7