Chapter 3 The limits of formalism

17 minute read

Illustration for Chapter 3, The limits of formalism

On September 8, 1930, the 68-year-old German mathematician David Hilbert delivered a famous retirement address in his hometown of Königsberg, soon broadcast on German radio. Hilbert was the undisputed leader of the mathematical world, and for three decades he had championed an ambitious campaign to place all of human reasoning on an unbreakable foundation. At the close of his speech, he pushed back against philosophical skeptics who claimed that some truths would forever elude science. In mathematics, Hilbert declared, there is no ignorabimus—there is nothing we cannot know. We must know, he insisted, and we will know. Those words were later engraved on his tombstone in Göttingen.

Hilbert did not know that one day earlier, on September 7, 1930, the 24-year-old logician Kurt Gödel had quietly announced a discovery in Königsberg that shattered Hilbert's dream.

To secure mathematics forever against paradoxes like Russell's, Hilbert had demanded an axiomatic system that satisfied three strict criteria. First, the system had to be complete, meaning that for every mathematical statement, the axioms could formally prove either the statement or its negation. Second, the system had to be consistent, meaning it could never prove both a statement and its negation, and that this consistency could be proved by finite reasoning. Third, the system had to be decidable, meaning there existed a finite mechanical procedure that could determine in finitely many steps whether any statement was provable.

Within six years, between 1931 and 1936, Kurt Gödel, Alonzo Church, and Alan Turing shattered all three pillars of Hilbert's program. They proved that any mathematical system rich enough to describe ordinary whole-number arithmetic is necessarily incomplete, cannot prove its own consistency, and admits no universal algorithm for deciding truth. Yet in uncovering the inescapable limits of formal reasoning, they gave birth to the modern digital computer and the science of information.

3.1Syntax and meaning in formal systems

To understand how Gödel and Turing proved what mathematics can and cannot do, we must separate two worlds that human minds constantly blur together: syntax and semantics. Semantics is the realm of meaning and truth. When we read that two plus three equals five, we understand what the words mean and recognize a truth about quantities. Syntax, by contrast, is the realm of pure form. It treats formulas as meaningless strings of ink marks on paper, manipulated according to rigid typographical rules.

Why did Hilbert care so deeply about separating syntax from semantics? Because human intuition about meaning is fallible, as Russell's paradox had painfully demonstrated. If you want to be 100% certain that a mathematical proof contains no hidden assumptions or leaps of faith, you must strip away all appeal to human intuition. Checking a proof must become a purely mechanical task that a clerk—or a machine—can verify simply by inspecting how symbols are arranged on a page.

A formal system is built from four explicit syntactic ingredients. First comes a finite alphabet of basic symbols, such as logical connectives, quantifiers, variables, the equals sign, zero, the successor symbol, and arithmetic plus and times signs. Second comes a grammar, which specifies exactly which finite strings of symbols from the alphabet form grammatically valid sentences, known as well-formed formulas.

The third ingredient is a set of starting formulas called axioms, chosen so a machine can always decide whether a candidate formula is an axiom. The fourth ingredient is a finite set of rules of inference, which are mechanical recipes for producing new formulas from existing ones. The most famous rule of inference is modus ponens. Whenever a first formula and an implication from that first formula to a second formula have been written down, modus ponens permits writing the second formula.

Inside a formal system, a formal proof is a finite list of well-formed formulas. Every line in the list must either be an axiom or follow from earlier lines by a rule of inference. The final line of a valid proof is called a theorem of the system. Because every step in a formal proof is governed by strict pattern-matching rules, verifying whether a sequence of formulas is a valid proof is completely mechanical. A computer does not need to understand infinity or geometry to check whether line 42 follows from lines 17 and 29 via modus ponens. By turning mathematical deduction into a rule-bound game of symbol manipulation, Hilbert made mathematical proof itself a mathematical object that could be studied with absolute precision.

3.2Gödel numbering and self-reference

