May has been quite a month for the Busy Beaver competition! After 12 years of no progress on the \(BB(6, 2)\) domain, my discovery on 13 May has kicked off quite the flurry of activity:

Name Date Discoverer \(BB(6, 2)\) bound  
e78k 13 May 2022 Shawn Ligocki \(> 10^{78,913}\) Announcement Analysis
e197k 15 May 2022 Pavel Kropitz \(> 10^{197,282}\) Announcement
e1B 22 May 2022 Pavel Kropitz \(> 10^{1,292,913,985}\) Announcement
t5 27 May 2022 Shawn Ligocki \(> 10↑↑5\) Announcement
t15 30 May 2022 Pavel Kropitz \(> 10↑↑15\) Announcement

A few notes:

  1. I am using the notation \(BB(n, m)\) to mean the max steps among halting \(n\)-state, \(m\)-symbol TMs (historically known as \(S(n, m)\)).
  2. Name is simply a shorthand name I will use to refer to these machines in this article. As you can probably infer, they are just a shorthand for the \(BB(6, 2)\) bound listed.
  3. I am using Knuth’s up-arrow notation for the last two records. So, for example, \(10↑↑5 = 10^{10^{10^{10^{10}}}}\)

I must (slightly begrudgingly) tip my hat to Pavel, who has, so far, refused to allow me to hold the champion title for over 3 days! But I take pride in knowing that my t5 machine brought us past a notable threshold: These numbers can no longer be stored directly in binary in computer memory. In fact, I cannot even tell you how many digits these numbers have or even the number of digits that [the number of digits] has without using a special notation.

In order to simulate these machines, we need symbolic notations for representing numbers and this turns out to make many problems (that were easy with binary representation) significantly more challenging! Let me show you via an analysis of Pavel’s current champion, t15.

Analysis of Pavel’s t15

The Machine

This is Pavel’s current champion (t15):

1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE

  0 1
A 1RB 0LD
B 1RC 0RF
C 1LC 1LA
D 0LE 1RZ
E 1LF 0RB
F 0RC 0RE

Pavel announced this machine on 30 May 2022 and listed the halting configuration as

1 H> 0 1^((81*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^(1)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 19)/8)) - 13)/2)

I provided a preliminary analysis on 31 May. Pascal Michel corrected a mistake in my analysis and provided some numeric improvements to the algorithm. On 16 Jun, Pascal posted a more detailed analysis including step counts. In this post I will synthesize this discussion into a narrative analysis.

The Collatz Rules

Let C(n) = 0∞ 1 0n 11 05 C> 0∞

The following rules can be proven:

  • Rule R0: \(C(4k) \to Halt((3^{k+3} - 11) / 2)\)
  • Rule R1: \(C(4k+1) \to C((3^{k+3} - 11) / 2)\)
  • Rule R2: \(C(4k+2) \to C((3^{k+3} - 11) / 2)\)
  • Rule R3: \(C(4k+3) \to C((3^{k+3} + 1) / 2)\)

I leave the proof as an exercise to the reader. The process of proving these is similar to that in my previous analyses of the BBB(3, 3) champion and e78k.1

Naive evaluation

Starting from a blank tape:

  • At step 45, the TM is in configuration \(C(5) = C(4 \cdot 1 + 1)\)
  • Applying R1:
\[C(4 \cdot 1 + 1) \to C((3^{1+3} - 11) / 2) = C(35) = C(4 \cdot 8 + 3)\]
  • Applying R3:
\[C(4 \cdot 8 + 3) \to C((3^{8+3} + 1) / 2) = C(88574) = C(4 \cdot 22143 + 2)\]
  • Applying R2:
\[C(4 \cdot 22143 + 2) \to C((3^{22143+3} - 11) / 2) = C(A_3) = C(4 k_3 + 3)\]
  • Applying R3:
\[C(4 k_3 + 2) \to C((3^{k_3+3} + 1) / 2) = C(A_4) = C(4 k_4 + r_4)\]

\(A_3 ≈ 1.1 \times 10^{10566}\) is too large of a number to write out here fully, but modern computers can calculate it and easily store it in memory directly in binary. However, \(A_4 > 10^{10^{10564}}\) is far too big to store directly in binary notation in any computer that will ever exist (it would require more bits than there are atoms in the observable universe!). So this is the end of the road when it comes to direct computation. We’ll need some new techniques in order to determine \(r_4\) (and future \(r_k\)).

Exponent Mod

How can we efficiently compute the remainder \(r\) of \((3^{k+3} + 1) / 2\) modulo 4? Well doing a little arithmetic, we get:

