Busy Beavers and Recurrence Relations

While analyzing the behavior of the latest BBB(3, 3) champion, I found that I had to brush up my skills on computing exact formulas for recurrence relations. Let me explain:

The Machine

1RB0LB1LA_2LC2LB2LB_2RC2RA0LC in Standard Text format

	0	1	2
A	1RB	0LB	1LA
B	2LC	2LB	2LB
C	2RC	2RA	0LC

It quasihalts at step 724193411946051617510910916281388064798340875589283913992444770 (\(> 7.2 \times 10^{62}\)) with respect to state B. I announced this machine on last Tuesday on a new Busy Beaver discussion mailing list.

It turns out that this machine has Collatz-like behavior, but requires an extra level of reasoning to analyze.

Level 1

If you simulate this TM using tape compression and chain steps you will probably start noticing the following pattern repeat over and over again:

Step #	Left tape	State	Right tape
0	0^inf	<C	0^a 2^b+1 …
1	0^inf 2	C>	0^a 2^b+1 …
a + 1	0^inf 2^a+1	C>	2^b+1 …
a + 2	0^inf 2^a+1	<C	0 2^b …
2a + 3	0^inf	<C	0^a+2 2^b …

This is our first rule:

Rule 1: 0^inf <C 0^a 2^b+1 ... -> 0^inf <C 0^a+2 2^b ... in 2a + 3 steps.

Repeated Application

Now, we can keep repeating this rule over and over again as long as we still have any 2s left (b > 0). I will write this as:

0^inf <C 0^a₀ 2^b₀ ... -> 0^inf <C 0^a₁ 2^b₁ ... -> … -> 0^inf <C 0^a_k 2^b_k ...

Where

a₀ = a
a_k+1 = a_k + 2
b₀ = b
b_k+1 = b_k - 1

That is, a_k and b_k are the values of a and b respectively after applying Rule 1 k times. These are our first recurrence relations:

A recurrence relation is a sequence of numbers where the next value in the sequence is determined by applying some function to the previous value of the sequence (or sometimes multiple previous values, like in the Fibonacci sequence … but in our case we will only ever look at a single previous value). In our case, the definition of a_k+1 is defined using a_k. Our goal is to “solve” the recurrence relations, which means to develop an equation for a_k which is not recursive (doesn’t depend upon previous values of a_k).

This first recurrence relation is pretty easy to solve. Each iteration of Rule 1 just adds 2 to a and subtracts 1 from b, so after k iterations, we get a_k = a + 2 k and b_k = b - k. We can keep applying Rule 1 as long as b > 0, in other words, until k = b, leaving us in configuration:

0^inf <C 0^a_b 2^b_b ... = 0^inf <C 0^a+2b 2⁰ ...

Therefore, we can write out completely the repeated version of Rule 1 as:

Rule 1x: 0^inf <C 0^a 2^b ... -> 0^inf <C 0^a+2b 2⁰ ...

How many steps will it take? Well, it takes 2a_k + 3 steps at each iteration, so in total it will take:

\[\sum_{k=0}^{b-1}(2 a_k + 3) = \sum_{k=0}^{b-1}(2 (a + 2 k) + 3) = 4 \sum_{k=0}^{b-1} k + (2a + 3) \sum_{k=0}^{b-1} 1\] \[= 2 b (b-1) + (2a + 3) b = 2 b^2 + (2a + 1) b\]

So fully stated:

Rule 1x: 0^inf <C 0^a 2^b ... -> 0^inf <C 0^a+2b 2⁰ ... in 2 b² + (2a + 1) b steps

Level 2

So now that we can quickly clear all the 2s out, what happens next? Well here’s the next situation I see repeatedly happening:

Step #	Left tape	State	Right tape
0	0^inf	<C	0^a 1^c+2 …
1	0^inf 2	C>	0^a 1^c+2 …
a + 1	0^inf 2^a+1	C>	1^c+2 …
a + 2	0^inf 2^a+2	A>	1^c+1 …
a + 3	0^inf 2^a+2	<B	0 1^c …
2a + 5	0^inf	<B	2^a+2 0 1^c …
2a + 6	0^inf	<C	2^a+3 0 1^c …
*	0^inf	<C	0^2a+6 0 1^c …

Note: The last step is accomplished by applying Rule 1x to go from: 0^inf <C 0⁰ 2^a+3 ... -> 0^inf <C 0^2a+6 2⁰ ... in 2 (a+3)² + (2 * 0 + 1) (a+3) = 2 a² + 13 a + 21 steps

