BBB Complex Collatzlike Behavior
Almost all existing Busy Beaver champions (and runner ups) exhibit Collatzlike behavior. Pascal Michel has a large collection of these analyses for existing and previous BB champions. I previously analyzed the BBB(4, 2) champion (it is still the reigning champion 7 months later) which fit into the Collatzlike model in a pleasingly simple way. Today, I’ll be analyzing my newly discovered BBB(5, 2) champion which runs for over 10^{502} steps before quasihalting. This machine exhibits more complex behavior, but still, it is not “Spaghetti Code”.
The Machine
0  1  

A  1RB  1LC 
B  1RC  0RD 
C  0LB  0RC 
D  0RE  1RD 
E  1LE  1LA 
1RB 1LC 1RC 0RD 0LB 0RC 0RE 1RD 1LE 1LA
As discussed in my announcement, it runs > 10^{502} steps before quasihalting. At that number of steps (> a googol^{5}) it is impossible to simulate directly. The only option we have for analyzing this machine is by finding patterns in it’s behavior that allow us to exponentially accelerate our simulation of it.
Rule Steps
I will jump straight into defining the “Rule Steps” of this machine. For a more stepbystep discussion of how we get to rule steps, including the description of tape compression notation and chain steps, please read my original article: “Collatzlike behavior of Busy Beavers”.
Common Configuration
This analysis will be built around a common configuration:
... 1^{n} <E 1^{m} 0^{∞}
which appears again and again as this TM runs. Note that this is only a partial tape specification, there could be many different patterns in the ...
section (we’ll dig more into that later in the “Remainder Rules” section). As a shorthand, we will denote this partial configuration as:
f(n, m) = 1^{n} <E 1^{m} 0^{∞}
So, for example, 0^{∞} 11101110 f(n, m)
would denote the full configuration 0^{∞} 11101110 1^{n} <E 1^{m} 0^{∞}
.
The Basic Rule
f(n+3, m)
> f(n, m+5)
in 2m + 15
steps.
Proof:
Step #  Left tape  State  Right tape 

0  1^{n+3}  <E  1^{m} 0^{∞} 
1  1^{n+2}  <A  1^{m+1} 0^{∞} 
2  1^{n+1}  <C  1^{m+2} 0^{∞} 
3  1^{n} 0  C>  1^{m+2} 0^{∞} 
m + 5  1^{n} 0^{m+3}  C>  0^{∞} 
m + 6  1^{n} 0^{m+3}  <B  0^{∞} 
m + 7  1^{n} 0^{m+2} 1  C>  0^{∞} 
m + 8  1^{n} 0^{m+2} 1  <B  0^{∞} 
m + 9  1^{n} 0^{m+3}  D>  0^{∞} 
m + 10  1^{n} 0^{m+4}  E>  0^{∞} 
m + 11  1^{n} 0^{m+4}  <E  1 0^{∞} 
2m + 15  1^{n}  <E  1^{m+5} 0^{∞} 
If you were to jump to any random point in the execution of this TM, you would almost certainly see it in the middle of evaluating this specific rule. It goes through eating 3 1
s from the left and adding 5 1
s to the right and repeats until the number of 1
s on the left gets to be less than 3.
Repeating Basic Rule
As with the BBB(4, 2) analysis, we can repeatedly apply this rule an arbitrary number of times in one simulator step. Specifically, we have a new rule:
f(3k + r, m)
> f(r, m + 5k)
Remainder Rules
OK, but what happens when n < 3
? Well now we have to consider the details of what’s in the ...
section on the left side of the tape.
Case n = 1
0 f(1, m)
> 10 f(m, 2)
in m + 6
steps.
Proof:
Step #  Left tape  State  Right tape 

0  0 1  <E  1^{m} 0^{∞} 
1  0  <A  1^{m+1} 0^{∞} 
2  1  B>  1^{m+1} 0^{∞} 
3  1 0  D>  1^{m} 0^{∞} 
m + 3  1 0 1^{m}  D>  0^{∞} 
m + 4  1 0 1^{m} 0  E>  0^{∞} 
m + 5  1 0 1^{m} 0  <E  1 0^{∞} 
m + 6  1 0 1^{m}  <E  1^{2} 0^{∞} 
Case n = 2
00 f(2, m)
> 010 f(m+1, 2)
in m + 14
steps.
Proof:
Step #  Left tape  State  Right tape 