How did Kurt Gödel turn Hilbert's syntactic machinery against itself? A formal system like Peano arithmetic is designed to talk about whole numbers—their sums, products, and prime factors. It has no built-in vocabulary for talking about formulas, axioms, or proofs. Gödel realized, however, that every symbol, formula, and proof can be encoded as a unique natural number. Once that encoding is in place, statements about whole numbers can simultaneously act as statements about the formal system itself.

This encoding technique, now called Gödel numbering, was the first time in history that symbolic rules and data were unified into a single numerical representation. We begin by assigning a small code number to each basic symbol in our formal alphabet. For example, we can assign the code 1 to zero, 2 to the successor symbol, 3 to plus, 4 to times, and 5 to the equals sign.

Next, suppose we have a well-formed formula made of a sequence of symbols. How do we pack that entire sequence of symbols into a single natural number without losing track of their order? Gödel used the fundamental theorem of arithmetic, which guarantees that every integer greater than one factors uniquely into a product of prime numbers—two, three, five, seven, 11, and so on. We take the first prime numbers in order and raise each prime to the code number of the corresponding symbol in the formula. Multiplying those prime powers together produces the Gödel number ⌜ϕ⌝\ulcorner \phi \urcorner of the formula:

⌜ϕ⌝≡∏i=1kpig(si)\ulcorner \phi \urcorner \equiv \prod_{i=1}^{k} p_i^{g(s_i)}

Consider the tiny formula stating that zero equals zero. It consists of three symbols with code numbers one, five, and one. Its Gödel number is two raised to the first power, times three raised to the fifth power, times five raised to the first power, which equals 2,430. Because prime factorization is unique, anyone handed 2,430 can factor it into primes, read off the exponents one, five, and one, and reconstruct the original formula.

Gödel did not stop with individual formulas. A formal proof is a sequence of formulas, each of which already has its own Gödel number. We can raise the first prime to the Gödel number of the first line, the second prime to the Gödel number of the second line, and so on. Multiplying those prime powers together encodes an entire multi-page proof into a single enormous natural number.

This double encoding translates every syntactic question about formulas and proofs into an arithmetic question about the prime factors of whole numbers. Checking whether a list of formulas is a valid proof is a purely mechanical step-by-step calculation on prime exponents. Consequently, Gödel showed that the relation between a proof number and the formula number it proves can be written down explicitly as an equation inside elementary arithmetic.

By prefixing the existential phrase "there exists a proof number" to that proof-checking relation, Gödel constructed the arithmetic provability predicate ProvF(x)\text{Prov}_{\mathcal{F}}(x). Inside the formal system, this arithmetic formula asserts that there exists a natural number encoding a valid formal proof of the target formula. Arithmetic has learned to talk about provability.

To close the loop of self-reference, Gödel adapted Cantor's diagonal argument to prove what is called the diagonal lemma. Suppose we have any arithmetic property with one free variable. The diagonal lemma states that we can always construct a sentence whose truth inside the formal system is equivalent to applying that property to the sentence's own Gödel number.

How does a sentence manage to talk about its own code number without circularity? Define the diagonal substitution operation, which takes the Gödel number of any one-variable formula. It then computes the Gödel number of the sentence obtained by plugging that very code number into the formula itself. Because substituting a numeral into a formula is a mechanical manipulation of prime exponents, this diagonal operation can be written directly inside arithmetic. When we compose our chosen property with this diagonal operation, we get a one-variable formula with some concrete Gödel number. Plugging that concrete number into the combined formula itself produces a sentence whose subject is its own Gödel number. By feeding a formula its own numerical blueprint, Gödel forged a mirror of pure arithmetic.

3.3The first and second incompleteness theorems

With the provability predicate and the diagonal lemma in hand, Gödel needed only one step to detonate Hilbert's program. Apply the diagonal lemma to the property of not being provable in the formal system. That immediately produces a specific arithmetic sentence GG, now famous as the Gödel sentence, satisfying:

