A conversation with the Oracle

The last chapter ended with a question: does every precise question have an answer that a machine can find? One such question has already come up three times. In Chapter 0 it was three lines about Collatz, and nobody knows whether they halt for every number. In Chapter 53 it was the wish for a check stronger than type checking: a program that reads any program and says whether it will hang. In the last chapter it was a simulator that can only wait. The answer to the last chapter’s question is no, but you needn’t take that on trust: we will reach it by arguing with someone who is sure of the opposite.

The chapter is written as a dialogue, after the model of Douglas Hofstadter’s Gödel, Escher, Bach (1979). Between the chapters of that book, Achilles and the Tortoise, borrowed from Lewis Carroll, hold conversations, and the book’s hardest ideas run through their arguments. The one you will be talking to is the Oracle. That word is borrowed too: in 1938, in the dissertation he wrote at Princeton under Church, Turing considered machines that can turn to an “oracle” with a hard question. Turing doesn’t explain how the oracle works, only that its answers are always right. Our Oracle claims to be such a device.

Königsberg, September 1930

The day before, Gödel had knocked out one half of this confidence: not every true statement can be proved. That story is told in “Mathematics, the Queen of the Sciences,” in the chapter on Gödel. The other half, that every precise question can be settled mechanically, was refuted six years later by Church and Turing. Their answer is where our conversation is heading.

Prelude. The Oracle’s shop

This is the first and most natural attempt: run the program and wait. The course module cs.oracle contains an Oracle of this kind. The function halts(source, steps) runs the program, counting lines, and if the program hasn’t finished within steps lines, it answers “won’t halt.” He isn’t hard to catch.

The patient program executes two lines per pass through the loop, the test and the increment, 120,002 lines in all, and that doesn’t fit into a budget of a hundred thousand. The Oracle declared it endless, though it finishes in a fraction of a second. Any budget breaks the same way: for a limit of a million there is a program that needs a million and one lines.

Here is the question we are arguing about, in strict terms. The halting problem is to determine, from the text of a program and its input, whether the program will finish. A problem with a yes-or-no answer is called decidable if some program halts on every input and gives the right answer. The whole weight of the definition rests on two words. “Every”: the Oracle has to cope with every program, including the ones he dislikes. “Halts”: “wait a little longer” doesn’t count as an answer.

Act one. The contrarian

Try playing the Oracle yourself. Answer whatever you like, as many times as you like, and change your strategy from one round to the next.

The Oracle always loses, and not because he chose badly. The contrarian is built to do the opposite of any answer. So the Oracle cannot give a correct answer to “will the contrarian halt?”, and yet a correct answer exists: the contrarian either halts or it doesn’t. Only one way out is left: no such Oracle exists. Here is the same thing stated rigorously.

The proof is shorter than this paragraph, and that is where its strength lies: it doesn’t depend on how halts works inside. Whether it is simple or elaborate, whether it tries cases or was trained on a million programs, its contrarian is built in the same way. Keep in mind what the theorem does not say. It doesn’t claim that nothing can be learned about whether a particular program halts; for while True: pass you can tell at a glance. What doesn’t exist is a single method that works for all programs.

Act two. The mirror

In Chapter 7 we took apart how a quine works: a template of the program with one hole, and into the hole goes the written form of the template itself. The same device lets a program get hold of its text for any purpose; printing is only one of them. Here is a contrarian you can run. It asks the Oracle what it is going to print, “yes” or “no”, and prints the opposite. It’s the same trap with “what will I say?” in place of “will I halt?”, which makes it easier to check. First we hand it to the honest Oracle from cs.oracle, who answers by running the program, and then to two Oracles who answer without thinking.

The first four lines of output are the contrarian itself, a finite and perfectly ordinary program. To find out what it prints, the honest Oracle runs it; the program asks the Oracle again, and the Oracle runs it again. He will never answer, and we stop him on the fourth round. The two “dishonest” Oracles answer at once, and both are wrong: the contrarian says the opposite. The last line confirms that the contrarian handed the Oracle its own text, character for character.

What worked here always works. In 1938 Stephen Kleene proved the recursion theorem: whatever transformation of program texts we take, there is a program that gets its own text and applies that transformation to it. Printing itself is a special case, the transformation “change nothing”; that is the quine of Chapter 0. Asking the Oracle about itself and doing the opposite is another.

