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

\[\text{B>} \; 121 \; 0^\infty \; \to \; 3 \; \text{<A} \; 231 \; 0^\infty\]

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))))))))))))))))))))))))))))))))))))))))