Staring into the Halting Abyss

I was watching a video late last night about the fastest-growing arrays in mathematics, the notations googologists use to construct numbers that break the human brain. Things like Knuth's up-arrow notation, where 3↑↑3 is already a tower of three 3s (3^3^3 = 3 ^ 27 or 7.6 * 10 ^ 12), and 2 ↑↑↑ 10 is a tower of twos whose height is itself a tower of twos of height... well, it quickly runs off the edge of human conception. It starts with simple arithmetic, but very quickly you are looking at the boundaries of human imagination. And then the video mentioned the Busy Beaver sequence (BB). It is the fastest-growing predefined sequence we can define, outstripping every up-arrow, every chained arrow notation, and every exploding array notation ever conceived. Why? Because it represents the absolute, hard limit of what we can compute—and by extension, what we can ever hope to explore of the mathematical universe.

We think of computation as a tool that can grow infinitely. We build faster chips, compile better algorithms, convinced that if we just add enough zeros to our processing power, we can simulate anything, solve anything, know anything. But there is a silent, terrifying limit to both our computation and our conception.

To understand this limit, you have to go back to Alan Turing in 1936. Before actual physical computers existed, he conceived theTuring machine: the ultimate, omnipotent abstraction of the mathematical world. It is ridiculously simple: an infinitely long tape divided into cells, a read-write head that sits over one cell, and a set of state transition rules. The machine can only do three things at any step: read the current cell, write a symbol (like 0 or 1), and either move left or right before switching to another state or halting. That’s it. Yet, this simple mathematical construct is capable of simulating any algorithm that can ever be written. If a computer can compute it, a Turing machine can too. It is the definition of computation itself.

              Infinite Tape (Memory)
     +---+---+---+---+---+---+---+---+---+---+
 ... | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | ...
     +---+---+---+---+---+---+---+---+---+---+
                       ^
                       | [Read/Write Head]
                       |
                 +-----------+
                 |  Control  | Current State: $q_1$
                 |   Unit    | Rules: If reading $1$, write $0$,
                 +-----------+        move Left, transition to $q_2$.

But Turing’s greatest triumph was not showing what computers could do; it was proving what they never could. He proved theHalting Problem: you cannot write a program that takes any arbitrary Turing machine and determines whether it will eventually stop running or loop forever.

This is where theBusy Beavergame comes in, invented by Tibor Radó in 1962. It’s a deceptively simple question: if you take an n-state Turing machine starting on a completely blank tape (all 0s), what is the maximum number of steps it can run before it halts? We call this function BB(n).

For n = 1, it is trivial: BB(1) = 1.
For n = 2, it is 6.
For n = 3, it is 21.
For n = 4, it jumps to 107.
It feels like a normal progression, a neat little curve. But then you hit BB(5), and the universe bends.

For decades, we didn't know the value of BB(5). It was only recently, in 2024, that a collaborative effort formally proved that BB(5) = 47,176,870. Think about that. A machine with only five states, operating on a binary tape with no inputs, can run for over forty-seven million steps before suddenly, inexplicably, deciding to halt. To prove this, mathematicians had to analyze millions of machines. Some of them behaved like chaotic dynamical systems, doing the equivalent of checking the Collatz conjecture for massive numbers before finally stopping.

And BB(6)? It is completely out of our reach. The current lower bound for BB(6) is already a number so large that we cannot write it down without using towers of exponents—at least 10^{36,534} steps. If we ever find the exact value of BB(6), it won’t just be a computational feat; it will represent a monumental advance in human civilization. It would mean we have developed mathematical techniques sophisticated enough to resolve the behavior of machines that simulate logic far beyond our current grasp.

And yet, we are so incredibly limited. The Busy Beaver sequence grows faster than any computable function. It grows faster than factorials, faster than exponentials, faster than Ackermann’s function, and faster than any chained arrow or array notation we could ever write down. If you tried to write a program to calculate BB(n) for any arbitrary n, your program would be mathematically guaranteed to fail. The sequence is uncomputable. The math proof is given but I won't put it here.

This is where the true omnipotence of the Busy Beaver reveals itself. Because it is the absolute limit of computation, it holds the key to all of mathematics. Consider Goldbach's Conjecture: the famous, unproven guess that every even integer greater than 2 is the sum of two primes. We could easily write a Turing machine with a small number of states—say, k states—that starts at 4 and checks every even number. If it finds one that isn't the sum of two primes, it halts. If the conjecture is true, the machine runs forever.

If we knew the exact value of BB(k), we wouldn't need to prove the conjecture. We would just run our k-state machine for BB(k) steps. If it halted, we'd have our counterexample. If it didn't halt by step BB(k), we would know with mathematical certainty that it would never halt, meaning Goldbach's Conjecture is true. The same goes for the Riemann Hypothesis, or any other finitely verifiable mathematical claim. In fact, people have already proven the difficulty of calculating BB(27) is definitely greater than proving Goldbach's Conjecture and BB(744) is definitely greater than provingRiemann Hypothesis. The Busy Beaver is a universal solvent for mathematical truth. If we had an oracle for BB(n), we would have a key to a glimpse to the infinite power of God.

And maybe that is the point. When you look back to the Busy Beaver, one is reminded of God's omnipotent power, and our own profound finitude. We live in a world where we think we are masters of information. We build AI, we collect petabytes of data, we pretend we can predict the future and optimize our lives down to the millisecond. But all of these are just Turing Machines, and we cannot even go beyond the calculation of BB(6), a simple machine with six states. (Note: this is a little inaccurate because it is one thing to build a Turing Machine and another thing to calculate the steps before a Turing Machine halts, and human beings are capable of doing the first not the latter)

It is a humbling reminder that the limits of our computation are also the limits of our conception. We can catch glimpses of the infinite, we can define the boundary of the unknowable, but we can never cross it. Turing has already prove to us that there will never be a program that you can just run to calculate BB(x). It is just mathematically, physically, realistically, and theologically impossible. In the end, we are just like those little machines, tracing patterns on an infinite tape, hoping that before the screen goes dark, we might write a few more 1s.

The entire post is inspired by 【【漫士】这是世界上增长最快的数列，不服来战】https://www.bilibili.com/video/BV1cf9YBhET1?vd_source=54f1de195da1139310624678efea87eb and the credit is given to the original author.