BBB Complex Collatz-like Behavior
Almost all existing Busy Beaver champions (and runner ups) exhibit Collatz-like 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 Collatz-like model in a pleasingly simple way. Today, I’ll be analyzing my newly discovered BBB(5, 2) champion which runs for over 10502 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 > 10502 steps before quasihalting. At that number of steps (> a googol5) 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 step-by-step discussion of how we get to rule steps, including the description of tape compression notation and chain steps, please read my original article: “Collatz-like behavior of Busy Beavers”.
Common Configuration
This analysis will be built around a common configuration:
... 1n <E 1m 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) = 1n <E 1m 0∞
So, for example, 0∞ 11101110 f(n, m)
would denote the full configuration 0∞ 11101110 1n <E 1m 0∞
.
The Basic Rule
f(n+3, m)
-> f(n, m+5)
in 2m + 15
steps.
Proof:
Step # | Left tape | State | Right tape |
---|---|---|---|
0 | 1n+3 | <E | 1m 0∞ |
1 | 1n+2 | <A | 1m+1 0∞ |
2 | 1n+1 | <C | 1m+2 0∞ |
3 | 1n 0 | C> | 1m+2 0∞ |
m + 5 | 1n 0m+3 | C> | 0∞ |
m + 6 | 1n 0m+3 | <B | 0∞ |
m + 7 | 1n 0m+2 1 | C> | 0∞ |
m + 8 | 1n 0m+2 1 | <B | 0∞ |
m + 9 | 1n 0m+3 | D> | 0∞ |
m + 10 | 1n 0m+4 | E> | 0∞ |
m + 11 | 1n 0m+4 | <E | 1 0∞ |
2m + 15 | 1n | <E | 1m+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 | 1m 0∞ |
1 | 0 | <A | 1m+1 0∞ |
2 | 1 | B> | 1m+1 0∞ |
3 | 1 0 | D> | 1m 0∞ |
m + 3 | 1 0 1m | D> | 0∞ |
m + 4 | 1 0 1m 0 | E> | 0∞ |
m + 5 | 1 0 1m 0 | <E | 1 0∞ |
m + 6 | 1 0 1m | <E | 12 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 | 1m 0∞ |
1 | 0 0 1 | <A | 1m+1 0∞ |
2 | 0 0 | <C | 1m+2 0∞ |
3 | 0 | <B | 0 1m+2 0∞ |
4 | 1 | C> | 0 1m+2 0∞ |
5 | 1 | <B | 0 1m+2 0∞ |
6 | 0 | D> | 0 1m+2 0∞ |
7 | 0 0 | E> | 1m+2 0∞ |
8 | 0 0 | <A | 1m+2 0∞ |
9 | 0 1 | B> | 1m+2 0∞ |
10 | 0 1 0 | D> | 1m+1 0∞ |
m + 11 | 0 1 0 1m+1 | D> | 0∞ |
m + 12 | 0 1 0 1m+1 0 | E> | 0∞ |
m + 13 | 0 1 0 1m+1 0 | <E | 1 0∞ |
m + 14 | 0 1 0 1m+1 | <E | 12 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 | 1m 0∞ |
1 | 1 0 1 | <A | 1m+1 0∞ |
2 | 1 0 | <C | 1m+2 0∞ |
3 | 1 | <B | 0 1m+2 0∞ |
4 | 0 | D> | 0 1m+2 0∞ |
5 | 0 0 | E> | 1m+2 0∞ |
6 | 0 0 | <A | 1m+2 0∞ |
7 | 0 1 | B> | 1m+2 0∞ |
8 | 0 1 0 | D> | 1m+1 0∞ |
m + 9 | 0 1 0 1m+1 | D> | 0∞ |
m + 10 | 0 1 0 1m+1 0 | E> | 0∞ |
m + 11 | 0 1 0 1m+1 0 | <E | 1 0∞ |
m + 12 | 0 1 0 1m+1 | <E | 12 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 | 1m 0∞ |
1 | <E | 1m+1 0∞ |
As a result, notice that this means that if we are in configuration:
0∞ f(0, m)
= 0∞ <E 1m 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 1n <E 1m 0∞
= f(n+1, m)
Collatz-like 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 Collatz-like function. Specifically, consider the general configuration:
g(x, n, m)
= 0∞ bin(x) 1n <E 1m 0∞
= 0∞ bin(x) f(n, m)
where bin(x)
means writing x
in binary in the standard big-endian 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∞ 11 <E 13 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 × 10251) |
2258 | g(7, 0, ~2.4 × 10251) |
2259 | g(3, 1, ~2.4 × 10251) |
2260 | g(1, 2, ~2.4 × 10251) |
2261 | g(0, 3, ~2.4 × 10251) |
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 Collatz-like 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 1a 0b f(0, m)
->0 f(a, m+b)
0∞ f(0, m)
-> Quasihalt
So, we repeatedly iterate a Collatz-like 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 |