0  0 0 1 1  <E  1^{m} 0^{∞} 
1  0 0 1  <A  1^{m+1} 0^{∞} 
2  0 0  <C  1^{m+2} 0^{∞} 
3  0  <B  0 1^{m+2} 0^{∞} 
4  1  C>  0 1^{m+2} 0^{∞} 
5  1  <B  0 1^{m+2} 0^{∞} 
6  0  D>  0 1^{m+2} 0^{∞} 
7  0 0  E>  1^{m+2} 0^{∞} 
8  0 0  <A  1^{m+2} 0^{∞} 
9  0 1  B>  1^{m+2} 0^{∞} 
10  0 1 0  D>  1^{m+1} 0^{∞} 
m + 11  0 1 0 1^{m+1}  D>  0^{∞} 
m + 12  0 1 0 1^{m+1} 0  E>  0^{∞} 
m + 13  0 1 0 1^{m+1} 0  <E  1 0^{∞} 
m + 14  0 1 0 1^{m+1}  <E  1^{2} 0^{∞} 
10 f(2, m)
> 010 f(m+1, 2)
in m + 12
steps.
Proof:
Step #  Left tape  State  Right tape 

0  1 0 1 1  <E  1^{m} 0^{∞} 
1  1 0 1  <A  1^{m+1} 0^{∞} 
2  1 0  <C  1^{m+2} 0^{∞} 
3  1  <B  0 1^{m+2} 0^{∞} 
4  0  D>  0 1^{m+2} 0^{∞} 
5  0 0  E>  1^{m+2} 0^{∞} 
6  0 0  <A  1^{m+2} 0^{∞} 
7  0 1  B>  1^{m+2} 0^{∞} 
8  0 1 0  D>  1^{m+1} 0^{∞} 
m + 9  0 1 0 1^{m+1}  D>  0^{∞} 
m + 10  0 1 0 1^{m+1} 0  E>  0^{∞} 
m + 11  0 1 0 1^{m+1} 0  <E  1 0^{∞} 
m + 12  0 1 0 1^{m+1}  <E  1^{2} 0^{∞} 
Case n = 0
0 f(0, m)
> f(0, m+1)
in 1 step
Proof:
Step #  Left tape  State  Right tape 

0  0 
<E  1^{m} 0^{∞} 
1  <E  1^{m+1} 0^{∞} 
As a result, notice that this means that if we are in configuration:
0^{∞} f(0, m)
= 0^{∞} <E 1^{m} 0^{∞}
That means that the machine has reached Chain Recurrence and it will remain in state E
forever after, moving left, writing 1
s (because of transition E0 > 1LE
).
Final Case
Finally, note that
1 f(n, m)
= 1 1^{n} <E 1^{m} 0^{∞}
= f(n+1, m)
Collatzlike Function
Collecting all these rules together we get:
f(3k + r, m)
>f(r, m + 5k)
1 f(n, m)
=f(n+1, m)
0 f(1, m)
>10 f(m, 2)
00 f(2, m)
>010 f(m+1, 2)
10 f(2, m)
>010 f(m+1, 2)

0 f(0, m)
>f(0, m+1)
0^{∞} h(0, m)
> Quasihalt
We can simplify this a bit by combining the first rule into the rest to get:
1 f(n, m)
=f(n+1, m)
0 f(3k + 1, m)
>10 f(5k + m, 2)
00 f(3k + 2, m)
>010 f(5k + m + 1, 2)
10 f(3k + 2, m)
>010 f(5k + m + 1, 2)
0 f(3k, m)
>f(0, 5k + m + 1)
It turns out we can even codify this further in order to completely convert it into a Collatzlike function. Specifically, consider the general configuration:
g(x, n, m)
= 0^{∞} bin(x) 1^{n} <E 1^{m} 0^{∞}
= 0^{∞} bin(x) f(n, m)
where bin(x)
means writing x
in binary in the standard bigendian notation (most significant bit on left, least significant bit on right). Ex: bin(18)
= 10010
.
It might not be at first clear why we are using binary encoding here. But consider what happens when we consider an example:
g(2x, 3k + 1, m)
= 0^{∞} bin(2x) f(3k + 1, m)
= 0^{∞} bin(x) 0 f(3k + 1, m)
> 0^{∞} bin(x) 10 f(5k + m, 2)
= 0^{∞} bin(4x+2) f(5k + m, 2)
= g(4x+2, 5k + m, 2)
So, in fact, each of the rules above can be converted completely into this g
context:
g(2x+1, n, m)
=g(x, n+1, m)
g(2x, 3k + 1, m)
>g(4x+2, 5k + m, 2)
g(4x, 3k + 2, m)
>g(8x + 2, 5k + m + 1, 2)
g(4x + 2, 3k + 2, m)
>g(8x + 2, 5k + m + 1, 2)
g(0, 3k, m)
> Quasihaltg(2x, 3k, m)
>g(x, 0, 5k + m + 1)
Collatz Orbit from Blank Tape
Starting our TM from a blank tape at step 8 it is in configuration:
0^{∞} 1^{1} <E 1^{3} 0^{∞}
= g(0, 1, 3)
Starting from this point the orbit of the Collatz function is:
# Iterations  Configuration 