F⊢(G  ⟺  ¬ProvF(⌜G⌝))\mathcal{F} \vdash \left( G \iff \neg \text{Prov}_{\mathcal{F}}(\ulcorner G \urcorner) \right)

At the surface level of syntax, the Gödel sentence is a dry statement about the prime factorizations of gigantic whole numbers. Yet because those prime factorizations encode the rules of the formal system, the sentence simultaneously asserts at the level of meaning that it is not provable in the formal system. It is a mathematical version of the ancient liar paradox, except that "I am false" has been replaced by "I am unprovable."

Can the formal system prove the Gödel sentence? Suppose first that the system could prove it. Then there would exist an actual formal proof having some concrete Gödel number. Because proof checking is purely mechanical, the formal system can verify that concrete number and prove that the Gödel sentence is provable. At the same time, however, the diagonal equivalence tells us that if the Gödel sentence holds, then it is not provable. Thus, if the Gödel sentence were provable, the formal system would prove both that it is provable and that it is not provable, violating consistency. Assuming our formal system is consistent—free of contradictions—we are forced to conclude that the Gödel sentence cannot be proved inside the system.

Here comes the decisive twist. Because we have just established that the Gödel sentence has no formal proof in the system, the statement that it is unprovable is a true fact about whole numbers. And since the Gödel sentence asserts its own unprovability, the Gödel sentence itself must be true. We have found a true statement of arithmetic that the formal system is powerless to prove. Under Gödel's stronger assumption of omega-consistency—that the system never claims a number exists while refuting every concrete whole number—it cannot prove the negation of the Gödel sentence either. In 1936, Barkley Rosser constructed a modified self-referential sentence that compares proof lengths, proving that ordinary consistency alone leaves both his Rosser sentence and its negation unprovable.

This is Gödel's first incompleteness theorem: any consistent, mechanically specified formal system capable of expressing elementary arithmetic is necessarily incomplete. There will always exist true statements about whole numbers that cannot be proved from its axioms.

A natural temptation is to try to repair the system by simply adding the unprovable Gödel sentence to our list of axioms, forming a stronger formal system. In the upgraded system, the old Gödel sentence is now trivially provable in one line. Have we sealed the gap? Not at all. Because the upgraded system is still a mechanical formal system, it has its own upgraded provability predicate. Applying the diagonal lemma to that new predicate immediately produces a brand-new sentence asserting that it is not provable in the upgraded system. Once again, the new sentence is true, and once again the upgraded system cannot prove it. No matter how many axioms you add, mathematical truth always outruns formal provability.

Even more sobering was Gödel's second incompleteness theorem, which struck down Hilbert's hope of proving that mathematics is free of contradictions. We can write an arithmetic sentence asserting that our formal system is consistent—for example, by stating that the equation "zero equals one" has no formal proof.

Recall the first half of our argument for the first incompleteness theorem. There we showed that if the formal system is consistent, then the Gödel sentence cannot be proved inside the system. Because the Gödel sentence is equivalent to stating its own unprovability, that conditional argument can be formalized inside the system itself: consistency implies the Gödel sentence.

Suppose the formal system could prove its own consistency. Applying modus ponens to that implication would allow the system to prove the Gödel sentence immediately. Yet the first incompleteness theorem already established that a consistent system can never prove its Gödel sentence. Therefore, no consistent formal system rich enough to contain arithmetic can ever prove its own consistency. To prove that a formal system is consistent, you must always step outside it into a strictly stronger system, whose own consistency then remains an article of faith.

3.4Turing machines and the halting problem

After Gödel demolished completeness and self-consistency in 1931, one piece of Hilbert's program still remained standing: the decision problem, or Entscheidungsproblem. Even if some truths are unprovable, could there still be a mechanical procedure that decides in finitely many steps whether any given formula is provable?

To answer this question, someone first had to define what a "mechanical procedure" or algorithm actually is. In 1935, a 22-year-old student at King's College, Cambridge, named Alan Turing went for a long run and lay down in a meadow at Grantchester. Instead of defining computation through abstract functions, as Alonzo Church was doing at Princeton, Turing asked a concrete physical question. What does a human clerk actually do when calculating with pencil and paper?

