The Uncomputable Number: A Sixty-Year Beaver Hunt

Bölüm metni

Picture a toy machine with five rules and two symbols. One of them runs for exactly forty-seven million one hundred seventy-six thousand eight hundred seventy steps and then stops — and working out which one stops took humanity sixty years, and in the end a proof we had to hand to a computer to verify. As for the next number, nobody knows it anymore; because that is where mathematics runs into a wall of its own making.

Kanal ayarı gereği bir not: `podcast-science.json` içinde bu kanal `"language": "en"` olarak tanımlı ve yönergesi "aynı günün bilim bölümü çevrilir" diyor. Kaynak metin (`bilim.txt`) zaten Türkçe olduğu için "Türkçe'ye çeviri" boş bir işlem olurdu; bu yüzden metni kanalın gerçek dili olan İngilizce'ye, kaynağa sadık kalarak çevirdim. Açılış kancası, jingle ve kapanış cümlesi sizin eklediğiniz parçalar olduğu için çıkarıldı.

In 1962, a Hungarian-born mathematician teaching at Ohio State University, Tibor Radó, proposed a game to his students. The rules were as simple as a child's game, and the consequences deep enough to press against the limits of mathematics.

Imagine you have a blank tape stretching out forever. The tape is divided into individual cells, and sitting on one of those cells is a read-write head. The head looks at the cell beneath it, sees whether there is a 0 or a 1 there, and then consults the table of rules it has been given. The table tells it three things: what to write in that cell, whether to move right or left, and which mood, which state, to move into on the next step. That is all. We call this a Turing machine, and in theory it can do everything every computer in the world can do.

Radó's question was this. Suppose the machine has only 5 different states, meaning the rule table has only 5 rows. There are a limited number of ways to fill in that table. Some tables send the machine into an endless loop, and it shuttles back and forth forever. Others bring it to a halt at some point. Focus on the ones that halt, Radó said. Among those, which one runs the longest? How many steps does it take? How many 1s does it write on the paper before it shuts down?

He called this number the busy beaver number. Because the machine, out on that infinite blank tape, keeps writing and erasing, going back and forth, just as a beaver hauls branches to a streambed. The paper Radó published in 1962 on non-computable functions revealed a bomb hidden inside this seemingly harmless game.

The bomb was this. If you knew the maximum number of steps a 5-state machine could take, you would hold enormous power in your hands. Hand someone a 5-state machine you had never seen before, and you would run it and wait exactly that many steps. If it halts, it halts. If it has not halted by that number, you would know with certainty that it never will. Because by definition that number is the longest any halting machine runs. So without ever examining the program, just by watching the clock, you could say whether any given program would fall into an infinite loop.

And yet Alan Turing had proved in 1936 that precisely this is impossible. There is no general method that tells you in every case whether a program halts, and there cannot be one. Which means there can be no formula, no algorithm, no computer program that hands you all the busy beaver numbers. The function is uncomputable. And not merely uncomputable: it grows at a rate beyond comprehension. Every computable function you can think of, it eventually leaves behind.

But here is the crucial point: being uncomputable does not mean none of its values can be known. One by one, by hand, by sheer labor, you can pin down some of them. And mathematicians set out to do exactly that.

The first steps were easy. The record for a 1-state machine is 1 step. For a 2-state machine, 6 steps. The third step began to fight back. Radó's doctoral student Shen Lin combed through every 3-state machine and proved that the record was 21 steps. They published the result together in 1965, shortly before Radó's death.

The fourth step took 18 years. In 1983 Allen Brady showed that the record for 4-state machines was 107 steps. 1, 6, 21, 107. At first glance, a sequence that looks harmless enough, not growing with any particular cruelty.

And then came the wall.

In 1989 two German researchers, Heiner Marxen and Jürgen Buntrock, found the monster among the 5-state machines. Its rule table still had just 5 rows, it still wrote nothing but 0s and 1s, but this machine ran on a blank tape for exactly 47,176,870 steps and then stopped without warning. When it halted, 4098 ones were left on the tape.

From 107 to 47 million. Adding a single row, a single state, had multiplied the scale of the game half a million times over.

Everyone believed this was the record. Searches went on for years and nothing longer turned up. But believing is one thing and proving is another. To say that this number truly is the record, you have to show that not one of the 5-state machines runs longer than that and then halts. Which means proving, for every single machine, that it either halts or runs forever.

And that was where the difficulty lay. Showing that a machine halts is easy: you run it, it stops, done. But showing that a machine will never halt is making a claim about an infinite future. However long you run it, you cannot know the answer. You have to understand it, unravel the pattern inside it, capture its loop mathematically.

And you had to do this millions of times over. The total number of 5-state machines runs into the billions. Once you strip away symmetries, duplicates, and tables identical to one another, roughly 120 million candidates remain. About 88 million of these had to be decided one by one. At one point Allen Brady feared the number might never be known at all. Because if even one of those millions of machines had behavior tied to an unsolved mathematical problem like the Goldbach conjecture, the door would close.

For 40 years nobody opened that door. Then a crowd from outside academia opened it.

In the spring of 2022, Tristan Stérin, who had just finished his doctoral work, set up an internet forum and a chat server devoted to the busy beaver problem. The effort was called the Busy Beaver Challenge. The aim was clear: to clear out the 5-state machines en masse, through distributed effort.

Most of the people who showed up had no academic title. Software developers, former mathematics students, curious amateurs. Shawn Ligocki was a software engineer. Justin Blanchard had an unfinished graduate background in mathematics. Maja Kądziołka was a self-taught 21-year-old Polish programmer. Their numbers passed 20.