0  g(0, 1, 3) 
1  g(2, 3, 2) 
2  g(1, 0, 8) 
3  g(0, 1, 8) 
4  g(2, 8, 2) 
…  … 
2257  g(14, 3, ~2.4 × 10^{251}) 
2258  g(7, 0, ~2.4 × 10^{251}) 
2259  g(3, 1, ~2.4 × 10^{251}) 
2260  g(1, 2, ~2.4 × 10^{251}) 
2261  g(0, 3, ~2.4 × 10^{251}) 
2262  Quasihalt 
In other words, we iterate this function 2262
times before the machine Quasihalts.
Intuition
In a way, I am done now. I have given you a precise Collatzlike function which exactly simulates this TM … but what is really going on here? In general, it feels like the value of having a Collatz analysis is that it sheds some light on what the TM is “actually doing”. But (at least for me) seeing the definition of this g
and the 2262 iterations it takes to Quasihalt is not especially illuminating. Instead I actually find the definition of f
to be more helpful in understanding what this machine “does”. Let me restate the f
rules in yet another way:
f(3k + r, m)
>f(r, m + 5k)
0 f(1, m)
>10 f(m, 2)
?0 f(2, m)
>010 f(m+1, 2)
(for?
either0
or1
)0 1^{a} 0^{b} f(0, m)
>0 f(a, m+b)
0^{∞} f(0, m)
> Quasihalt
So, we repeatedly iterate a Collatzlike function on (n, m)
doing something different with the left side of the tape depending on the remainder of n
mod 3. If the remainder is 1
or 2
, then we expand the size of the left side of the tape by 1 symbol (0 > 10
or ?0 > 010
). If the remainder is 0
, then we reduce the size of the left side of the tape. In order to quasihalt, the TM must reduce the left side of the tape down to empty and then have a remainder of 0
. The question is, will the left side of the tape be reduced to empty and have remainder 0
for n
? Or will it grow endlessly?
By looking at the details of this specific orbit, it appears that these two forces (growth and reduction) are pretty evenly balanced. The tape grows a lot at first and then stays long for thousands of iterations before finally crashing down to empty.
See here, for example, where I show only the iterations where n < 3
(just the remainder).
Iteration #  Left Tape  n  m 

0  1  3  
1  1 
0  7 
2  1  8  
3  1 
2  12 
4  01 
1  22 
5  011 
1  37 
6  0111 
1  62 
7  01111 
2  102 
8  011101 
1  172 
9  0111011 
1  287 
10  01110111 
2  477 
11  011101101 
1  797 
12  0111011011 
2  1327 
13  01110110101 
2  2212 
14  011101101001 
2  3687 
15  0111011010001 
1  6147 
16  01110110100011 
0  10247 
17  01110110100 
2  10248 
18  011101101001 
1  17082 
19  0111011010011 
0  28472 
20  0111011010 
2  28473 
21  01110110101 
1  47457 
22  011101101011 
0  79097 
23  011101101 
2  79098 
24  0111011001 
1  131832 
25  01110110011 
0  219722 
26  01110110 
2  219723 
27  011101101 
1  366207 
28  0111011011 
0  610347 
29  0111011 
2  610348 
30  01110101 
2  1017247 
31  011101001 
2  1695412 
32  0111010001 
2  2825687 
33  01110100001 
0  4709482 
34  011101000 
1  4709483 
35  0111010001 
2  7849137 
36  01110100001 
1  13081897 
37  011101000011 
1  21803162 
38  0111010000111 
2  36338602 
39  01110100001101 
2  60564337 
40  011101000011001 
2  100940562 
…  …  …  … 
1498  011101101001010001 
2  
1499  0111011010010100001 
1  
1500  01110110100101000011 
1  
1501  011101101001010000111 
0  
1502  01110110100101000 
0  
1503  011101101001 
1  
1504  0111011010011 
0  
1505  0111011010 
2  
1506  01110110101 
0  
1507  011101101 
1  
1508  0111011011 
1  
1509  01110110111 
1  
1510  011101101111 
0  
1511  0111011 
1  
1512  01110111 
2  
1513  011101101 
0  
1514  0111011 
1  
1515  01110111 
0  
1516  0111 
0  
1517  ``  0 