Turing realized that any calculation can be stripped down to the simplest imaginable machine. Picture an infinitely long strip of paper tape divided into squares, like a roll of film. Each square holds a single symbol from a finite alphabet. A mechanical read-write head sits over one square of the tape at a time. Inside the machine is a gearbox that can occupy a finite set of internal states, including a starting state and two halting states representing acceptance and rejection.

The entire behavior of a deterministic Turing machine is specified by a finite lookup table called its transition function. At each tick of the clock, the machine looks only at its current internal state and the single symbol printed on the square directly under its head. It consults its lookup table and executes three elementary actions. It switches to a new internal state, overwrites the current square with a new symbol, and shifts the tape head one square to the left or right. That is all.

Despite the almost childlike simplicity of this paper-tape device, the Church-Turing thesis states that any step-by-step algorithm can be carried out by a Turing machine. Indeed, any classical physical device that processes discrete symbols in finite steps computes the exact same class of functions.

Even more remarkably, because the lookup table of any Turing machine is finite, we can write down the rules of any machine as a finite string on a tape. That insight allowed Turing to design a single machine, the universal Turing machine. It reads both the encoded blueprint of any other machine and an input string, and faithfully simulates what that machine would do on that input.

Before Turing's 1936 paper, every calculating engine in history was built to do one fixed job. To change the task, you had to rewire the gears. Turing showed that a single fixed piece of hardware can perform any conceivable calculation simply by reading a new software program from its memory tape. Every laptop, smartphone, and server on Earth today is a physical realization of Turing's universal machine.

Having invented the universal computer on paper, Turing immediately used it to prove what no computer can ever do. When you run a program on an input, sometimes the machine finishes its task and halts, and sometimes it gets trapped in a loop and runs forever. Turing asked whether there exists a master debugging machine that can inspect any program and input and decide in finite time whether that program will eventually halt.

Turing proved that this halting problem is undecidable: no such debugging machine can ever exist. His proof is a direct computational twin of Cantor's diagonal argument. Suppose, for the sake of contradiction, that an always-halting debugging machine did exist. Using it as a component, we can build an adversarial machine—call it the diagonal machine—that takes the blueprint of any machine as its input. First, the diagonal machine runs the debugger to find out whether the input machine halts when fed its own blueprint as input. Second, whatever the debugger predicts, the diagonal machine does the exact opposite. If the debugger predicts that the machine will halt, the diagonal machine deliberately enters an endless loop and never halts. If the debugger predicts that the machine will run forever, the diagonal machine immediately halts.

Now comes the diagonal blow. Because the diagonal machine is a well-defined program, it has its own blueprint string. When we feed the diagonal machine's blueprint to the diagonal machine itself, a contradiction is immediate. If the diagonal machine halts, the debugger must predict that it halts; yet whenever the debugger predicts halting, the diagonal machine enters an endless loop and never halts. Conversely, if the diagonal machine runs forever, the debugger predicts that it runs forever, causing the diagonal machine to halt immediately.

Thus the diagonal machine halts if and only if it does not halt. Because the diagonal machine was built from the debugger using completely legal operations, our assumption that the halting debugger exists must be false. No algorithm can ever predict the ultimate fate of all computer programs. And if arithmetic were complete and decidable, a machine could solve the halting problem by searching all formal proofs until it proved whether a program halts or loops. Thus Turing's theorem simultaneously killed Hilbert's Entscheidungsproblem and gave an independent computational proof of Gödel's incompleteness theorem.

3.5Algorithmic complexity and halting probability

The three great limit theorems of modern mathematics—Cantor's uncountability of the continuum, Gödel's incompleteness of arithmetic, and Turing's undecidability of the halting problem—all share a single logical skeleton. Each one examines a family of objects, asks what happens along the self-referential diagonal, and applies a negation flip to construct an object that escapes the list.