\[(3^{k+3} + 1) / 2 = 4 k + r\] \[3^{k+3} + 1 = 8 k + 2r\] \[3^{k+3} = 8k + 2r - 1\]

So this problem reduces to the problem of efficiently computing \(3^{n} \pmod{8}\). Let’s look at some small examples:

\(n\) \(3^{n}\) \(3^{n} \pmod{8}\)
0 1 1
1 3 3
2 9 1
3 27 3
4 81 1

So, there seems to be a pattern here that \(3^{2k} \equiv 1 \pmod{8}\) and \(3^{2k+1} \equiv 3 \pmod{8}\) and (in fact) that’s pretty easy to show since:

\[3^{2k+r} = 3^{2k} \cdot 3^{r} = 9^k \cdot 3^r \equiv 1^k \cdot 3^r = 3^r \pmod{8}\]

Continuing evaluation

Going back to our analysis. In order to compute \(r_4\) we need to calculate \(k_3 + 3 \pmod{2}\). And we know the binary expansion of \(k_3\), specifically \(k_3\) is odd, so \(k_3 + 3\) is even and thus

\[2 r_4 - 1 \equiv 3^{k_3+3} \equiv 1 \pmod{8}\] \[2 r_4 \equiv 2 \pmod{8}\] \[r_4 = 1\]

So,

\[A_4 = 4 k_4 + 1\]

Applying R1:

\[C(4 k_4 + 1) \to C((3^{k_4+3} - 11) / 2) = C(A_5) = C(4 k_5 + r_5)\]

Hm, so we already know that in order to find \(r_5\) we need to know \(k_4 + 3 \pmod{2}\). Let \(k_4 = 2k + r\) then \(A_4 = 8k + 2r - 1\). So now we need to find out what is \(A_4 \pmod{8}\) (Note: We previously calculated \(A_4 \pmod{4}\)).

Generalizing Exponent Mod

In a previous section we figured out how to evaluate \(3^n \pmod{8}\), but now we want to calculate \(3^n \pmod{16}\). Can we (perhaps) find a generalized method for calculating \(3^n \pmod{2^m}\) for arbitrary \(m\)? For the \(3^n \pmod{8}\) we solved this problem by discovering that \(3^2 \equiv 1 \pmod{8}\). So, in order to solve our general problem of computing \(3^n \pmod{2^m}\) we need to find a value \(n\) such that \(3^n \equiv 1 \pmod{2^m}\). In fact, this is a well-studied question from Group Theory. Specifically, it is the question:

Computing Periods

The Period of a number \(a \pmod{b}\) is defined as the smallest (positive) \(n\) such that \(a^n \equiv 1 \pmod{b}\). Finding the period of \(a \pmod{b}\) (for fixed values of \(a, b\)) can be computed naively by directly computing powers of \(a^n \pmod{b}\) until you find one that is \(\equiv 1 \pmod{b}\). For small \(b\) this reasonable, but if \(b\) is large, this can become very slow. Luckily for us, we have hundreds of years of Mathematical innovation to help us out here. In 1763, Leonhard Euler proved:

Euler’s totient theorem: For all \(a, n\) coprime, \(a^{\phi(n)} \equiv 1 \pmod{n}\) (where \(\phi(n)\) is Euler’s totient function).

So, for example, in our case we now definitively say that for all \(m\):

\[3^{\phi(2^m)} = 3^{2^{m-1}} \equiv 1 \pmod{2^m}\]

We could use this right away to evaluate our rules above. But could we do better? Note that this is not proof that the period of \(3 \pmod{2^m}\) is \(2^{m-1}\). The period is defined as the smallest exponent that satisfies this equation, so the period of 3 could be smaller. In fact, in 1910, Robert Carmichael made an improvement on this formula:

The Carmichael function: For all \(n\), \(\lambda(n)\) is the smallest positive integer such that, for all \(a\) coprime to \(n\), \(a^{\lambda(n)} \equiv 1 \pmod{n}\).

In our case, \(\lambda(2^m) = 2^{m-2}\) for all \(m \ge 3\), so:

\[\forall m \ge 3, 3^{\lambda(2^m)} = 3^{2^{m-2}} \equiv 1 \pmod{2^m}\]

is an improvement (smaller exponent). But could we still do better?

