I spend a lot of time doing “quick-and-dirty” analyses of new Busy Beaver champions. Recently, when I have time, I have been posting those analyses on this blog in detailed form. However, converting from my quick notes to a polished blog post is a lot of time and work and so most of my analyses don’t make it. However, I think there is some value in the quick notes, so I keep them in unsaved documents in my editor until I end up with too many tabs (or my computer crashes) and eventually I delete them. As a middle ground, I’ve decided to try and post unpolished notes here as a value to myself if I ever come back and want to understand these machines behavior again in the future. I may add more notes here over time.

## 2022

### May 2022

#### Pavel-e197k

Shared by email 15 May 2022 by Pavel Kropitz. This TM runs >10^197,282 steps leaving >10^98,641 symbols.

1RB 1RH 1RC 1RA 1RD 0RB 1LE 0RC 0LF 0LD 0LB 1LA

Rule 1: 11 01^n D> 00 -> 01^n+2 D> Rule 1x: 11^n D> 0^inf -> 01^2n D> 0^inf

Rule 2: 1010 01^m D> 0^inf -> 01^2m+8 D> 0^inf Rule 2x: 1010^n 01^m D> 0^inf -> 01^((m+8) 2^n - 8) D> 0^inf

Rule 3: 000 01^n D> 000 -> 0100 10^n 11 D> Rule 4: 100 01^n D> 0^inf -> 11 10^n+1 11^1 D> 0^inf

Rule 5: 000 01^2k+1 D> 0^inf -> 01^(20 2^k - 8) D> 0^inf Rule 6: 000 01^2k D> 0^inf -> 011 Z> 10 10^(10 2^(5 2^k - 4) - 8) 1 0^inf (Halt(10 2^(5 2^k - 4) - 4)) Rule 7: 0^inf 01^2k+1 D> 0^inf -> Halt(10 2^(5 2^(10 2^k - 4) - 4) - 5)

At step 9, it’s in config 0^inf 01^3 D> 0^inf -> Halt(10 2^(5 2^16 - 4) - 4)

While analyzing 6x2 machines “adjacent” to Pavel-e197k, I found this machine which our filters do not appear to be able to categorize:

0LD 1RZ 1RC 1RA 1RD 0RB 1LE 0RC 0LF 0LD 0LB 1LA

Rule 1: 1010 01^m D> 00 -> 01^m+3 D> Rule 1x: 1010^n 01^m D> 0^inf -> 01^m+3n D> 0^inf

Rule 2: 0^inf 100 01^m D> 0^inf -> 0^inf 10010 01^m+1 D> 0^inf Rule 3: 0^inf 10010 01^m D> 0^inf -> 0^inf 100 10^m+3 01^2 D> 0^inf

Rule 4a: 100 01^2k D> -> 100 10^2k+4 01^2 D> -> 100 01^3k+8 D> Rule 4b: 100 01^2k+1 D> -> 100 10^2k+5 01^2 D> -> 10010 01^3k+8 D> -> 100 10^3k+11 01^2 D>

Rule 5a: 100 10^2k 01^2 D> -> 100 01^3k+2 D> Rule 5b: 100 10^2k+1 01^2 D> -> 10010 01^3k+2 D> -> 100 10^3k+5 01^2 D>

At step 20, it’s in config 100 01^2 D> at which point Rules 4/5 a/b will apply forever, so this is infinite (but our system is not smart enough to know that).

While analyzing 6x2 machines “adjacent” to the short-lived 6x2 champion I announced on Friday (which runs for >10^78913 steps), I found exactly one machine (with 3 different permutations of start state) which our filters aren’t able to categorize. This is the same as my 6x2 former champion except with A1 -> 1RA.

1RB 1RA 1LC 0RF 1RA 0LD 0LC 0LE 1LD 0RA 1RE 1RZ

a0: 00001 <E 0101^a 1^3k 00 -> 1 <E 0101 1 0^4a 001^k 1 a1:  001 <E 0101^a 1^3k+1 00 -> 1 <E 0101^a+1 001^k 1 a2:  0001 <E 0101^a 1^3k+2 00 -> 1 <E 0101 1^4a+2 001^k 1

Once this machine gets into a tape matching regular expression 0^inf 1 <E (0101)+ (00|1)* 0^inf it will never leave. Thus these machines are infinite.

#### Swapping Rules

1RB 1RF 1LC 1LB --- 0LD 1LE 1LF 1RE 1LD 0RF 0RA

Rule 1: 0100 01^a <D 01 11^b -> 0100 01^b+1 <D 01 11^a Rule 1x: 0100 01^a <D 01 11^b -> 0100 01^a+1 <D 01 11^b -> Infinite

1RB 1LC 0RC 1LE 1RD 0LA 1LB 1RC 1RC 1LF --- 1LE

Rule 1: 01 11^a 10 C> 01^b 11 -> 01 11^b-2 10 C> 01^a+4 11 Rule 1x: 01 11^a 10 C> 01^b 11 -> 01 11^a+2 10 C> 01^b+2 11 -> Infinite

#### Three Stage Rules

1RB 1LE 1LC --- 1RD 1LB 1LF 0LE 0LD 1RF 0RE 0RA

C(a, b, c) = <F 10^a 0^b 11^c

Rule 1: C(a, b + 1, c) -> C(a + 1, b, c) Rule 1x: C(a, b, c) -> C(a + b, 0, c)

Rule 2: C(a, 0, c+2) -> C(1, 2a+2, c+1) -> C(2a+3, 0, c+1) Rule 2x: C(a, 0, c+1) -> C( (a+3) 2^c - 3, 0, 1)

Rule 3: C(a, 0, 1) -> C(1, 4, 2a+4) -> C(5, 0, 2a+4) -> C(8 2^(2a+4) - 3, 0, 1) Rule 3x: C(a, 0, 1) -> Infinite

1RB --- 1LC 1LB 0RE 0LD 1RD 1LC 1RF 0LE 1RE 1RA

E(a, b, c) = <E 0^2a+1 1^b 01^2c+1

Rule 1: E(a, b+1, c) -> E(a+1, b, c) Rule 1x: E(a, b, c) -> E(a+b, 0, c)