Act three. The diagonal

All programs can be written out in one infinite list: programs are finite texts, and finite texts can be ordered by length and, among texts of the same length, alphabetically. Let $P_0, P_1, P_2, \ldots$ be this list. Number the inputs too: $0, 1, 2, \ldots$ Now make an infinite table in which cell $(i, j)$ says whether program $P_i$ halts on input $j$. If the Oracle existed, he could fill in any cell.

Walk down the diagonal, through the cells $(0, 0), (1, 1), (2, 2), \ldots$, and build a program $D$ that on input $n$ does the opposite of what cell $(n, n)$ says: if $P_n$ halts on input $n$, $D$ loops forever, and vice versa. $D$ differs from $P_0$ on input 0, from $P_1$ on input 1, from every $P_n$ on input $n$. So $D$ is not in the list. But the list holds every program, and $D$ is a program: if the Oracle exists, such a program is easy to write, since it only has to call him on each diagonal cell. The contradiction is the same as with the contrarian, and no wonder: the contrarian is $D$ asked about itself.

Georg Cantor used the same argument in 1891 to prove that there are more real numbers than natural numbers: see day three of “Infinities” in the math course. And it has a consequence stronger than the theorem itself. Programs form a countable set: they can be numbered. But there are as many yes-or-no problems about natural numbers as there are subsets of the natural numbers, since each problem is the set of numbers for which the answer is yes. Cantor’s diagonal shows that there are uncountably many such sets. There aren’t enough programs to go around, and undecidable problems are the overwhelming majority. What is strange is rather the reverse: how often the problems we meet in practice turn out to be decidable.

Act four. Modest questions

This argument is called a reduction. Problem A reduces to problem B if every input of A can be mechanically turned into an input of B with the same answer. Then a solver for B would solve A as well. And the other way round: if A is undecidable, then so is B, or else the solver for B would solve A. Reduction is the main tool of this part of the course: in the next chapter it will be used to prove that a problem is hard.

The reduction to the “hello” question fits in three lines:

The word “silently” isn’t there for decoration. If P prints “hello” on its own and then hangs, Q must not pass that answer off as its own. And if P crashes with an error, that counts as halting too, and Q still has to reach its last line. Turning the scheme into working code is the task “The reduction” at the end of the chapter. The same scheme works for any other “modest” question.

None of the workshop’s questions mentions halting. Will there be a division by zero? Will the program go online? Will it return 42? Will it delete a file? These are questions about what a program does. And the same scheme worked for each of them: run P silently, then do whatever the question asks about. In 1951 Henry Gordon Rice noticed that this works for every such question and proved it in his dissertation; the theorem was published in 1953.

Rice’s theorem is a short answer to a great many practical questions. There is no perfect antivirus: “the program infects other files” is a property of behavior. Fred Cohen, one of the first people to study computer viruses, was already running experiments in 1983, as a student of Leonard Adleman (the “A” in RSA from Chapter 60). In a 1984 paper (the journal version came out in 1987) Cohen proved that no algorithm can detect every possible virus. There is no perfect type checker: “the program never adds a string to a number” is a property of behavior, and that is why mypy in Chapter 53 rejected innocent programs. For the same reason no linter will find all the dead code, no optimizer will produce the best possible program, and no tests can prove that a program has no bugs.

And yet analyzers exist and earn their keep. Each one breaks one of the Oracle’s three promises (always to answer, to answer correctly, to answer about any program), and it chooses which. Some don’t always answer: “I don’t know” is an answer too, and checkers that ask you for type hints work this way. Others make mistakes, but on the safe side. A type checker rejects whatever looks doubtful (better a false alarm than a missed bug), while a signature-based antivirus, the other way round, lets unfamiliar programs through but almost never raises a false alarm. A common case is a time limit, the Oracle’s strategy from the prelude, only admitted openly: when time runs out, a trustworthy tool says “I don’t know,” and a hasty one risks being wrong. And the third kind changes the language. If programs are written in a language that isn’t Turing complete, like the Starlark configurations from the last chapter, Rice’s theorem doesn’t apply to them, and a great deal becomes decidable.

Act five. The beavers