(Note that: although \(\lambda(n)\) is known to be the smallest exponent such that for all \(a\) coprime to \(n\), \(a^{\lambda(n)} \equiv 1 \pmod{n}\), this does not mean that \(\lambda(n)\) is the period for all \(a\). In fact, we know that some values of \(a\) have smaller periods, for example, \(a = -1 \equiv b-1 \pmod{b}\) will always have period 2 since \((-1)^2 = 1\).)

However, in our case, it is known that the period of \(3 \pmod{2^m}\) is exactly \(\lambda(2^m) = 2^{m-2}\) (for all \(m \ge 3\)). (See my follow-up article for a proof of this).

Finalizing Exponent Mod

Returning to our example, if we want to calculate the remainder \(3^n \pmod{2^m}\) (for \(m \ge 3\)) we can do it by first calculating the remainder \(n \equiv r \pmod{2^{m-2}}\) and then \(3^n \equiv 3^r \pmod{2^m}\).

In other words, if \(k \equiv r \pmod{2^m}\) (and \(m \ge 1\)), then

\[3^{k+3} + b \equiv 3^{r+3} + b \pmod{2^{m+2}}\] \[(3^{k+3} + b) / 2 \equiv (3^{r+3} + b) / 2 \pmod{2^{m+1}}\]

Finishing Evaluation

Oh my, that was quite the aside … what was our goal for all of this again? Oh right, we are trying to evaluate the repeated application of the “Collatz-like” rules:

  • Rule R0: \(C(4k) \to Halt((3^{k+3} - 11) / 2)\)
  • Rule R1: \(C(4k+1) \to C((3^{k+3} - 11) / 2)\)
  • Rule R2: \(C(4k+2) \to C((3^{k+3} - 11) / 2)\)
  • Rule R3: \(C(4k+3) \to C((3^{k+3} + 1) / 2)\)

We now have enough tools to complete this evaluation! First, let me lay out a bit of notation:

  • Let \(A_0 = 5\) and let \(C(A_{n-1}) \to C(A_n)\) define \(A_n\) (as as long as R1-3 apply).
  • Let \(A_n = 4 k_n + r_n\) so that \(r_n\) is the remained when dividing \(A_n / 4\).

Our goal here is to be able to precisely evaluate all \(r_n\) so that we can figure out which rules apply at each iteration \(n\).

\(n\) \(A_n\) formula \(A_n \pmod{2^m}\) \(k_n\) \(r_n\)
0   \(5\) \(1\) 1
1 \(A_{ 1} = (3^{k_{ 0}+3} - 11) / 2 =\) \(35\) \(8\) 3
2 \(A_{ 2} = (3^{k_{ 1}+3} + 1) / 2 =\) \(88574\) \(22143\) 2
3 \(A_{ 3} = (3^{k_{ 2}+3} - 11) / 2 =\) \(255 \pmod{2^{14}}\) \(63 \pmod{2^{12}}\) 3
4 \(A_{ 4} = (3^{k_{ 3}+3} + 1) / 2 =\) \(4741 \pmod{2^{13}}\) \(1185 \pmod{2^{11}}\) 1
5 \(A_{ 5} = (3^{k_{ 4}+3} - 11) / 2 =\) \(2147 \pmod{2^{12}}\) \(536 \pmod{2^{10}}\) 3
6 \(A_{ 6} = (3^{k_{ 5}+3} + 1) / 2 =\) \(990 \pmod{2^{11}}\) \(247 \pmod{2^{ 9}}\) 2
7 \(A_{ 7} = (3^{k_{ 6}+3} - 11) / 2 =\) \(175 \pmod{2^{10}}\) \(43 \pmod{2^{ 8}}\) 3
8 \(A_{ 8} = (3^{k_{ 7}+3} + 1) / 2 =\) \(253 \pmod{2^{ 9}}\) \(63 \pmod{2^{ 7}}\) 1
9 \(A_{ 9} = (3^{k_{ 8}+3} - 11) / 2 =\) \(127 \pmod{2^{ 8}}\) \(31 \pmod{2^{ 6}}\) 3
10 \(A_{10} = (3^{k_{ 9}+3} + 1) / 2 =\) \(69 \pmod{2^{ 7}}\) \(17 \pmod{2^{ 5}}\) 1
11 \(A_{11} = (3^{k_{10}+3} - 11) / 2 =\) \(3 \pmod{2^{ 6}}\) \(0 \pmod{2^{ 4}}\) 3
12 \(A_{12} = (3^{k_{11}+3} + 1) / 2 =\) \(14 \pmod{2^{ 5}}\) \(3 \pmod{2^{ 3}}\) 2
13 \(A_{13} = (3^{k_{12}+3} - 11) / 2 =\) \(7 \pmod{2^{ 4}}\) \(1 \pmod{2^{ 2}}\) 3
14 \(A_{14} = (3^{k_{13}+3} + 1) / 2 =\) \(1 \pmod{2^{ 3}}\) \(0 \pmod{2^{ 1}}\) 1
15 \(A_{15} = (3^{k_{14}+3} - 11) / 2 =\) \(0 \pmod{2^{ 2}}\)   0