So we get:

Rule 2: 0^inf <C 0^a 1^c+2 ... -> 0^inf <C 0^2a+7 1^c ... in 2 a² + 15 a + 27 steps

Non-trivial Recurrence Relation

Just like with Rule 1, we can repeatedly apply Rule 2:

0^inf <C 0^a₀ 1^c₀ ... -> 0^inf <C 0^a₁ 1^c₁ ... -> … -> 0^inf <C 0^a_k 1^c_k ...

Where Rule 2 tells us that:

a_k+1 = 2 a_k + 7
c_k+1 = c_k - 2

c_k is just as easy as before to calculate: c_k = c₀ - 2 k but it is much less obvious how to calculate a_k in general!

Aside: Solving Degree 1, Linear, Non-Homogeneous Recurrence Relations

It turns out that this is an example of a well studied type of recurrence relation called a non-homogeneous linear recurrence relation of degree 1:

Degree 1 means that a_k+1 = f(a_k) (that is, it depends only on a_k, not say a_k-1, etc.).
Linear means that f is a linear function. (In our case: f(n) = 2n + 7).
Non-homogeneous means that f(0) != 0.

If only our recurrence was homogeneous it would be easy to solve. For example, consider the recurrence: h₀ = 3 h_k+1 = 2 h_k. Here we can clearly see that h_k = 2^k * 3.

So, can we convert our recurrence relation into a homogeneous one? Let’s try :) What if we consider the family of recurrence relations H(n)_k = a_k + n (parameterized by n) then:

H(n)_k+1 = a_k+1 + n = (2 a_k + 7) + n = 2 (H(n)_k - n) + 7 + n = 2 H(n)_k + (7 - n)

so, then H(7)_k+1 = 2 H(7)_k is a homogeneous recurrence relation! Woohoo!

So H(7)_k = 2^k * H(7)₀ = 2^k * (a₀ + 7)

And converting back into our original relation:

a_k = H(7)_k - 7 = 2^k * (a₀ + 7) - 7

Note: For a more general approach: Someone at Columbia University posted this excellent book chapter explaining how to solve linear recurrences using generating functions which is really quite magical and mind-bending.

Back to Repeating Rule 2

Ok, now that we have a closed-form solution to our new (Rule 2) recurrence relation:

a_k = 2^k * (a₀ + 7) - 7

we have:

Rule 2x: 0^inf <C 0^a 1^2k+r ... -> 0^inf <C 0^{(2^k * (a + 7) - 7)} 1^r ...

How many steps does it take? Each iteration of Rule 2 takes 2 a_k² + 15 a_k + 27 steps. So total it’s:

\[\sum_{i=0}^{k-1}(2 a_i^2 + 15a_i + 27) = \sum_{i=0}^{k-1}(2 (2^i (a + 7) - 7)^2 + 15 (2^i (a + 7) - 7) + 27)\] \[= \sum_{i=0}^{k-1}(2 (a + 7)^2 4^i + (15 + (2 \cdot 2 \cdot -7)) (a + 7) 2^i + (27 - 15 \cdot 7 + 2 \cdot 7^2))\] \[= 2 (a + 7)^2 \sum_{i=0}^{k-1} 4^i - 13 (a + 7) \sum_{i=0}^{k-1} 2^i + 20 \sum_{i=0}^{k-1} 1\] \[= 2 (a + 7)^2 \frac{4^k - 1}{3} - 13 (a + 7) (2^k - 1) + 20 k\]

Well that’s quite a mouthfull! Let’s give it a shorthand name:

\[B(a, k) = \frac{2}{3} (a + 7)^2 (4^k - 1) - 13 (a + 7) (2^k - 1) + 20 k\]

Remainder Behavior

Finally, once we’ve applied Rule 2x, we could be in one of two situations: r = 0 or r = 1. Let’s see what happens in each of those cases.

Even

For r = 0:

0^inf <C 0^a 1⁰ 0^inf = 0^inf <C 0^inf so we are on a blank tape and since C0 -> 2RC, we will never leave state C again. We’ve reached Chain Recurrence and the TM must have already Quasihalted.