In the 1960s, Andrey Kolmogorov, Ray Solomonoff, and Gregory Chaitin took Turing's universal machine one step further to answer a fundamental question about nature. What does it mean for a pattern of data to be simple, complex, or random?

Suppose you flip a fair coin 50 times and write down one for heads and zero for tails. Under classical probability theory, 50 alternating ones and zeros have the exact same probability, one in two to the 50th power, as a jumble of 50 coin tosses. Classical probability talks only about ensembles of possibilities. It has no way to look at a single individual string of bits and say whether that string contains structure or randomness.

Algorithmic information theory solves this problem by measuring complexity in terms of computer programs. Fix a reference universal Turing machine whose valid programs are prefix-free, meaning no valid program is the opening prefix of another. The Kolmogorov complexity K(s)K(s) of a binary string is the length in bits of the shortest program that makes the universal machine print out that string and halt.

Suppose a string consists of a trillion alternating ones and zeros, or the first trillion binary digits of pi. A tiny program just a few hundred bits long can generate it. Its Kolmogorov complexity is minuscule compared to its length. Scientific laws are nothing more and nothing less than short computer programs that compress vast tables of observational data.

What if a string contains no regularities at all? Then there is no way to compress it. The shortest program that prints the string is essentially to hard-code the entire string inside the program itself. Such an incompressible string is called algorithmically random. A simple counting argument known as the pigeonhole principle shows that most strings are incompressible. Because there are exponentially fewer short programs than there are long binary strings, almost all strings of any given length cannot be compressed at all. Order and compressibility are rare islands in an ocean of algorithmic randomness.

Yet here too, self-reference imposes a strict horizon on what we can prove. Just as we cannot compute whether an arbitrary program halts, we cannot compute the Kolmogorov complexity of an arbitrary string. Using a formal version of Berry's paradox—which asks for "the smallest positive integer not definable in under sixty letters"—Gregory Chaitin proved an information-theoretic incompleteness theorem. For any consistent formal system, there is a fixed complexity ceiling determined by the length of the axioms of the system itself. The formal system can never prove that any specific string has a Kolmogorov complexity exceeding that ceiling.

Why? Suppose the formal system could prove that specific strings have complexity greater than any chosen threshold. Then we could write a short search program that checks all formal proofs in the system until it finds a theorem proving some string exceeds a huge threshold. Once the program finds that theorem, it immediately prints the target string and halts. When the threshold is chosen larger than the length of our search program itself, that short program prints the target string using fewer bits than the threshold. That means the string's true Kolmogorov complexity is below the threshold, directly contradicting the theorem that the formal system just proved. A formal system whose axioms contain a given number of bits of information can never prove that any object in the universe contains more irreducible complexity than the axioms themselves.

Chaitin crystallized this limit in a single real number Ω\Omega between zero and one, called the halting probability:

Ω≡∑p halts2−∣p∣\Omega \equiv \sum_{p \text{ halts}} 2^{-|p|}

Imagine generating a computer program by flipping a fair coin for each bit of code and feeding the stream into a prefix-free universal Turing machine. Each halting program of length L bits contributes two raised to the minus L power to the sum. Thus Chaitin's number is the exact probability that a randomly generated program eventually halts.

As a mathematical constant, the halting probability is as unambiguously defined as pi or the square root of two. Yet its binary expansion is a concentrate of pure logical uncomputability. Knowing the first 1,000 bits of the halting probability would let you solve the halting problem for every program of length up to 1,000 bits. Consequently, no algorithm can compute its digits, and its binary expansion is completely incompressible. Even though Chaitin's constant is uniquely determined by pure logic, its binary digits are statistically indistinguishable from fair coin tosses, devoid of any pattern or redundancy whatsoever.

Starting from the empty set, pure logic has generated the continuum, the continuous symmetries of manifolds and Lie groups, and the boundaries of universal computation. Now those mathematical structures step out of abstraction to become space, time, matter, and energy.