Specifically, I computed \(A_n\) and \(k_n\) directly up to \(n = 3\). Then, I reduced \(A_3\) to the remainder using a “sufficiently large” \(2^m\). (How did I know which \(2^m\) to start with? Guess and check. I just tried some different values, if they were too small, I restarted with a bigger one. Then, in hindsight, I figured out the smallest \(2^m\) necessary.) In the last row, we only know \(A_{15} \equiv 0 \pmod{4}\), which is just barely enough to know that \(r_{15} = 0\). And so we can see that the 16th iteration will be applying Rule R0 which will lead us to halt with \(A_{16} = (3^{k_{15}+3} - 11) / 2\) marks on the tape.

Busy Beaver Bound

Huzzah! We have proven that this TM halts! In fact, we can even specify precisely the number of marks it leaves on the tape:

\[A_{16} = \frac{-11 + 3^{\frac{13 + 3^{\frac{23 + 3^{\frac{7 + 3^{\frac{21 + 3^{\frac{7 + 3^{\frac{23 + 3^{\frac{7 + 3^{\frac{23 + 3^{\frac{7 + 3^{\frac{21 + 3^{\frac{7 + 3^{\frac{23 + 3^{\frac{7 + 3^{\frac{21 + 3^{\frac{7 + 3^{4}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{8}}}{2}\]

(which, I believe, matches Pavel’s expression from the earlier section)

But that expression is a bit unwieldy, can we simplify the bound into a simpler notation? Well:

\[k_{n+1} \ge \frac{A_{n+1} - 3}{4} \ge \frac{3^{k_n + 3} - 17}{8} = \frac{9 \cdot 3^{k_n + 1} - 17}{8} = 3^{k_n + 1} + \frac{3^{k_n + 1} - 17}{8}\]

So (as long as \(k_n >= 2\)):

\[k_{n+1} > 3^{k_n + 1} > 3^{k_n}\] \[A_{16} > 3^{k_{15}}\]

Thus (starting from \(k_1 = 8 > 3\)):

\[k_n > 3↑↑n\] \[A_{16} > 3↑↑16\]

And so, we have proven that \(BB(6, 2) > 3↑↑16\)

Standardizing Notation

This is a pleasingly compact notation, but what if we find another TM which writes \(4↑↑15\) marks. Which one is bigger? It is not immediately obvious how to compare two numbers written in this “up-arrow” notation with different “bases”. So, just as we convert numbers to base 10 in scientific notation (\(3^{13} \approx 1.59 \times 10^{6}\)), we can convert these giant numbers to a base 10 tower.

Let \(T = \frac{1}{\log_{10}(3)} \approx 2.1\) and \(S = \log_{10}(T) \approx 0.32\), so that

\[3^k = 10^{k/T}\] \[3^k / T = 10^{k/T - S}\]

Then,

\[k_{n+1} / T - S \ge 3^{k_n} / T + \frac{3^{k_n + 1} - 17}{8 T} - S = 10^{k_n / T - S} + \frac{3^{k_n + 1} - 17}{8 T} - S\]

Well, assuming \(k_n \ge 2\), then:

\[3^{k_n + 1} - 17 \ge 10\] \[\frac{3^{k_n + 1} - 17}{8 T} > 0.5 > S\] \[k_{n+1} / T - S > 10^{k_n / T - S}\]

Starting from \(k_1 = 8\) (and thus \(k_1 / T - S > 3.4 > 1\)) we can see:

\[k_n / T - S > 10↑↑(n-1)\] \[A_{16} = \frac{3^{k_{15}+3} - 11}{2} > 3^{k_{15}} = 10^{k_{15} / T} > 10^{10↑↑14} = 10↑↑15\]

And so we have proven that \(BB(6, 2) > 10↑↑15\)

Upper Bound

We proved a lower bound on the number of marks (or steps) that this TM writes. How about an upper bound? Is our estimate tight?

Here we need to be a little careful not to confuse the number of marks the TM writes (\(\sigma(\mbox{t15}) = A_{16}\)) with the number of steps it runs for (\(s(\mbox{t15})\)). According to Pascal’s analysis, \(s(\mbox{t15}) \approx \frac{3}{8} \sigma(\mbox{t15})^2\) so I assume that we can safely say that \(s(\mbox{t15}) < \sigma(\mbox{t15})^2 = A_{16}^2\).

So,

\[s(\mbox{t15}) < A_{16}^2 = (\frac{3^{k_{15} + 3} - 11}{2})^2 < (3^{k_{15} + 3})^2 = 3^{2 k_{15} + 6}\] \[2 k_{n+1} + 6 < \frac{A_{n+1}}{2} + 6 \le \frac{3^{k_n + 3} + 1}{4} + 6 = \frac{3^{k_n + 3} + 25}{4} < 3^{2 k_n + 6}\]

(For all \(k_n \ge 0\))

So, starting from \(2 k_1 + 6 = 22 < 27 = 3^3\):

\[k_n + 3 < 3↑↑(n+1)\] \[s(\mbox{t15}) < A_{16}^2 < 3↑↑17\]

So, \(3↑↑16 < \sigma(\mbox{t15}) \le s(\mbox{t15}) < 3↑↑17\) is as tight of a bound as you can get with this notation!

Likewise, for base 10 tower notation:

\[s(\mbox{t15}) < A_{16}^2 < 3^{2 k_{15} + 6} < 10^{2 k_{15} + 6}\] \[2 k_{n+1} + 6 < 3^{2 k_n + 6} < 10^{2 k_n + 6}\]

Starting from \(2 k_2 + 6 = 44292 < 10^{10}\):

\[3 k_n + 6 < 10↑↑n\] \[s(\mbox{t15}) < A_{16}^2 < 10^{10↑↑15} = 10↑↑16\]

so, \(10↑↑15 < \sigma(\mbox{t15}) \le s(\mbox{t15}) < 10↑↑16\) is as tight of a bound as you can get with this base as well.

Note: For a more precise bound (using new notation), see Extending Up-arrow Notation.

Acknowledgements

This article is my synthesis of many techniques I learned from others.

  1. I first learned about Euler’s Totient Theorem and it’s use in evaluating repeated exponential Collatz-like recurrence from a blog post from 2014 by “googology” user “Cloudy176”. This was in analysis of the long-reigning \(BB(7, 2)\) champion machine discovered by “googology” user “Wythagoras”. As “Wythagoras” notes in his post, the key insight was originally described by Pascal Michel at the end of his analysis of Pavel’s \(10^{36534}\) machine in 2010.
  2. Pascal Michel explained to me that the period of a number \(a \pmod{b}\) can be smaller than \(\phi(b)\) (and in fact, that it is in this case). Originally, I had proved Pavel’s machine using only the fact that \(3^{\phi(2^m)} = 3^{2^{m-1}} \equiv 1 \pmod{2^m}\). This proof was correct, but inefficient, requiring a starting modulus with roughly twice as many bits.
  3. Pavel Kropitz described to me (on the bbchallenge.org Discord server) how you can actually computed periods \(a \pmod{b}\) via brute force and how these computations can be done recursively on \(k_n\) (I have not used this fact here, but it will be relevant if we find machines with larger Collatz modulus).
  4. Pascal discovered a discrepancy with my original analysis which turned out to be an arithmetic mistake on my part and led to me originally reporting this as only \(s(\mbox{t15}) \ge \sigma(\mbox{t15}) > 3↑↑14\).
  5. I first explored properties of “Knuth’s up-arrow notation” in 2009 in a “blog post” (on my Wikipedia User page!). It was in this early exploration that I discovered that the base of tetration (↑↑) is almost irrelevant: \(10 \uparrow \uparrow (n-1) < 3 \uparrow \uparrow n < 10 \uparrow \uparrow n\) for all \(n \ge 3\).
  6. Neither I nor “Wythagoras” were the first to propose a TM which ran for so many steps that we cannot write their digits. As far as I know, that honor goes to Milton Green who described an infinite sequence of machines which grow as fast as the Ackermann function. Specifically, his 9-state machine is still unbeaten, writing \(> 3↑↑29 > 10↑↑28\) marks and his 10-state machine writes \(> 3↑↑↑3 = 3↑↑3^{3^3} = 3↑↑7,625,597,484,987\) marks. I first wrote about these machines and calculated these bounds in 2009.

Footnotes

  1. As a hint: start by trying to prove that \(B(n+4, m) \to B(n, 3m+7)\) (where B(n, m) = 0∞ 1 0n 11 03m+2 C> 0∞). ↩