Rule 2: E(a, 0, c+1) -> E(0, 2a+6, c) -> E(2a+6, 0, c) Rule 2x: E(a, 0, c) -> E( (a+6) 2^c - 6, 0, 0)

Rule 3: E(2k, 0, 0) -> E(0, 0, k+1) -> E(6 2^k+1 - 6, 0, 0) Rule 3x: E(2k, 0, 0) -> Inf

1RB 1LE 1RC 1RB 1LD 0RE --- 0LA 1LF 0RD 1RB 1LA

E(a, b, c) = <E 10^a 1^b 0 01^c

Rule 1: E(a, b+2, c) -> E(a+1, b+1, c) Rule 1x: E(a, b+1, c) -> E(a+b, 1, c)

Rule 2: E(a, 1, c+1) -> E(1, 2a+3, c) -> E(2a+3, 1, c) Rule 2x: E(a, 1, c) -> E((a+3) 2^c - 3, 1, 0)

Rule 3: E(a, 1, 0) -> E(1, 1, a + 2) -> E(4 2^(a+2) - 3, 1, 0) Rule 3: E(a, 1, 0) -> Infinite

1RB --- 1RC 1RA 0RD 1LE 1RE 0RC 0LC 0LF 1LA 1RC

E(a, b, c) = 11^a 0^b 01^c E>

E(a, b+1, c) -> E(a, b, c+1) E(a, b, c) -> E(a, 0, c+b)

E(a+2, 0, c) -> E(a+1, 2c + 2, 1) -> E(a+1, 0, 2c+3)

E(1, 0, c) -> E(c+3, 0, 1) -> Inf

1RB 0LC 0LA 1RD 1LA 1LB 0RE 1LA 0RB 0RF 1RE ---

Rule 1: 00 <C 01^n+1 -> 11^2 00 <C 01^n Rule 1x: 00 <C 01^n+1 -> 11^2n 00 <C 01 Rule 1+: 00 <C 01^n+1 -> <C 01^2n 001

C(a, b, c) = 11^a 00 <C 01^b 001 01^c 001

Rule 2: C(a, b+1, c) -> C(a+1, b, 2c) Rule 2x: C(a, b, c) -> C(a+b, 0, c 2^b)

Rule 3: C(a, 0, c) -> C(0, a+1, 2c) -> C(a+1, 0, c 2^b+1) Rule 3x: C(a, 0, c) -> Infinite

### June 2022

#### Halting 6x2

1RB 0LE 0RC 1RF 1RD 0RB 1LA 1RB 1LA 0LD 1RA 1RZ

0 011^n 01 D> 0  ->  1^3n+2 01 D>

D(n, a, b, c) = 111 011^n 0^a 1^b 011^c 01 D>

Rule 1:  D(a, b+3, c) -> D(a, b+1, c+2)
Rule 1x: D(a, 2k+r, c) -> D(a, r, c+2k)

Rule 2: D(a+1, 0, c) -> D(a, 3c+2, 0)

Rule 3: D(a+1, 2k) -> D(a+1, 0, 2k) -> D(a, 6k+2) = D(a, 3b+2)
Rule 3x: D(a, 2k) -> D(0, A 3^a - B)

Rule 4: D(4, 1, c+1) -> 111 011 D(2, 3c+1, 0)
Rule 5: 1 D(2, 1, c) -> 1011 D(4, 0, c) -> 1011 D(3, 3c+2, 0)

@3:  D(0, 1, 1)
@36: D(0, 5, 1)
1x:  D(0, 1, 5)
4:   111 011 D(2, 13)
1x:  111 011 D(2, 1, 12)
5:   111 011 011 D(3, 38)  # 38 -> 116 -> 350 -> 1052
3x:  111 011 011 D(0, 1052)  =  111 011 D(1, 1054)
3x:  111 011 D(0, 3164) = 111 D(1, 3166)
3x:  111 D(0, 9500) = D(0, 9503)
1x:  D(0, 1, 9502)
4:   111 011 D(2, 28_504)

       +-----+-----+
|  0  |  1  |
+---+-----+-----+
| A | 1RB | 0LE |
+---+-----+-----+
| B | 0RC | 1RF |
+---+-----+-----+
| C | 1RD | 0RB |
+---+-----+-----+
| D | 1LA | 1RB |
+---+-----+-----+
| E | 1LA | 0LD |
+---+-----+-----+
| F | 1RA | 1RZ |
+---+-----+-----+

<D 001010  100^4     101
10 <D 00  100^2     101   001^340    01
<E 0100  100^9     10    100^e10    101
<D 001010  100^23    10    100^e28    101
10 <D 00  100^82    10    100^e111   101
<E 0100  100^279   10    100^e391   101
<D 001010  100^946   10    100^e1344  101
10 <D 00  100^3195  10    100^e4561  101
<E 0100  100^10787 10 10 100^e15427 101

A(a, b) = 1011 <A 100^a 100 101 001 001^b 01
111 011 00 111^a 1101100 B> 01 001^b 01
111 011 00 111^a 1101100 00 B> 001^b 01
111 011 00 111^a 1101100 00 011^b B> 01
111 011 00 111^a 1101100 00 011^b 01101 D> 0
= 111 011 00 1^3a+2 011 D(4, 0, b+1)
111 011 00 1^3a+2 011 D(3, 3b+5, 0)

A(a, 2k+1)
111 011 00 1^3a+2 011 D(3, 6k+8, 0)
111 011 00 1^3a+2 011 D(0, (6k+9) 3^3 - 1, 0)
= 111 011 00 1^3a+2 D(1, (6k+9) 3^3 + 1, 0)
111 011 00 1^3a+2 D(0, (6k+9) 3^4 + 5, 0)
= 111 011 00 1^3a+2 D(0, (6k+9) 3^4 + 5, 0)

Rule 1:  D(a, b+3, c) -> D(a, b+1, c+2)
Rule 1x: D(a, 2k+r, c) -> D(a, r, c+2k)

Rule 2: D(a+1, 0, c) -> D(a, 3c+2, 0)

