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

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

It quasihalts at step 724193411946051617510910916281388064798340875589283913992444770 (> 7.2 * 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 0inf <C 0a 2b+1
1 0inf 2 C> 0a 2b+1
a + 1 0inf 2a+1 C> 2b+1
a + 2 0inf 2a+1 <C 0 2b
2a + 3 0inf <C 0a+2 2b

This is our first rule:

  • Rule 1: 0inf <C 0a 2b+1 ... -> 0inf <C 0a+2 2b ... 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:

0inf <C 0a0 2b0 ... -> 0inf <C 0a1 2b1 ... -> … -> 0inf <C 0ak 2bk ...

Where

  • a0 = a
  • ak+1 = ak + 2
  • b0 = b
  • bk+1 = bk - 1

That is, ak and bk 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 ak+1 is defined using ak. Our goal is to “solve” the recurrence relations, which means to develop an equation for ak which is not recursive (doesn’t depend upon previous values of ak).

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 ak = a + 2 k and bk = b - k. We can keep applying Rule 1 as long as b > 0, in other words, until k = b, leaving us in configuration:

0inf <C 0ab 2bb ... = 0inf <C 0a+2b 20 ...

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

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

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

So fully stated:

  • Rule 1x: 0inf <C 0a 2b ... -> 0inf <C 0a+2b 20 ... in 2 b2 + (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 0inf <C 0a 1c+2
1 0inf 2 C> 0a 1c+2
a + 1 0inf 2a+1 C> 1c+2
a + 2 0inf 2a+2 A> 1c+1
a + 3 0inf 2a+2 <B 0 1c
2a + 5 0inf <B 2a+2 0 1c
2a + 6 0inf <C 2a+3 0 1c
* 0inf <C 02a+6 0 1c

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

So we get:

  • Rule 2: 0inf <C 0a 1c+2 ... -> 0inf <C 02a+7 1c ... in 2 a2 + 15 a + 27 steps

Non-trivial Recurrence Relation

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

0inf <C 0a0 1c0 ... -> 0inf <C 0a1 1c1 ... -> … -> 0inf <C 0ak 1ck ...

Where Rule 2 tells us that:

  • ak+1 = 2 ak + 7
  • ck+1 = ck - 2

ck is just as easy as before to calculate: ck = c0 - 2 k but it is much less obvious how to calculate ak 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 ak+1 = f(ak) (that is, it depends only on ak, not say ak-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: h0 = 3 hk+1 = 2 hk. Here we can clearly see that hk = 2k * 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 = ak + n (parameterized by n) then:

  • H(n)k+1 = ak+1 + n = (2 ak + 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 = 2k * H(7)0 = 2k * (a0 + 7)

And converting back into our original relation:

  • ak = H(7)k - 7 = 2k * (a0 + 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:

  • ak = 2k * (a0 + 7) - 7

we have:

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

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

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

  • B(a, k) = 2/3 (a + 7)2 (4k - 1) - 13 (a + 7) (2k - 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:

  • 0inf <C 0a 10 0inf = 0inf <C 0inf 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 0inf <C 0a 12 0inf. 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:

  • 0inf <C 0a 12 0inf -> 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 0inf <C 0a 1 0inf
1 0inf 2 C> 0a 1 0inf
a + 1 0inf 2a+1 C> 1 0inf
a + 2 0inf 2a+2 A> 0inf
a + 3 0inf 2a+2 1 B> 0inf
a + 4 0inf 2a+2 1 <C 2 0inf
a + 5 0inf 2a+3 A> 2 0inf
a + 6 0inf 2a+3 <A 1 0inf
2a + 9 0inf <A 1a+4 0inf
2a + 10 0inf 1 B> 1a+4 0inf
2a + 11 0inf 1 <B 2 1a+3 0inf
2a + 12 0inf <B 22 1a+3 0inf
2a + 13 0inf <C 23 1a+3 0inf
2a + 34 0inf <C 06 1a+3 0inf

so we have our final rule:

  • Rule 3: 0inf <C 0a 11 0inf -> 0inf <C 06 1a+3 0inf in 2a + 34 steps

“Collatz-like Behavior”

Consider the tape configuration:

  • g(m) = 0inf <C 06 1m 0inf

Then:

  • g(2k+1) = 0inf <C 06 12k+1 0inf -> 0inf <C 0(13 * 2k - 7) 11 0inf in B(6, k) steps by Rule 2x
  • -> 0inf <C 06 1(13 * 2k - 4) 0inf = g(13 * 2k - 4) in 2 (13 * 2k - 7) + 34 = 26 * 2k + 20 steps by Rule 3

and

  • g(2k) = 0inf <C 06 12k 0inf -> 0inf <C 0(13 * 2k-1 - 7) 12 0inf in B(6, k-1) steps by Rule 2x
  • -> Quasihalt at time 2 (13 * 2k-1 - 7) + 6 = 26 * 2k-1 - 8

Summarizing:

  • g(2k+1) -> g(13 * 2k - 4) in B(6, k) + 26 * 2k + 20
  • g(2k) -> Quasihalt at time B(6, k-1) + 26 * 2k-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 * 20 + 20 = 46 76
g(204) 102 0 B(6, 4) + 26 * 24 + 20 = 26_711 26_787
QHalt     B(6, 101) + 26 * 2101 - 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 * 2k - 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 * 4k+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.