We met them on the sixth level of the game in the last chapter. In 1962 Tibor Radó asked: how many steps can a Turing machine with $n$ states and the symbols 0 and 1 make, started on a blank tape, if it does eventually halt? The maximum is called the busy beaver number $BB(n)$, and a machine that reaches it is a champion.

The machines below are written the way the bbchallenge project writes them: one row per state, and in each row one rule per symbol, saying what to write, which way to move and which state to go to; Z means halt. The cs.turing module from the last chapter reads this notation with the function standard.

Six steps, twenty-one, a hundred and seven. The five-state champion hasn’t halted after a million steps and isn’t about to: it needs 47,176,870. In the course sandbox that would take seconds, and on a busy server it might not fit into a cell’s time limit. A browser needs only a fraction of a second, and in the race below you can run the champion all the way to the end.

Five states took that much effort, and six may never yield, because the beavers are the halting problem in different clothes.

The same argument shows that $BB(n)$ grows faster than any computable function: if some computable $f$ had $BB(n) \le f(n)$ for all $n$, then $f$ could take the place of $BB$ in the proof. The numbers bear this out. For six states it is known that $BB(6)$ is at least $2 \uparrow\uparrow\uparrow 5$, a tower of twos whose height is itself a tower of twos 65,536 high. And there is a machine with 745 states that halts only if ZFC, the system of axioms on which nearly all of mathematics rests, is inconsistent. If ZFC is consistent, it cannot prove that this machine never halts, and so it cannot pin down $BB(745)$ either. Here the halting problem meets Gödel’s theorem from Königsberg.

Act six. Collatz

At the end of June 2024, when the proof for five states was already finished, the bbchallenge participant mxdys reported a six-state machine whose behavior looked random, and soon a participant who goes by Racheline worked out what it does. The machine was named Antihydra. Stripped of detail, it runs this process:

Over and over, the number is multiplied by one and a half with any half dropped, and the counter gains two points for every even value and loses one for every odd one. The machine halts if the odd values ever outnumber the even ones by more than two to one, because then the counter goes below zero. If the parity of the numbers behaves like a coin, odd values are on average as common as even ones, the counter grows, and getting below zero becomes harder and harder. Most likely Antihydra never halts. But proving that means solving a problem of the same kind as the Collatz conjecture, a question about how a simple arithmetic rule behaves at every step at once. Mathematics doesn’t yet know how to solve such problems, and so $BB(6)$ runs into an unsolved problem before undecidability even enters the picture.

The link between Collatz and this chapter goes deeper than coincidence. In 1972 John Conway, the inventor of Life from the last chapter, looked at generalized Collatz rules of the form “if $n$ leaves remainder $r$ when divided by $m$, replace it with $a_r n + b_r$,” where the coefficients are fractions chosen so that the result stays a whole number. Conway proved that for such rules the question “will the number reach one?” is undecidable: any Turing machine can be programmed in them. Later he built the language FRACTRAN on this idea, in which a program is nothing but a list of fractions. The Collatz conjecture itself may turn out to be true, false or unprovable; but the question it belongs to is undecidable in general.

Finale. The shop closes

Tasks

Three tasks. In the first you become the contrarian: your program has to get its own text without reading a file and fool any Oracle. In the second you turn the reduction from Act four into working code, and the tests probe the traps it usually falls into. In the third you write a beaver simulator fast enough to run millions of steps.

What next

The border is drawn: there are problems no machine will ever solve. But the other side of the border isn’t all sunshine either. Take a formula with a hundred logical variables joined by “and,” “or” and “not,” and ask whether they can be given values that make it true. This problem is decidable in the plainest possible way: try every assignment of values, since there are finitely many. The catch is that there are $2^{100}$ of them, about $1.3 \cdot 10^{30}$, and a computer checking a billion assignments a second would need about three thousand ages of the universe to get through them.

Decidable doesn’t mean doable: some problems would keep you waiting longer than the universe has existed. Can such a problem be solved quickly, without trying everything? Checking a ready answer is easy: substitute the values into the formula. But finding one? In 1956 Kurt Gödel wrote a letter about this to John von Neumann, the man who had once taken him aside in Königsberg after his announcement. Von Neumann was dying by then, and the question in the letter is still open. It is the subject of the next chapter.