# 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

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

in^{inf}**<C**0^{a+2}2^{b}...`2a + 3`

steps.

### Repeated Application

Now, we can keep repeating this rule over and over again as long as we still have any `2`

s left (`b > 0`

). I will write this as:

`0`

-> ^{inf} **<C** 0^{a0} 2^{b0} ...`0`

-> … -> ^{inf} **<C** 0^{a1} 2^{b1} ...`0`

^{inf} **<C** 0^{ak} 2^{bk} ...

Where

`a`

_{0}= a`a`

_{k+1}= a_{k}+ 2`b`

_{0}= b`b`

_{k+1}= b_{k}- 1

That is, `a`

and _{k}`b`

are the values of _{k}`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`

is defined using _{k+1}`a`

. Our goal is to “solve” the recurrence relations, which means to develop an equation for _{k}`a`

which is not recursive (doesn’t depend upon previous values of _{k}`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`

and _{k} = a + 2 k`b`

. We can keep applying Rule 1 as long as _{k} = b - k`b > 0`

, in other words, until `k = b`

, leaving us in configuration:

`0`

= ^{inf} **<C** 0^{ab} 2^{bb} ...`0`

^{inf} **<C** 0^{a+2b} 2^{0} ...

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^{0} ...

How many steps will it take? Well, it takes `2a`

steps at each iteration, so in total it will take:_{k} + 3

So fully stated:

- Rule 1x:
`0`

->^{inf}**<C**0^{a}2^{b}...`0`

in^{inf}**<C**0^{a+2b}2^{0}...`2 b`

steps^{2}+ (2a + 1) b

## Level 2

So now that we can quickly clear all the `2`

s 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^{0} 2^{a+3} ...`0`

in ^{inf} **<C** 0^{2a+6} 2^{0} ...`2 (a+3)`

= ^{2} + (2 * 0 + 1) (a+3)`2 a`

steps^{2} + 13 a + 21

So we get:

- Rule 2:
`0`

->^{inf}**<C**0^{a}1^{c+2}...`0`

in^{inf}**<C**0^{2a+7}1^{c}...`2 a`

steps^{2}+ 15 a + 27

### Non-trivial Recurrence Relation

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

`0`

-> ^{inf} **<C** 0^{a0} 1^{c0} ...`0`

-> … -> ^{inf} **<C** 0^{a1} 1^{c1} ...`0`

^{inf} **<C** 0^{ak} 1^{ck} ...

Where Rule 2 tells us that:

`a`

_{k+1}= 2 a_{k}+ 7`c`

_{k+1}= c_{k}- 2

`c`

is just as easy as before to calculate: _{k}`c`

but it is much less obvious how to calculate _{k} = c_{0} - 2 k`a`

in general!_{k}

## 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`

(that is, it depends only on_{k+1}= f(a_{k})`a`

, not say_{k}`a`

, etc.)._{k-1} - 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`

_{0} = 3`h`

. Here we can clearly see that _{k+1} = 2 h_{k}`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)`

(parameterized by _{k} = a_{k} + n`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)`

is a homogeneous recurrence relation! Woohoo!_{k+1} = 2 H(7)_{k}

So `H(7)`

= _{k}`2`

= ^{k} * H(7)_{0}`2`

^{k} * (a_{0} + 7)

And converting back into our original relation:

`a`

=_{k}`H(7)`

=_{k}- 7`2`

^{k}* (a_{0}+ 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_{0}+ 7) - 7

we have:

- Rule 2x:
`0`

->^{inf}**<C**0^{a}1^{2k+r}...`0`

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

How many steps does it take? Each iteration of Rule 2 takes `2 a`

steps. So total it’s:_{k}^{2} + 15 a_{k} + 27

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

`B(a, k) = 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}0^{inf}`0`

so we are on a blank tape and since^{inf}**<C**0^{inf}`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`

. Looking back inside the proof of Rule 2 above, we can see that the last non-^{inf} **<C** 0^{a} 1^{2} 0^{inf}`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`

-> Quasihalt at time^{inf}**<C**0^{a}1^{2}0^{inf}`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^{2} 1^{a+3} 0^{inf} |

2a + 13 | 0^{inf} |
<C |
2^{3} 1^{a+3} 0^{inf} |

2a + 34 | 0^{inf} |
<C |
0^{6} 1^{a+3} 0^{inf} |

so we have our final rule:

- Rule 3:
`0`

->^{inf}**<C**0^{a}1^{1}0^{inf}`0`

in^{inf}**<C**0^{6}1^{a+3}0^{inf}`2a + 34`

steps

## “Collatz-like Behavior”

Consider the tape configuration:

`g(m) = 0`

^{inf}**<C**0^{6}1^{m}0^{inf}

Then:

`g(2k+1)`

=`0`

->^{inf}**<C**0^{6}1^{2k+1}0^{inf}`0`

in^{inf}**<C**0^{(13 * 2k - 7)}1^{1}0^{inf}`B(6, k)`

steps by Rule 2x- ->
`0`

=^{inf}**<C**0^{6}1^{(13 * 2k - 4)}0^{inf}`g(13 * 2`

in^{k}- 4)`2 (13 * 2`

=^{k}- 7) + 34`26 * 2`

steps by Rule 3^{k}+ 20

and

`g(2k)`

=`0`

->^{inf}**<C**0^{6}1^{2k}0^{inf}`0`

in^{inf}**<C**0^{(13 * 2k-1 - 7)}1^{2}0^{inf}`B(6, k-1)`

steps by Rule 2x- -> Quasihalt at time
`2 (13 * 2`

^{k-1}- 7) + 6 = 26 * 2^{k-1}- 8

Summarizing:

`g(2k+1)`

->`g(13 * 2`

in^{k}- 4)`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` = 46 |
76 |

g(204) | 102 | 0 | `B(6, 4) + 26 * 2` = 26_711 |
26_787 |

QHalt | `B(6, 101) + 26 * 2` = 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`

is even, therefore ^{k} - 4`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`

). Sadly, unlike in that case, for our configuration ^{k+1} - 11)/3)`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.