a turing machine: a tape, a head, and a handful of states. in each state it reads the mark under the head, writes a mark, moves one cell, and switches state. the busy beaver game asks: of all machines with exactly 5 states that eventually stop, which one runs the longest?
47,176,870 steps. the hard part is the machines that never stop. running one only tells you it hasn't stopped yet, and turing proved no single method can decide, for every machine, whether it ever stops (the halting problem). so each holdout needed its own proof. that took decades, until a mass collaboration formally verified every case in 2024. it is the smallest number on this tour. remember it.
busy beaver challenge, formally verified 2024
tap right half or press → / space
shuffle a deck of cards. there are 52 choices for the top card, 51 for the next, and so on down to 1, so the number of orderings is 52 × 51 × … × 1, written 52! (52 factorial). it has 68 digits. if every person on earth shuffled once per second since the big bang, they would have seen less than a trillionth of a trillionth of a trillionth of all arrangements.
every shuffle you have ever done was almost certainly unique. every shuffle anyone has ever done was almost certainly unique.
how many possible chess games are there? claude shannon estimated 10120. the observable universe has about 1080 atoms. the number of chess games is ten thousand trillion trillion trillion times that.
shannon, 1950
the next numbers need a new way to write them. one up-arrow is repeated multiplication. two arrows repeat the one-arrow step: 3↑↑3 is a power tower of three 3s. three arrows repeat the two-arrow step, and the tower is suddenly 7.6 trillion 3s tall. every extra arrow repeats the one before it.
add one more arrow and you get g1 = 3↑↑↑↑3, already too large to write down if every particle in the observable universe were a digit. g2 has g1 arrows. graham's number is g64.
it came from a coloring problem: join every pair of corners of an n-dimensional cube, color each line red or blue, and ask how big n must be before four corners in one flat plane are forced to have all six lines the same color. graham's number was an upper bound. the actual answer might be 13.
ronald graham, 1970s; made famous by martin gardner, 1977
build a list of trees with colored nodes. tree number k can have at most k nodes, and no earlier tree may be hidden inside a later one: you must never be able to get an earlier tree by pruning a later one, colors kept. kruskal proved every such list has to end. how long can it get?
with one color, 1 tree. with two colors, 3. with three colors, so many that graham's number is a rounding error next to it.
kruskal's tree theorem, 1960
the answers outgrew every tool we had to write them down.
and then they outgrew what we can compute. the busy beaver from the first stop grows faster than any function a computer can calculate. if some computable function kept up with it, you could run any machine for that many steps and know that if it hasn't stopped by then, it never will. that would solve the halting problem. at 6 states it already runs into open problems nobody knows how to solve, and somewhere further along it passes TREE(3). some numbers are not just large. they are unreachable.