BB(2, 6) > 10↑↑70
Update(29 Apr 2023): Pavel strikes again! He announced a 2x6 TM running for > 10↑↑91 steps.
It’s approaching one year since the discovery that \(BB(6, 2) > 10 \uparrow\uparrow 15\) and I finally got a chance to update my code to actually simulate machines like this (where you must store integers as formula instead of directly in binary). Unsurprisingly, I don’t have any new BB(6, 2)
champions to share (Pavel searched well!), but I also did a search of BB(2, 6)
and found a couple exciting machines!
The Machines
The two TMs in Standard Text format:
Name | TM | Score Bound |
---|---|---|
t70 |
1RB2LA1RA4LA5RA0LB_1LA3RA2RB1RZ3RB4LA |
\(> 10 \uparrow\uparrow 70.27\) |
t69 |
1RB2LB1RZ3LA2LA4RB_1LA3RB4RB1LB5LB0RA |
\(> 10 \uparrow\uparrow 69.68\) |
Written out fully these are: t70
:
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
A | 1RB | 2LA | 1RA | 4LA | 5RA | 0LB |
B | 1LA | 3RA | 2RB | 1RZ | 3RB | 4LA |
with precise score (number of non-zeros left on tape at halt):
\[\sigma(\text{t70}) = 14 + 2^{ -1 + 2^{ 2 + 2^{ 1 + 2^{ -1 + 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 3 + 2^{ 2^{ 3 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ 3 + 2^{ 2^{ -1 + 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 1 + 2^{ 1 + 2^{ -1 + 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^8 } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }\]And t69
:
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
A | 1RB | 2LB | 1RZ | 3LA | 2LA | 4RB |
B | 1LA | 3RB | 4RB | 1LB | 5LB | 0RA |
with precise score:
\[\sigma(\text{t69}) = 14 + 2^{ -1 + 2^{ 2 + 2^{ 1 + 2^{ -1 + 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 3 + 2^{ 2^{ 3 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ 3 + 2^{ 2^{ -1 + 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ -1 + 2^{ 2^{ 1 + 2^{ 1 + 2^{ -1 + 2^{ 4 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^{ 2^{ 2 + 2^{ 2^{ -1 + 2^{ 2^{ 2 + 2^4 } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }\]TM Siblings
The keep eyed observer will note that these scores are identical except for the very top exponent (which is 8 vs. 4). In fact, these two machine are just “permutation” of each other. That is to say, if you take the first machine and swap the two states and then put it into TNF you will get the second machine (and vice versa).
Analysis
I happened to find and analyze t69
first, so I will use it’s state and symbol naming for this analysis. For t70
, I will consider it to be t69
started in state B
.
For this analysis, I break the tape up into a “left” and “right” side. The left side is always of the form \(0^\infty \; 3^n\) or \(0^\infty \; 1 \; 3^n\) and here are the rules for simulating the left side tape:
\[\begin{array}{l} 0^\infty & & 3^{n} & \text{<B} & \to & 0^\infty & 1 & 3^{n+1} & \text{B>} \\ 0^\infty & 1 & 3^{n} & \text{<B} & \to & 0^\infty & & 3^{n+1} & \text{B>} \\ \\ 0^\infty & & 3^{2k} & \text{<A} & \to & 0^\infty & 1 & 3^{4k} & \text{B>} \\ 0^\infty & & 3^{2k+1} & \text{<A} & \to & 0^\infty & & 3^{4k+2} & \text{B>} \\ \\ 0^\infty & 1 & 3^{n} & \text{<A} & \to & 0^\infty & 1 & 3^{4(2^n - 1)} & \text{B>} & 12 \\ \end{array}\]The right side is a bit more chaotic and I have not yet found any particularly useful abstraction for it. But, interestingly, we don’t need to provide any abstraction for the right side because using the above rules and then just manually simulating the right side we can simulate this TM to halting in only 175 iterations.
0 : 1 3^4 B> 121
1 : 1 3^124 B> 12231
2 : 3^125 B> 15511
3 : 3^254 B> 1231
4 : 1 3^255 B> 1511
5 : 1 3^~10^77.7 B> 12121
6 : 1 3^~10↑↑3.28 B> 1223231
...
173 : 1 3^~10↑↑69.28 B> 12515223232121231
174 : 1 3^~10↑↑70.28 B> 122125223232121231
HALT (14 + 2^(-1 + 2^(2 + 2^(1 + 2^(-1 + 2^(4 + 2^2^(-1 + 2^2^(2 + 2^2^(2 + 2^2^(-1 + 2^2^(-1 + 2^2^(3 + 2^2^(3 + 2^2^(2 + 2^2^(-1 + 2^2^(-1 + 2^2^(2 + 2^2^(4 + 2^2^(-1 + 2^2^(2 + 2^2^(2 + 2^2^(-1 + 2^2^(3 + 2^2^(-1 + 2^(4 + 2^2^(-1 + 2^2^(-1 + 2^2^(-1 + 2^2^(4 + 2^2^(-1 + 2^2^(-1 + 2^2^(1 + 2^(1 + 2^(-1 + 2^(4 + 2^2^(-1 + 2^2^(2 + 2^2^(2 + 2^2^(-1 + 2^2^(2 + 2^8))))))))))))))))))))))))))))))))))))))))
(See the end of this article for the full trajectory)
As a short explanation for this analysis: t70
starts in config \(0^\infty \; 1 \; 3^4 \; B> \; 121 \; 0^\infty\) at step 33. In order to simulate one iteration, we simulate the TM manually on the right side until it comes back to the left side (or halts). So, for example, the first iteration takes
Then I apply the appropriate left side rule from above. For example, the first iteration takes
\[0^\infty \; 1 \; 3^{5} \; \text{<A} \; \to \; 0^\infty \; 1 \; 3^{4(2^5 - 1)} \; \text{B>} \; 12\]Combining these together we get:
\[\begin{array}{l} 0^\infty & 1 & 3^{4} & \text{ B>} & 121 & 0^\infty & \to \\ 0^\infty & 1 & 3^{5} & \text{<A } & 231 & 0^\infty & \to \\ 0^\infty & 1 & 3^{4(2^5 - 1)} & \text{ B>} & 12 \; 231 & 0^\infty \\ \end{array}\]which is exactly the first iteration above. The trajectory for t69
is identical except that it starts with config 1 3^0 B> 121
at step 5.
A Non-Collatz Champions?
This analysis is really different than most other BB champion analyses I’ve shared. Specifically, most of those analyses have basically reduced the TM to a simulation of Collatz-like rules and then the question of halting was simplified to whether or not the Collatz-like rules halt. Pascal Michel has written extensively about how almost all current and former Busy Beaver champions have Collatz-like Behavior.
For Pavel’s reigning BB(6, 2) champion, simulating these Collatz-like rules turned out to require non-trivial Mathematical theorems in order to evaluate \(3^n \pmod{2^m}\). In contrast, in order to simulate t70
you only need to know how to evaluate \(2^n \pmod{2}\)!
This TM does have one Collatz-like rule:
\[\begin{array}{l} 0^\infty & & 3^{2k} & \text{<A} & \to & 0^\infty & 1 & 3^{4k} & \text{B>} \\ 0^\infty & & 3^{2k+1} & \text{<A} & \to & 0^\infty & & 3^{4k+2} & \text{B>} \\ \end{array}\]And furthermore, I have not really provided any sort of theory to explain the behavior of this TM on arbitrary right sides. So perhaps there is more “Collatz-like behavior” on that side.
But overall, it doesn’t seem to me that it’s behavior is “driven” by Collatz-like behavior. Instead, to me, it seems that it simulates relatively chaotic behavior which occasionally applies the function \(n \mapsto 4(2^n - 1)\). That function is applied 69 times before the TM halts and so we end up with a score around \(10 \uparrow\uparrow 69\).
Appendix
Full Trajectory
The full simulation trajectory for t70
is:
0 : 1 3^4 B> 121
1 : 1 3^124 B> 12231
2 : 3^125 B> 15511
3 : 3^254 B> 1231
4 : 1 3^255 B> 1511
5 : 1 3^~10^77.7 B> 12121
6 : 1 3^~10↑↑3.28 B> 1223231
7 : 3^~10↑↑3.28 B> 1551231
8 : 1 3^~10↑↑3.28 B> 151511
9 : 1 3^~10↑↑4.28 B> 1212511
10 : 1 3^~10↑↑5.28 B> 12232121
11 : 3^~10↑↑5.28 B> 15512121
12 : 3^~10↑↑5.28 B> 1223231
13 : 1 3^~10↑↑5.28 B> 1551231
14 : 1 3^~10↑↑6.28 B> 12151511
15 : 1 3^~10↑↑7.28 B> 122312511
16 : 3^~10↑↑7.28 B> 155112511
17 : 3^~10↑↑7.28 B> 1232121
18 : 1 3^~10↑↑7.28 B> 1512121
19 : 1 3^~10↑↑8.28 B> 12122121
20 : 1 3^~10↑↑9.28 B> 1223223231
21 : 3^~10↑↑9.28 B> 1551223231
22 : 1 3^~10↑↑9.28 B> 151551231
23 : 1 3^~10↑↑10.28 B> 1212551231
24 : 1 3^~10↑↑11.28 B> 12232151511
25 : 3^~10↑↑11.28 B> 15512151511
26 : 3^~10↑↑11.28 B> 122312511
27 : 1 3^~10↑↑11.28 B> 155112511
28 : 1 3^~10↑↑12.28 B> 121232121
29 : 3^~10↑↑12.28 B> 151512121
30 : 1 3^~10↑↑12.28 B> 12512121
31 : 1 3^~10↑↑13.28 B> 122122121
32 : 1 3^~10↑↑14.28 B> 12223223231
33 : 3^~10↑↑14.28 B> 15551223231
34 : 3^~10↑↑14.28 B> 125551231
35 : 3^~10↑↑14.28 B> 23125511
36 : 1 3^~10↑↑14.28 B> 51125511
37 : 1 3^~10↑↑15.28 B> 1212125511
38 : 1 3^~10↑↑16.28 B> 122323231231
39 : 3^~10↑↑16.28 B> 155123231231
40 : 1 3^~10↑↑16.28 B> 15151231231
41 : 1 3^~10↑↑17.28 B> 121251231231
42 : 1 3^~10↑↑18.28 B> 1223212231231
43 : 3^~10↑↑18.28 B> 1551212231231
44 : 1 3^~10↑↑18.28 B> 151515511231
45 : 1 3^~10↑↑19.28 B> 1212515511231
46 : 1 3^~10↑↑20.28 B> 12232125511231
47 : 3^~10↑↑20.28 B> 15512125511231
48 : 3^~10↑↑20.28 B> 122321511511
49 : 1 3^~10↑↑20.28 B> 155121511511
50 : 1 3^~10↑↑21.28 B> 121223121511
51 : 3^~10↑↑21.28 B> 151551121511
52 : 1 3^~10↑↑21.28 B> 12551121511
53 : 1 3^~10↑↑22.28 B> 122312323121
54 : 3^~10↑↑22.28 B> 155112323121
55 : 1 3^~10↑↑22.28 B> 15115123121
56 : 1 3^~10↑↑23.28 B> 121215123121
57 : 1 3^~10↑↑24.28 B> 1223231223121
58 : 3^~10↑↑24.28 B> 1551231223121
59 : 1 3^~10↑↑24.28 B> 151511223121
60 : 1 3^~10↑↑25.28 B> 1212511223121
61 : 1 3^~10↑↑26.28 B> 12232121223121
62 : 3^~10↑↑26.28 B> 15512121223121
63 : 1 3^~10↑↑26.28 B> 1515151551121
64 : 1 3^~10↑↑27.28 B> 12125151551121
65 : 1 3^~10↑↑28.28 B> 122321251551121
66 : 3^~10↑↑28.28 B> 155121251551121
67 : 3^~10↑↑28.28 B> 1223212551121
68 : 1 3^~10↑↑28.28 B> 1551212551121
69 : 1 3^~10↑↑29.28 B> 12122323123231
70 : 3^~10↑↑29.28 B> 15155123123231
71 : 1 3^~10↑↑29.28 B> 1255123123231
72 : 1 3^~10↑↑30.28 B> 12215151123231
73 : 1 3^~10↑↑31.28 B> 122231251123231
74 : 3^~10↑↑31.28 B> 155511251123231
75 : 1 3^~10↑↑31.28 B> 122323212123231
76 : 3^~10↑↑31.28 B> 155123212123231
77 : 1 3^~10↑↑31.28 B> 15151212123231
78 : 1 3^~10↑↑32.28 B> 121251212123231
79 : 1 3^~10↑↑33.28 B> 1223212212123231
80 : 3^~10↑↑33.28 B> 1551212212123231
81 : 1 3^~10↑↑33.28 B> 151515515151231
82 : 1 3^~10↑↑34.28 B> 1212515515151231
83 : 1 3^~10↑↑35.28 B> 12232125515151231
84 : 3^~10↑↑35.28 B> 15512125515151231
85 : 3^~10↑↑35.28 B> 122323121251231
86 : 1 3^~10↑↑35.28 B> 155123121251231
87 : 1 3^~10↑↑36.28 B> 1215151121251231
88 : 1 3^~10↑↑37.28 B> 12231251121251231
89 : 3^~10↑↑37.28 B> 15511251121251231
90 : 3^~10↑↑37.28 B> 123212121251231
91 : 1 3^~10↑↑37.28 B> 151212121251231
92 : 1 3^~10↑↑38.28 B> 1212212121251231
93 : 1 3^~10↑↑39.28 B> 12232232323212231
94 : 3^~10↑↑39.28 B> 15512232323212231
95 : 1 3^~10↑↑39.28 B> 1515512323212231
96 : 1 3^~10↑↑40.28 B> 12125512323212231
97 : 1 3^~10↑↑41.28 B> 122321515123212231
98 : 3^~10↑↑41.28 B> 155121515123212231
99 : 3^~10↑↑41.28 B> 1223125123212231
100 : 1 3^~10↑↑41.28 B> 1551125123212231
101 : 1 3^~10↑↑42.28 B> 1212321223212231
102 : 3^~10↑↑42.28 B> 1515121223212231
103 : 1 3^~10↑↑42.28 B> 125121223212231
104 : 1 3^~10↑↑43.28 B> 1221221223212231
105 : 3^~10↑↑43.28 B> 1551551551212231
106 : 3^~10↑↑43.28 B> 12312151515511
107 : 1 3^~10↑↑43.28 B> 15112151515511
108 : 1 3^~10↑↑44.28 B> 121212151515511
109 : 1 3^~10↑↑45.28 B> 1223232312515511
110 : 3^~10↑↑45.28 B> 1551232312515511
111 : 1 3^~10↑↑45.28 B> 151512312515511
112 : 1 3^~10↑↑46.28 B> 1212512312515511
113 : 1 3^~10↑↑47.28 B> 12232122312515511
114 : 3^~10↑↑47.28 B> 15512122312515511
115 : 1 3^~10↑↑47.28 B> 1515155112515511
116 : 1 3^~10↑↑48.28 B> 12125155112515511
117 : 1 3^~10↑↑49.28 B> 122321255112515511
118 : 3^~10↑↑49.28 B> 155121255112515511
119 : 3^~10↑↑49.28 B> 1223231232125511
120 : 1 3^~10↑↑49.28 B> 1551231232125511
121 : 1 3^~10↑↑50.28 B> 12151511232125511
122 : 1 3^~10↑↑51.28 B> 122312511232125511
123 : 3^~10↑↑51.28 B> 155112511232125511
124 : 3^~10↑↑51.28 B> 1232121232125511
125 : 1 3^~10↑↑51.28 B> 1512121232125511
126 : 1 3^~10↑↑52.28 B> 12122121232125511
127 : 3^~10↑↑52.28 B> 15155151512125511
128 : 1 3^~10↑↑52.28 B> 1255151512125511
129 : 1 3^~10↑↑53.28 B> 12231212512125511
130 : 3^~10↑↑53.28 B> 15511212512125511
131 : 3^~10↑↑53.28 B> 123232122125511
132 : 1 3^~10↑↑53.28 B> 151232122125511
133 : 1 3^~10↑↑54.28 B> 1212232122125511
134 : 3^~10↑↑54.28 B> 1515512122125511
135 : 1 3^~10↑↑54.28 B> 125512122125511
136 : 1 3^~10↑↑55.28 B> 12231223223231231
137 : 3^~10↑↑55.28 B> 15511223223231231
138 : 1 3^~10↑↑55.28 B> 1511551223231231
139 : 1 3^~10↑↑56.28 B> 12121551223231231
140 : 1 3^~10↑↑57.28 B> 122323151551231231
141 : 3^~10↑↑57.28 B> 155123151551231231
142 : 1 3^~10↑↑57.28 B> 15151151551231231
143 : 1 3^~10↑↑58.28 B> 121251151551231231
144 : 1 3^~10↑↑59.28 B> 1223212151551231231
145 : 3^~10↑↑59.28 B> 1551212151551231231
146 : 3^~10↑↑59.28 B> 12232312551231231
147 : 1 3^~10↑↑59.28 B> 15512312551231231
148 : 1 3^~10↑↑60.28 B> 121515112551231231
149 : 1 3^~10↑↑61.28 B> 1223125112551231231
150 : 3^~10↑↑61.28 B> 1551125112551231231
151 : 3^~10↑↑61.28 B> 12321212551231231
152 : 1 3^~10↑↑61.28 B> 15121212551231231
153 : 1 3^~10↑↑62.28 B> 121221212551231231
154 : 1 3^~10↑↑63.28 B> 1223223232151511231
155 : 3^~10↑↑63.28 B> 1551223232151511231
156 : 1 3^~10↑↑63.28 B> 151551232151511231
157 : 1 3^~10↑↑64.28 B> 1212551232151511231
158 : 1 3^~10↑↑65.28 B> 12232151512151511231
159 : 3^~10↑↑65.28 B> 15512151512151511231
160 : 3^~10↑↑65.28 B> 122312512151511231
161 : 1 3^~10↑↑65.28 B> 155112512151511231
162 : 1 3^~10↑↑66.28 B> 121232122151511231
163 : 3^~10↑↑66.28 B> 151512122151511231
164 : 1 3^~10↑↑66.28 B> 12512122151511231
165 : 1 3^~10↑↑67.28 B> 122122122151511231
166 : 1 3^~10↑↑68.28 B> 1222322322312511231
167 : 3^~10↑↑68.28 B> 1555122322312511231
168 : 3^~10↑↑68.28 B> 12555122312511231
169 : 3^~10↑↑68.28 B> 2312555112511231
170 : 1 3^~10↑↑68.28 B> 5112555112511231
171 : 1 3^~10↑↑69.28 B> 121212555112511231
172 : 3^~10↑↑69.28 B> 151515223232121231
173 : 1 3^~10↑↑69.28 B> 12515223232121231
174 : 1 3^~10↑↑70.28 B> 122125223232121231
HALT (14 + 2^(-1 + 2^(2 + 2^(1 + 2^(-1 + 2^(4 + 2^2^(-1 + 2^2^(2 + 2^2^(2 + 2^2^(-1 + 2^2^(-1 + 2^2^(3 + 2^2^(3 + 2^2^(2 + 2^2^(-1 + 2^2^(-1 + 2^2^(2 + 2^2^(4 + 2^2^(-1 + 2^2^(2 + 2^2^(2 + 2^2^(-1 + 2^2^(3 + 2^2^(-1 + 2^(4 + 2^2^(-1 + 2^2^(-1 + 2^2^(-1 + 2^2^(4 + 2^2^(-1 + 2^2^(-1 + 2^2^(1 + 2^(1 + 2^(-1 + 2^(4 + 2^2^(-1 + 2^2^(2 + 2^2^(2 + 2^2^(-1 + 2^2^(2 + 2^8))))))))))))))))))))))))))))))))))))))))