Rule 3: D(a+1, 2k) -> D(a+1, 0, 2k) -> D(a, 6k+2) = D(a, 3b+2)
Rule 3x: D(a, 2k) -> D(0, (2k+1) 3^a - 1)

Rule 4: D(4, 1, c+1) -> 111 011 D(2, 3c+1, 0)
Rule 5: 1 D(2, 1, c) -> 1011 D(4, 0, c) -> 1011 D(3, 3c+2, 0)

0000 1011 <A  -> 11101100 B>
000010 <D 00
0000 <E 0100
00 <D 001010
11101100 B>

B> 100 -> 111 B>
(11) B> 1010 -> 101100 B>
B> 01 -> 00 B>
B> 001 -> 011 B>

B> 01 0000 -> <A 100101
0001 D> 00
01101 D> 0
<A 100 101

       +-----+-----+
|  0  |  1  |
+---+-----+-----+
| A | 1LE | 0LD |
+---+-----+-----+
| B | 0RC | 0RE |
+---+-----+-----+
| C | 0RD | 1RC |
+---+-----+-----+
| D | 1LA | 1LF |
+---+-----+-----+
| E | 1RB | 0LA |
+---+-----+-----+
| F | 1LD | 1RZ |
+---+-----+-----+

Rule 1:  00 <E 10^n 11 -> <E 10^n+2
Rule 1x: 0^inf <E 10^n 11^m -> 0^inf <E 10^n+2m

Rule 2:  0000 <E 10^n 0101 -> <E 1^2n+8 -> 0^inf <E 10^2n+8
Rule 2x: 0^inf <E 10^n 0101^m -> 0^inf <E 10^((n+8) 2^m - 8)

Rule 3:  000 <E 10^n 000 -> <E 11 0 10^n 010 -> <E 10^2 01^n 00 10
Rule 4:  00 <E 10^n 0100 -> <E 10^n+2 11 -> 0^inf <E 10^n+4

@64:  <E 10^7
R 3:  <E 10^2 01^7 00 10
R 2x: <E 10^(10 2^3 - 8) 0100 10   # = 72
R 4:  <E 10^76 10
R 3:  <E 10^2 01^77 0010

Repeat forever:
<E 10^2k+1
R 3:  <E 10^2 01^2k+1 0010
R 2x: <E 10^(10 2^k - 8) 0100 10
R 4:  <E 10^(10 2^k - 4) 10  =  <E 10^(10 2^k - 3)


### Oct 2022

#### 5x2 Qhalt

This is the latest Quasihalting TM I’ve found in 5x2 with at least 1 undefined transition (i.e. it’s part of the BB(5, 2) search).

1RB---_0LC0LB_0LD1LC_1RD0RE_1LB1LA

D(a, b, c) = 0^inf 1^a D> 1^b 0 1^c 0^inf

D(a, b+2, c) -> D(a+5, b, c)
D(a, 2, 0) -> Qhalt
D(a, 2, c) -> D(a+6, c, 0)
D(a, 1, c) -> D(2, a, c+1)

0 : D(2, 1, 0)   @ step 6
1 : D(2, 2, 1)
2 : D(8, 1, 0)
3 : D(2, 8, 1)
4 : D(17, 2, 1)
5 : D(23, 1, 0)
6 : D(2, 23, 1)
7 : D(57, 1, 1)
8 : D(2, 57, 2)
9 : D(142, 1, 2)
10 : D(2, 142, 3)
11 : D(352, 2, 3)
12 : D(358, 3, 0)
13 : D(363, 1, 0)
14 : D(2, 363, 1)
15 : D(907, 1, 1)
16 : D(2, 907, 2)
17 : D(2267, 1, 2)
18 : D(2, 2267, 3)
19 : D(5667, 1, 3)
20 : D(2, 5667, 4)
21 : D(14167, 1, 4)
22 : D(2, 14167, 5)
23 : D(35417, 1, 5)
24 : D(2, 35417, 6)
25 : D(88542, 1, 6)
26 : D(2, 88542, 7)
27 : D(221352, 2, 7)
28 : D(221358, 7, 0)
29 : D(221373, 1, 0)
30 : D(2, 221373, 1)
31 : D(553432, 1, 1)
32 : D(2, 553432, 2)
33 : D(1383577, 2, 2)
34 : D(1383583, 2, 0)
35 : Qhalt


## 2023

### March 2023

#### 6x2 Level 3 Infinite

https://bbchallenge.org/1RB1LA_1RC0LE_1RD1RB_0LA0LF_1LC1LB_—1LD