The method was this. Instead of solving machines one at a time, they wrote programs they called deciders. Each decider recognized a particular pattern of behavior. One program to catch a certain shape repeating on the tape forever, another to catch a different kind of loop. Every new decider wiped millions of machines off the remaining pile in a single stroke. The pile fell from millions to hundreds of thousands, from hundreds of thousands to thousands, from thousands to a few dozen.

The last survivors became legendary. Two machines from a list of hard cases compiled years earlier by a Bulgarian researcher under the pseudonym Skelet, Skelet 1 and Skelet 17, resisted every attack. Skelet 17 was cracked by Chris Xu, a graduate student.

But the real turning point came from a participant nobody could identify, who appeared only under the handle mxdys. mxdys raised the community's standard: every claim had to be not an argument a human could read and be persuaded by, but a formal proof a machine could check line by line. In May 2024, mxdys completed a colossal proof, 40,000 lines long. It was written in the proof checker called Coq, a system in which every logical step is independently tested by the computer and nothing is left to human intuition. On an ordinary laptop, using 13 cores, that checker verified the entire proof in about 45 minutes.

On July 2, 2024, the result was announced. The fifth busy beaver number is 47,176,870. The machine Marxen and Buntrock had found 35 years earlier really was the champion.

62 years had passed since Radó asked the question. The winner was not the elegant discovery of a single genius, but the collective bookkeeping of a community, spread over years, most of whose names were nothing but pseudonyms.

The victory had not even been announced yet when it became clear that something far darker was waiting on the next step of the hunt.

Nobody knows how large the sixth step is. The only thing known is that the estimates coming from below have long since abandoned human intuition. In 2022 Pavel Kropitz showed that the number of 1s a 6-state machine writes on the tape is larger than a tower of 10s stacked 15 high, a 10 raised to a 10 raised to a 10 and so on. Next to that number, the count of atoms in the universe is a rounding error. In 2025 mxdys broke the bound once again and pushed it to a level that cannot be expressed even with towers of exponents, a level that requires counting towers of towers.

But the real issue is not size. The real issue surfaced on June 28, 2024, just four days before the fifth number was officially announced. On the community's chat server, mxdys mentioned a strange 6-state machine. The machine neither halted nor fell into any recognizable loop; it behaved almost at random. A participant named Racheline soon worked out the machine's hidden rule. They named it Antihydra, because it closely resembled an earlier machine called Hydra.

What Antihydra does can be reduced to a plain arithmetic game. You have a number, 8 to begin with. Each round you take that number, compute its half, throw away the remainder, and add what you get back to the number itself. So the number grows by roughly one and a half times each round. On the side you also keep a counter. If the number in your hand that round is even, you increase the counter by 2; if it is odd, you decrease it by 1. The machine halts if and only if that counter drops below zero.

So for Antihydra to halt, the odd numbers in this sequence growing by a factor of one and a half have to leave the even ones behind by an overwhelming margin. It is a race in which the counter gains 2 for every even and loses 1 for every odd. If odds and evens arrive with roughly equal frequency, the counter climbs on average, steadily. For it to fall, a long run of odd numbers has to come up back to back.

Probability gives a very clear answer here. If odd and even really are distributed like a coin toss, the chance that the counter ever dips below zero is one in the number you get by writing 10 followed by 200 million zeros. In practice, zero. The machine almost certainly runs forever.

Except that almost certainly means nothing in mathematics. These numbers are not being produced by flipping coins. It is a fully determined sequence, born from a single starting value. Someone has to prove that the distribution of odds and evens really does behave as though it were random, and nobody can. What is more, this question connects directly to a problem that has stood open in mathematics for decades, Mahler's question about Z numbers, about how the fractional parts of the powers of one and a half are distributed.

Shawn Ligocki gave machines like this a name: cryptids. Like creatures said to exist in the forest but never captured, they are machines whose behavior you can observe but cannot prove. Antihydra is the most famous of them. And on its own it locks the door to the sixth step. If you want to know the sixth busy beaver number, you first have to solve this arithmetic puzzle. The beaver hunt has turned into a mathematics problem.

As the scale climbs, the picture grows heavier still. Through Stefan O'Rear's work, it was shown that a 27-state Turing machine searches for a counterexample to the Goldbach conjecture, meaning it halts only if that conjecture is false. With about 744 states the same thing can be done for the Riemann hypothesis. And the most striking of all: there is a 745-state machine for which the question of whether it halts can neither be proved nor disproved from the set theory axioms on which modern mathematics is built. O'Rear established this result, and Johannes Riebel wrote it up in detail in his undergraduate thesis and brought it down one more step.

Here is what that means. The 745th busy beaver number is, by definition, a specific, finite, single whole number. It stops somewhere, it has a value. But from inside the mathematics we use today, we will never be able to learn what that value is. A number proved to be unprovable.

And this is where the real worth of the busy beaver function comes out. It is not an amusing puzzle but a ruler that measures mathematics' own difficulty. Every open conjecture corresponds to some rung on that ruler. Goldbach at 27, Riemann at 744, the boundary of what mathematics can know at 745. A hunt lasting 60 years won the fifth step. On the sixth the hunt is not over; a handful of anonymous people from every corner of the world are learning together at exactly what point the hunt stops being a hunt and becomes the boundary itself.

Nöron Science'de bugünkü bölümün sonuna geldik. Yeni bir hikâyede yeniden buluşmak üzere.