But when did it quasihalt? For this we’ll have to step back one iteration of Rule 2 and consider what happens starting at 0^inf <C 0^a 1² 0^inf. Looking back inside the proof of Rule 2 above, we can see that the last non-C state the TM is in is 2a + 5 steps in, it is in state B (Note that Rule 1 never leaves state C). Therefore:

0^inf <C 0^a 1² 0^inf -> Quasihalt at time 2a + 6 (Note: Quasihalting time is the step after the last step B is seen).

Odd

For r = 1:

Step #	Left tape	State	Right tape
0	0^inf	<C	0^a 1 0^inf
1	0^inf 2	C>	0^a 1 0^inf
a + 1	0^inf 2^a+1	C>	1 0^inf
a + 2	0^inf 2^a+2	A>	0^inf
a + 3	0^inf 2^a+2 1	B>	0^inf
a + 4	0^inf 2^a+2 1	<C	2 0^inf
a + 5	0^inf 2^a+3	A>	2 0^inf
a + 6	0^inf 2^a+3	<A	1 0^inf
2a + 9	0^inf	<A	1^a+4 0^inf
2a + 10	0^inf 1	B>	1^a+4 0^inf
2a + 11	0^inf 1	<B	2 1^a+3 0^inf
2a + 12	0^inf	<B	2² 1^a+3 0^inf
2a + 13	0^inf	<C	2³ 1^a+3 0^inf
2a + 34	0^inf	<C	0⁶ 1^a+3 0^inf

so we have our final rule:

Rule 3: 0^inf <C 0^a 1¹ 0^inf -> 0^inf <C 0⁶ 1^a+3 0^inf in 2a + 34 steps

“Collatz-like Behavior”

Consider the tape configuration:

g(m) = 0^inf <C 0⁶ 1^m 0^inf

Then:

g(2k+1) = 0^inf <C 0⁶ 1^2k+1 0^inf -> 0^inf <C 0^{(13 * 2^k - 7)} 1¹ 0^inf in \(B(6, k)\) steps by Rule 2x
-> 0^inf <C 0⁶ 1^{(13 * 2^k - 4)} 0^inf = g(13 * 2^k - 4) in \(2 (13 \cdot 2^k - 7) + 34 = 26 \cdot 2^k + 20\) steps by Rule 3

and

g(2k) = 0^inf <C 0⁶ 1^2k 0^inf -> 0^inf <C 0^{(13 * 2^k-1 - 7)} 1² 0^inf in \(B(6, k-1)\) steps by Rule 2x
-> Quasihalt at time \(2 (13 \cdot 2^{k-1} - 7) + 6 = 13 \cdot 2^k - 8\).

Summarizing:

g(2k+1) -> g(13 * 2^k - 4) in \(B(6, k) + 26 * 2^k + 20\)
g(2k) -> Quasihalt at time \(B(6, k-1) + 26 * 2{k-1} - 8\)

Orbit from a blank tape

And finally, connecting this all together. Starting a blank tape, this TM reaches configuration g(1) at step 30, from which we get:

Config	k	r	Steps Since Last	Step At
g(1)	0	1		30
g(9)	4	1	`B(6, 0) + 26 * 2⁰ + 20` = 46	76
g(204)	102	0	`B(6, 4) + 26 * 2⁴ + 20` = 26_711	26_787
QHalt			`B(6, 101) + 13 * 2¹⁰² - 8` = 724193411946051617510910916281388064798340875589283913992417982	724193411946051617510910916281388064798340875589283913992444770

Is `g` Really “Collatz-like”?

g has behavior that is reminiscent of Collatz-like behavior. Specifically, it iterates checking the parity of it’s argument at each iteration and branching based upon that parity. However, if you spend a few moments looking at the final recurrence for g you might notice something … for all k > 0, 13 * 2^k - 4 is even, therefore g is known to be “total”. If a TM gets to any state g(m) it will Quasihalt in:

1 iteration if m is even
2 iterations if m >= 3 is odd or
3 iterations in the one special case (m = 1)

Similarity to pre-existing analyses

Note that this analysis is similar to Pascal Michel’s analysis of Pavel Kropitz’s current BB(6, 2) record holder which similarly seems to have a 2 level recurrence behavior and thus leads to this sort of exponential recurrence (C(9k + 9) -> C((50 * 4^k+1 - 11)/3)). Sadly, unlike in that case, for our configuration g we will never have the possibility to iterate g more than 3 times and thus this machine cannot be modified in the way that “Wythagoras” did to create the current BB(7,2) champion.