A TM Pavel shared on Discord which does Level 3 Collatz recurrence (like https://www.sligocki.com/2022/06/21/bb-6-2-t15.html) but none of the Collatz cases halt:

Let A(a, b, c) = 0^inf <A 01^a 00 10^b 1^c 0^inf

Level 1:
A(a, b+1, c) -> A(a+2, b, c)
A(a, 0, c+5) -> A(1, a+5, c)
A(a, 0, 0) -> A(1, 2, 2a)
A(a, 0, 1) -> A(1, 2, 2a+4)
A(a, 0, 2) -> A(1, 2, 2a+6)
A(a, 0, 3) -> A(1, 2, 2a+8)
A(a, 0, 4) -> A(1, 2, 2a+10)

Level 2:
A(a, 0, c+5) -> A(2a+11, 0, c)

Level 3:
A(1, 2, 5k  ) -> A(1, 2, 32 2^k - 22)
A(1, 2, 5k+1) -> A(1, 2, 32 2^k - 18)
A(1, 2, 5k+2) -> A(1, 2, 32 2^k - 16)
A(1, 2, 5k+3) -> A(1, 2, 32 2^k - 14)
A(1, 2, 5k+4) -> A(1, 2, 32 2^k - 12)


Level 1 rules are actually all you need. The set $$\{A(a, b, c) : a, b, c \in \mathbb{N}\}$$ is closed, so once TM enters it cannot halt.

#### 6x2 Level 3 Avoids Halt

https://bbchallenge.org/1RB0LF_1LC1RD_1LA0RC_0RE1RB_0LC1LA_—1LE

Another TM Pavel shared on Discord which also has Level 3 Collatz recurrence and some of the Collatz cases even halt! But it skillfully avoids them:

Let C(a, b, c) = $1100 (01111 1100)^a 1100 0110^b 1100^c C> 1$

@93: C(0, 0, 1)

Level 1:
C(a, b+1, c) -> C(a, b, c+2)
C(a+1, 0, c) -> C(a, c+2, 2)

C(0, 0, 9k+1) -> C(4k+1, 0, 2)
C(0, 0, 9k+4) -> C(4k+2, 1, 2)
C(0, 0, 9k+7) -> C(4k+4, 0, 1)

C(0, 0, 3k+2) -> Halt

Level 2:
C(a+1, 0, c) -> C(a, 0, 2c+6)
*: C(a, 0, c) -> C(0, 0, (c+6) 2^a - 6)

Level 3:
C(0, 0, 9k+1) -> C(0, 0,  8 2^{4k+1} - 6)
C(0, 0, 9k+4) -> C(0, 0, 10 2^{4k+2} - 6)
C(0, 0, 9k+7) -> C(0, 0,  7 2^{4k+4} - 6)


The trick is that we can rewrite the Level 3 rules as:

  C(0, 0, 9k+1) -> C(0, 0,    4^{2k+2} - 6)
C(0, 0, 9k+4) -> C(0, 0, 10 4^{2k+1} - 6)
C(0, 0, 9k+7) -> C(0, 0,  7 4^{2k+2} - 6)


And since $$4^n \equiv 1 \mod 3$$ (and so do 10 and 7), the right sides will always be remainder 1 (mod 3) and so always one of remainders (1, 4, 7) mod 9.

But it is delicate! A slight tweak, like 7 2^{4k+1} - 6 and this condition would not hold any longer!

All of the permutations of this TM fall into the same starting config C(0, 0, 1) except for starting from state B in which case we reach C(0, 0, 0) which leads to the rule:

C(0, 0, 9k+0) -> C(0, 0, 10 2^{4k+1} - 7) = C(0, 0, 5 4^{2k+1} - 7)


But that is also guaranteed to always be remainder 1 (mod 3)! and so will never halt.

A re-analysis which makes absorbs these coincidences is:

E(a, b, c) = C(2a, 3b, 3c+1) = $1100 {01111 1100 01111 1100}^a 1100 {0110 0110 0110}^b 1100 {1100 1100 1100}^c C> 1$

E(a, b+1, c) -> E(a, b, c+2)
E(a+1, 0, c) -> E(a, 0, 4c+7)
E(0, 0, 3k)   -> E(2k  , 0, 3)
E(0, 0, 3k+1) -> E(2k+1, 0, 1)
E(0, 0, 3k+2) -> E(2k+2, 0, 0)

And Blank -> E(0, 0, 0) in 93 steps.


At which point we have a closed set, so presumably this TM is solveable by CTL with regular expression: 1100 (01111 1100 01111 1100)* 1100 (0110 0110 0110)* 1100 (1100 1100 1100)* C> 1?

#### 6x2 Another Avoids Halt

https://bbchallenge.org/1RB1RD_1LC1LF_0LD1LB_1RE0RA_1RA1RE_—1LD

TM shared by @savask on Discord: https://discord.com/channels/960643023006490684/1026577255754903572/1091130641317372035

1RB1RD_1LC1LF_0LD1LB_1RE0RA_1RA1RE_---1LD

C(a, b, c, d) = $1^a 10^b 1^c 01^d <C 1$

Level 1:
C(a, b, c+4, d) -> C(a, b, c, d+3)

C(a, b, 2, d) ->  HALT!

C(a, b+1, 0, d) -> C(a, b, 2d+5, 0)
C(a, b+1, 1, d) = C(0, 0, a+1, b+d+1)
C(a, b+1, 3, d) -> C(a, b, 2d+8, 0)

C(0, 0, 0, d) -> C(2, d, 4, 0)
C(0, 0, 1, d) = C(0, 0, 0, d+1)
C(0, 0, 3, d) -> C(0, 0, 2d+7, 0)

Level 2:
C(a, b+1, 4k+0, 0) -> C(a, b, 6k+5, 0)
C(a, b+1, 4k+1, 0) -> C(0, 0, a+1, 3k+b+1)
C(a, b+1, 4k+2, 0) ->  HALT!
C(a, b+1, 4k+3, 0) -> C(a, b, 6k+8, 0)

Level 3:
C(0, 0, 4k+1, 0) -> C(0, 0, 6k+131, 0)     for k >= 2
C(0, 0, 4k+3, 0) -> C(0, 0, 6k+7, 0)


So, you can see the “Level 3” rules are closed, but the way that C(0, 0, 4k+1, 0) -> C(0, 0, 6k+131, 0) is proven is wild! Basically it repeats the same sequence of “Level 2” rules each time (and they happen to never hit the 4k+2 case):

Proof of C(0, 0, 4k+1, 0) -> C(0, 0, 6k+131, 0):
C(0, 0, 4k+1, 0) -> C(0, 0, 1, 3k) = C(0, 0, 0, 3k+1)
-> C(2, 3k+1,  4, 0)
-> C(2, 3k+0, 11, 0)
-> C(2, 3k-1, 20, 0)
-> C(2, 3k-2, 35, 0)
-> C(2, 3k-3, 56, 0)
-> C(2, 3k-4, 89, 0)
-> C(0, 0, 3, 3k+62)
-> C(0, 0, 6k+131, 0)


### April 2023

#### 3x3 Linear Rules

Among my 3x3 holdouts there are 8 that I can prove Linear Rules for:

Group A:
1RB2RB1RC_1LC0LA---_1RA2LC1LB
1RB0RC---_1LC2RB1RA_1LA2LA1LB
1RB2LA1LC_1RC2RC1RA_1LA0LB---

Group B:
1RB---2RA_0RC1RA0RB_2LC2LB0LA
1RB2RA---_0RC2LB2RB_1LC0LA0RB
1RB0RA---_0RC2LB2RB_1LC0LA0RB

Group C:
1RB2LB2LA_1LA2RC1LB_---2RB0LB
1RB1LA2LA_1LA2RC1LB_---2RB0LB

##### Group A
1RB2RB1RC_1LC0LA---_1RA2LC1LB

$1 11^a A> 22 _ ->$ 1 11^a+2 A> _
$1 11^a A> 21 _ ->$ 1 A> 22^a+1 2 _
$1 11^a A> 2000 _ ->$ 1 A> 22^a+2 1 _
$1 11^a A> 10 _ ->$ 1 A> 2 1^2a+1 _

A(a, b, c) = $1 11^a C> 2^b 1^c$

Level 1:
A(a, b+2, c)    -> A(a+2, b, c)
A(a, 1,   c+1)  -> A(0, 2a+3, c)
A(a, 1,   0)    -> A(0, 2a+4, 1)
A(a, 0,   1)    -> A(0, 1, 2a+1)

Level 2:
A(a, 2k+r, c) -> A(a+2k, r, c)
A(0, 2k+1, c+1) -> A(0, 4k+3, c)   4k+3 = 2 (2k+1) + 1
A(0, 2k, 1) -> A(0, 1, 4k+1)

Level 3:
A(0, 1, c) -> A(0, 2^c+1 - 1, 0)
-> A(2^c+1 - 2, 1, 0)
-> A(0, 2^c+2, 1)
-> A(0, 1, 2^c+3 + 1)   [Infinite Rule]

Starts in A(0, 1, 1) @4


The next two are just permutations of the first with start configs:

1RB0RC---_1LC2RB1RA_1LA2LA1LB  :  Starts in A(0, 1, 3) @10
1RB2LA1LC_1RC2RC1RA_1LA0LB---  :  Starts in A(0, 1, 7) @38

##### Group B

These are not permutations of each other, but do share a lot of rules

1RB---2RA_0RC1RA0RB_2LC2LB0LA

_ 22 0^c C> $-> _ 0^c+6 C>$
_ 01 0^c C> $-> _ 1^c+2 0 C>$
_ 11 0^c C> $-> _ 1 2^c+1 0^5 C>$

D(a, b, c) = $1^a+1 2^2b 0^2c+1 C>$

Level 1 (Closed Set):
D(a, b+1, c) -> D(a, b, c+3)
D(a+1, 0, c) -> D(a, c+1, 2)
D(0, 0, c) -> D(2c+2, 0, 0)

Level 2:
D(a, b, c) -> D(a, 0, c+3b)
D(a+1, 0, c) -> D(a, 0, 3c+5)
D(a, 0, c) -> D(0, 0, (c+5/2) 3^a - 5/2)

Level 3:
D(0, 0, c) -> D(0, 0, 5/2 (3^2c+2 - 1))   [Infinite Rule]

Starts in D(0, 0, 0) @2


Next: 1RB2RA—_0RC2LB2RB_1LC0LA0RB

1RB2RA---_0RC2LB2RB_1LC0LA0RB

_  2 0^c C> 00 _ -> _ 0^c+3 C> _
_ 01 0^c C> 0  _ -> _ 1^c+2 0 C> _
_ 11 0^c C> 00 _ -> _ 2^c+3 0 C> _

C(a, b, c) = $1^a 2^b 0^c C>$

Level 1 (Closed Set):
C(a,   b+1, c)  ->  C(a,   b,   c+3)
C(a+2, 0,   c)  ->  C(a,   c+3, 1)
C(1,   0,   c)  ->  C(c+2, 0,   1)
C(0,   0,   c)  ->  Inf Translated Cycle

Starts in C(1, 0, 1) @2


Note that we can even prove that this TM never reaches the C(0, 0, c) transition:

Level 2:
C(a,   b, c)  ->  C(a, 0, c+3b)
C(a+2, 0, c)  ->  C(a, 0, 3c+10)

Level 3:
C(2k+1, 0, 1) -> C(1, 0, 6 3^k - 5)
-> C(6 3^k - 3, 0, 1)   [Infinite Rule]


Next: 1RB0RA—_0RC2LB2RB_1LC0LA0RB is very similar to the previous one.

1RB0RA---_0RC2LB2RB_1LC0LA0RB

_  2 0^c C> 00 _ -> _ 0^c+3 C> _
_ 01 0^c C> 0  _ -> _ 1^c+2 0 C> _
_ 11 0^c C> 00 _ -> _ 00 2^c+1 0 C> _

C(a, b, c) = $1^a 00 2^b 0^c C>$

Level 1 (Closed Set):
C(a,   b+1, c)  ->  C(a,   b,   c+3)
C(a+2, 0,   c)  ->  C(a,   c+3, 1)
C(1,   0,   c)  ->  C(c+2, 2,   1)
C(0,   0,   c)  ->  Inf Translated Cycle

Starts in C(1, 2, 1) @27


Like the last TM we have rules:

Level 2:
C(a, b, c)  ->  C(a, 0, c+3b)
C(a+2, 0, c)  ->  C(a, 0, 3c+10)

Level 3:
C(2k+1, 2, 1) -> C(2k+1, 0, 7)
-> C(1, 0, 12 3^k - 5)
-> C(12 3^k - 3, 2, 1)   [Infinite Rule]

##### Group C
1RB2LB2LA_1LA2RC1LB_---2RB0LB

_  00 <A 11^n 22 _ -> _ <A 11^n+2 _
_   0 <A 11^n 12 _ -> _ <A 22^n+1 1 _
_ 000 <A 11^n 0  _ -> _ <A 22 1 2^2n 1 _

A(a, b, c) = $<A 11^a 22^b 1 2^c 1$

Level 1 (Closed Set):
A(a, b+1, c)    ->  A(a+2, b,   c)
A(a, 0,   c+1)  ->  A(0,   a+1, c)
A(a, 0,   0)    ->  A(0,   1,   2a+2)

Level 2:
A(a, b, c)  ->  A(a+2b, 0, c)
A(a, 0, c+1) -> A(2a+2, 0, c)

Level 3:
A(a, 0, c) -> A((a+2) 2^c - 2, 0, 0)
-> A(0, 1, (a+2) 2^c+1 - 2)
-> A(2, 0, (a+2) 2^c+1 - 2)   [Infinite Rule]

Starts at A(0, 0, 1) @3


And the last TM is extremely similar, but with a small tweak to the A(a, 0, 0) rule.

1RB1LA2LA_1LA2RC1LB_---2RB0LB

_  00 <A 11^n  22 _ -> _ <A 11^n+2 _
_   0 <A 11^n  12 _ -> _ <A 22^n+1 1 _
_  00 <A 11^n+1 0 _ -> _ <A 22 1 2^2n+1 1 _

A(a, b, c) = $<A 11^a 22^b 1 2^c 1$

Level 1 (Closed Set):
A(a, b+1, c)    ->  A(a+2, b,   c)
A(a, 0,   c+1)  ->  A(0,   a+1, c)
A(a, 0,   0)    ->  A(0,   1,   2a+1)

Level 2:
A(a, b, c)  ->  A(a+2b, 0, c)
A(a, 0, c+1) -> A(2a+2, 0, c)

Level 3:
A(a, 0, c) -> A((a+2) 2^c - 2, 0, 0)
-> A(0, 1, (a+2) 2^c+1 - 3)
-> A(2, 0, (a+2) 2^c+1 - 3)   [Infinite Rule]

Starts at A(0, 0, 0) @3


#### 6x2 Mixed Exponential and Add

1RB0RD_0RC0RA_1LD0LC_1LE1LB_0RE0LF_1LA---

$01^a B> 0110 ->$ 01^a+4 B>
$01^2a+2 B> 00 ->$ 01^3 B> 0110^a 011
$01^2a+1 B> 00 ->$ 01^2 B> 110 0110^a 011

B(a, b, c) = $0101^a B> 110 10^b+1 0110^d$
C()

Closed Set:
B(a, b, c+1) -> B(4a+5, b+1, c-1)
B(a, b, 0)   -> B(7, 0, a+2b+2)

Starts in B(7, 0, 3) @405


This proof (by closed set) is complete, but if you try to evaluate the trajectory here, it’s slightly more interesting:

B(7, 0, c) -> B((7 + 5/3) 4^c - 5/3, c, 0)
-> B(7, 0, (26 4^c + 1)/3 + 2c)


So we are recursing the map c -> (26 4^c + 1)/3 + 2c which has both exponential and addition.

#### 6x2 ExpInt close

1RB0RC_1LC1RA_1RE1RD_1LF0RB_---1LA_1LB0LD

Rules:
00^inf 10 11^f 10^g 11^h-1 01^i+2 (01) D> 00^inf
00^inf 10 11^(j - 1) 10^(k + 2) 11^1 01^(2 l + 4) (01) D> 00^inf

11 01^c D> $-> 01^c+2 D>$
11 10^b 01^c D> $-> 10^b+2 11^c 01 D>$
11 01^a A> 10^2 -> 01^a+3 A>

D(a, b, c, d) = $10 11^a 10^b 11^c 01^d D>$

Level 1:
D(a, b, c+1, d) -> D(a, b, c, d+2)
D(a, b, 0, d) -> D(a-1, b+2, d, 1)
D(0, b, 0, d) -> D(3b+5, 3, d-2b-5, 1)   (Assuming d > 2b+5)

Level 2:
D(a, b, c, d) -> D(a, b, 0, d+2c)
D(a, b, 0, d) -> D(a-1, b+2, 0, 2d+1)
D(0, b, 0, d) -> D(3b+5, 3, 0, 2d-4b-9)

Level 3:
D(a, b, 0, d) -> D(0, b+2a, 0, (d+1) 2^a - 1)
D(0, b, 0, d) -> D(0, 6b+13, 0, (d-2b-4) 2^(3b+6) - 1)   [Infinite rule]

Starts at D(0, 0, 3, 1) @35


The last rule is infinite (b/c $$d > b$$ remains true forever), but the sequence produces progressively more and more complicated terms:

D(0, 0, 0, 7)
D(0, 13, 0, 3 2^6 - 1)
D(0, 7*13, 0, (3 2^6 - 31) 2^45 - 1)
D(0, 13(1+6+6^2), 0, ((3 2^6 - 31) 2^45 - 187) 2^279 - 1)


### May 2023

#### Pavel’s BB(2, 6) > 10^^91

1RB3LA4LB0RB1RA3LA_2LA2RA4LA1RA5RB1RZ

This is the current 2x6 champion found by Pavel last month. Like my 10^^70 TM, it seems to have a mix of orderly and chaotic behavior. (As usual, what I am calling chaotic is really just behavior I haven’t been able to make sense of, maybe someone else will be able to make an orderly analysis at some point.)

The orderly behavior is built upon these two rules:

01 11 0211^n B> 00  ->  11 0211^n+1 B>
Repeated: 01^k 11 0211^n B> $-> 11 0211^n+k B>$

01^3 11 01 21 0211^n B> $-> 11 01 21 0211^4n+10 B>$
Repeated: 01^3k+r 11 01 21 0211^n B> $-> 01^r 11 01 21 0211^{((3n+10) 4^k - 10)/3} B>$


Most notably, a single simplification of the last rule basically accounts for all of the 10^^91 growth:

01^3k+r 11 01 21 0211^17 B> $-> 01^r 11 01 21 0211^{(61 4^k - 10)/3} B>$


Which is applied ~90 times thus leading to ~4^^90 score.

Other rules I discovered while analyzing:

Hand Rules:
01 11 0211^n B> 00  ->  11 0211^n+1 B>

01 0211^n B> 00    ->        12 11 0211^n   B>
12 11 0211^n B> 00    ->           21 0211^n+1 B>
12 11 11 0211^n B> 00    ->        21 01 0211^n+1 B>
01 11 02 11 11 0211^n B> 00    ->  11 02 11 01 0211^n+1 B>
01 11^a 02 21 11 0211^n B> 0000  ->    11 01^a+1 0211^n+2 B>
01 1551 11 02 11 11 0211^n B> 00    -> 11 01^2 02 11 01 0211^n+1 B>

01 11^a+1 0211^n B> 00    ->            11 01^a  0211^n+1 B>
0 11 11 0211^n B> 000   ->         11 11 01^2n 0211     B>
1 21 11 0211^n B> 000   ->         21 11 01^2n 0211     B>
0 11^a|1 01 21 0211^n B> 000   ->  11 01^a-1 1551 01^2n 0211     B>

01 01 21 0211^n B> 0000  ->     12 11 01^2n 11 0211 B>
01 11 01 21 0211^n B> 0000  ->  11 02 11 01^2n 11 0211 B>
01 21 21 0211^n B> 0000  ->     11 11 01^2n 11 0211 B>
11 21 0211^n B> 0000  ->        21 01^2n 11 0211 B>

Simplified:
01 11   02 11 11 0211^n B> $-> 11 02 21 11 0211^2n+5 B>$
01 11^a 02 21 11 0211^n B> $-> 11 01^a 21 0211^n+3 B>$
01 1551 11 02 11 11 0211^n B> 00 -> 11 01 21 11 0211^4n+17 B> $01 11^a+2 0211^n B>$  ->  11 01^a 21 0211^n+2  B> $0 11 11 0211^n|3 B>$  ->           11 11  01^2n-5 11 01 21 0211^17 B> $1 21 11 0211^n|3 B>$  ->           21 11  01^2n-5 11 01 21 0211^17 B> $0 11^a|1 01 21 0211^n|3 B>$  ->  11 01^a-1 1551  01^2n-5 11 01 21 0211^17 B> $01 01 21 0211^n B>$  ->        21 21 0211^2n+3 B> $01 11 01 21 0211^n B>$  ->  11 02 11 11 0211^2n+1 B> $01 21 21 0211^n B>$  ->     11 11 11 0211^2n+1 B> $11 21 0211^n B>$  ->        21 11 0211^2n+1 B> $01^3 21 0211^n B>$  ->   11 11 11 0211^4n+7 B> $01^4 21 0211^n B>$  ->   11 01 21 0211^4n+9 B> $01^3 11 01 21 0211^n B>$ -> 11 01 21 0211^4n+10 B> $01^3k 11 01 21 0211^n B>$ -> 11 01 21 0211^{(n+10/3) 4^k - 10/3} B> $Start: 21 0211 B> 11 01^3 11 0211 B> 11 11 0211^4 B> 11 11 01^3 11 01 21 0211^17 B> 11 11 11 01 21 0211^78 B> [@q279] 11 01^2 1551 01^151 11 01 21 0211^17 B> [@q390+s5] 151 = 3 (50) + 1 a = (61 4^50 - 10)/3 11 01^2 1551 01 11 01 21 0211^a B> 11 01^2 1551 11 02 11 11 0211^2a+1 B> 11 01 11 01 21 11 0211^8a+21 B> 11 01 11 0 21 11 01^16a+37 11 01 21 0211^17 B> 4^3 % 9 = 1 52 % 3 = 1 4^52 % 9 = 4^1 61 4^52 - 49 % 9 = 7 4 - 4 % 9 = 24 % 9 = 6 16a+37 = (61 4^52 - 49)/3 = 3 k_a + 2 b = (61 4^k_a - 10)/3 11 01 11 0 21 11 01^2 11 01 21 0211^b B>  But this process doesn’t show any sign of simplifying over time. There may be endlessly many rules like this … ## 2024 ### June 2024 #### Coincidence Collatz 1RB1RD_0LC0RD_1LD1LC_1RA1LE_0RE0RF_1RZ0LC Longest running halter of set of 9 halting TMs shared by @mxdys on 8 June 2024. https://discord.com/channels/960643023006490684/1026577255754903572/1249137796778823760 This took Quick_Sim.py 12 hours and almost 5 billion simulator steps to solve! 1RB1RD_0LC0RD_1LD1LC_1RA1LE_0RE0RF_---0LC A(a, b, c) = 0^inf 11^a 01 11^b A> 1^c 0^inf A(a, b+1, c+2) --> A(a+2, b, c) A(a, b, 0) --> A( 0, a, 2b+3) A(a, b, 1) --> A( a, b+1, 0) A(a, 0, c+7) --> A( 2, a+2, c) A(a, 0, 2) --> A( 0, a+1, 0) A(a, 0, 3) --> A(a+2, 0, 0) A(a, 0, 4) --> Halt(2a+5)$ 11^a+2 00 1 Z> $A(a, 0, 5) --> A( 0, a+3, 0) A(a, 0, 6) --> A( 0, a+4, 0) @61: A(0, 0, 9) =$ 1 A> 1^9 $ The trick here is that this TM reduces both b and c at the same time. If one runs out enough before the other, then it continues, but only when the both “run out” at the same time (b = 0 and 2 <= c < 7) does it have a chance of halting. And then only 1 of 5 remainders leads to halt. Furthermore it gets very lucky and doesn’t hit that 1 of 5 remainders until the 18th try! All iterations where b = 0 and 2 <= c < 7:  36 A( 22, 0, 6) 61 A( 38, 0, 2) 100 A( 56, 0, 3) 431 A( 230, 0, 2) 709 A( 368, 0, 5) 4_115 A( 2_058, 0, 6) 5_987 A( 2_994, 0, 3) 6_060 A( 3_028, 0, 3) 16_028 A( 7_950, 0, 6) 27_428 A( 13_652, 0, 3) 322_000 A( 160_934, 0, 2) 944_198 A( 472_128, 0, 5) 1_778_129 A( 889_264, 0, 5) 5_695_317 A( 2_847_234, 0, 5) 178_941_119 A( 89_468_770, 0, 5) 305_476_095 A(152_733_912, 0, 3) 585_453_777 A(292_712_846, 0, 4) Halted: Score: 585_425_697  Final config: 00^inf 01^1 11^292_712_847 10^1 (01) Z> 00^inf  #### BB(6, 2, -1) Step Champ AFAICT this is the current BB6 (with one unfilled transition) step champion: https://bbchallenge.org/1RB1RA_1LC1RF_1RE1LD_0RD1LB_—0RA_1RZ0LE 1RB1RA_1LC1RF_1RE1LD_0RD1LB_---0RA_1RZ0LE Steps: ~10^13.39223 = 24_673_582_891_560 Nonzeros: 2_323_223 = 2_323_223 C(a, b, c) =$ 1^a 0 1^b <C 1^2c+1 $C(a, b+3, c) -> C(a, b, c+2) C(a, 0, c) -> C(a+1, 2c+1, 0) C(a, 1, c) -> C(0, a, c+1) C(0, 2, c) -> C(1, 2c+4, 0) C(1, 2, c) -> C(1, 2c+6, 0) C(2, 2, c) -> C(1, 2c+7, 0) C(a+3, 2, c) -> 1^a 01^c+3 11 Z> @2: C(0, 1, 0)  It does one of these interesting Collatz Markov Chains where it only halts if a>=3 and b%3 = 2 and otherwise has a couple ways to reset a <= 1. But eventually after flipping that coin 62 times it finally halts.  0 A( 0, 1, 0) 1 A( 0, 0, 1) 2 A( 1, 3, 0) 3 A( 2, 5, 0) 4 A( 1, 11, 0) 5 A( 1, 18, 0) 6 A( 2, 25, 0) 7 A( 0, 2, 17) 8 A( 1, 38, 0) 9 A( 1, 54, 0) 10 A( 2, 73, 0) 11 A( 0, 2, 49) 12 A( 1, 102, 0) 13 A( 2, 137, 0) ... 58 A( 3, 1_470_157, 0) 59 A( 0, 3, 980_105) 60 A( 1, 1_960_215, 0) 61 A( 2, 2_613_621, 0) 62 A( 3, 3_484_829, 0) Halted: 62 2_323_223  Most of the other top BB(6, 2, -1) TMs are closely related and seem to harness basically the same process judging by the scores being all equal. 1RB1RA_1LC1RF_1RE1LD_0RD1LB_---0RA_---0LE Halt 24_673_582_891_560 2_323_223 B: 1RB1LF_1LC1RE_---0LD_1LA1LD_0LE1RA_---0RC Halt ~10^13.4 2_323_223 D0->1LC: 1RB1RA_1LC1RF_1RE1LD_1LC1LB_---0RA_---0LE Halt ~10^13.3 2_323_223 B: 1RB1LF_1LC1RE_---0LD_1LA1LD_1RB1RA_---0RC Halt ~10^13.3 2_323_223 D: 1RB1RE_1LC1RA_---0LD_1LE1LD_1RB1LF_---0RC Halt ~10^13.3 2_323_223 B1->0RF F1->1RB: 1RB1RA_1LC0RF_1RE1LD_0RD1LB_---0RA_---1RB Halt ~10^13.3 2_323_222 B: 1RB0LF_1LC1RE_---0LD_1LA1LD_0LE1RA_---1LA Halt ~10^13.3 2_323_222 D0->1LC: 1RB1RA_1LC0RF_1RE1LD_1LC1LB_---0RA_---1RB Halt ~10^13.1 2_323_222 B: 1RB0LF_1LC1RE_---0LD_1LA1LD_1RB1RA_---1LA Halt ~10^13.1 2_323_222 D0->1LE: 1RB0LF_1LC1RE_---0LD_1LE1LD_1RB1RA_---1LA Halt ~10^13.1 2_323_222 1RB1RA_1LC1LE_1RD1LB_---0RA_1LC0RF_---1RE Halt ~10^13.1 2_323_222 1RB1RE_1LC1RA_---0LD_1LA1LD_1RB0LF_---1LE Halt ~10^13.1 2_323_222 D: 1RB1RE_1LC1RA_---0LD_1LE1LD_1RB0LF_---1LE Halt ~10^13.1 2_323_222  #### BB(6, 2, -1) Score Champ BB6 (with one unfilled transition) score champion: https://bbchallenge.org/1RB0RC_1LC1LF_1RD0LB_—0LE_—1RA_1LB0RE 1RB0RC_1LC1LF_1RD0LB_---0LE_---1RA_1LB0RE Steps: ~10^13.15788 = 14_384_000_997_114 Nonzeros: 4_059_761 = 4_059_761 A(a, b, c) =$ 01^a A> 1^b 0 1^c \$

A(a, b+3, c) -> A(a+4, b, c)  if a >= 1

A(a, 0, 0) -> A(2, 2a-1, 1)   if a >= 1
A(a, 0, c+1) -> A(a+1, c, 0)
A(a, 2, c) -> A(2, 2a+5, c+1)

A(a, 1, 0) -> Halt(a+2)
A(a, 1, 1) -> A(2, 2a+1, 1)
A(a, 1, 2) -> A(2, 2a+3, 1)
A(a, 1, 3) -> Halt(a+4)
A(a, 1, c+4) -> A(a+5, 0, c)

@20: A(2, 1, 2)

   0  A(          2,           1,           2)
1  A(          2,           7,           1)
2  A(          2,          21,           1)
3  A(         31,           0,           0)
4  A(          2,          61,           1)
5  A(          2,         165,           1)
6  A(        223,           0,           0)
7  A(          2,         445,           1)
8  A(          2,       1_189,           1)
9  A(          2,       3_173,           1)
10  A(          2,       8_465,           2)
11  A(          2,      22_577,           3)
12  A(          2,      60_209,           4)
13  A(          2,     160_561,           5)
14  A(    214_087,           0,           1)
15  A(    214_088,           0,           0)
16  A(          2,     428_175,           1)
17  A(    570_903,           0,           0)
18  A(          2,   1_141_805,           1)
19  A(          2,   3_044_817,           2)
20  A(  4_059_759,           1,           0)
Halted:           20    4_059_761


This one has a sibling too:

1RB0RC_1LC1LF_1RD0LB_---0LE_---1RA_1LB0RE Halt 14_384_000_997_114 4_059_761
D1->1RB (E <-> F):
1RB0RC_1LC1LE_1RD0LB_---1RB_1LB0RF_---1RA Halt 14_383_991_253_724 4_059_761