Central Question: What is computation itself?
It is 1935, and we find ourselves in the quiet courts of King’s College, Cambridge. The great lawns stretch toward the River Cam, and the Gothic chapel casts long shadows in the afternoon light. In a modest room overlooking the college grounds, a young Fellow named Alan Turing is wrestling with one of the deepest questions in mathematics.
Turing is twenty-three years old, awkward in manner, brilliant in mind. He speaks in bursts, his thoughts often running ahead of his words. He is known around college for his long-distance running, his unmade bed, and his habit of chaining his coffee mug to the radiator to prevent theft. He has recently been elected to a Fellowship on the strength of his work in probability theory—work he produced without realizing that the central result had already been proved. When he discovered his error, he simply moved on to harder problems.
The problem now consuming him is Hilbert’s Entscheidungsproblem: Is there a definite procedure—an algorithm, we would say today—that can determine whether any given mathematical statement is true or false? We have seen how Godel shattered the dream of completeness. But the decision problem remains open. Perhaps, even if some truths cannot be proved, there is still a mechanical method to sort statements into categories.
To attack this question, Turing realizes he must first answer a more fundamental one: What exactly do we mean by a “definite procedure”? What is an algorithm? What is computation itself?
The insight that comes to him is characteristically direct. We should not begin with abstract definitions, Turing reasons. We should begin with what we can observe: a human being performing a calculation.
Picture a mathematician working at a desk. She has paper—perhaps an unlimited supply of it, stretched out like a tape. She can write symbols on the paper, read them, erase and replace them. At any moment, she is in some mental state: focused on a particular part of the calculation, remembering certain intermediate results. Her actions are governed by rules she has internalized—rules that tell her, given what she sees and what she remembers, what to do next. Write this symbol. Move attention to the left. Erase that symbol. Stop and announce the answer.
From this simple analysis, Turing constructs his machine.
The Turing machine—though Turing himself never calls it that—consists of just a few components. There is a tape, infinite in both directions, divided into cells. Each cell can hold a single symbol from some finite alphabet. There is a head that can read the symbol in the current cell, write a new symbol, and move one cell left or right. And there is a finite control mechanism that determines, based on the current symbol and the machine’s internal state, what action to take.
That is all. An infinite tape, a read-write head, and a finite set of rules. From these austere ingredients, Turing builds a complete theory of computation.
The machine operates in discrete steps. At each step, it reads the current symbol, consults its rules, writes a new symbol (possibly the same one), moves left or right, and transitions to a new state (possibly the same one). The computation proceeds until the machine enters a special halting state, at which point the answer can be read from the tape.
The elegance of this construction lies in its universality. Anything that can be computed by any mechanical process—any algorithm that a human mathematician could execute given enough time and paper—can be computed by some Turing machine. This is not a theorem that can be proved; it is a thesis, a claim about the nature of computation that must be evaluated by its consequences. We call it the Church-Turing thesis, and seven decades of computer science have only strengthened our confidence in its truth.
Consider what this means. Addition, multiplication, finding prime numbers, sorting lists, searching databases, rendering graphics, parsing language—every computational process you have ever encountered can be performed by one of these simple machines. The modern smartphone in your pocket, with its billions of transistors, its multiple cores, its gigabytes of memory, computes nothing that a Turing machine could not compute in principle. The difference is speed, not capability.
But Turing’s paper does more than define computation. It uses that definition to prove a profound negative result.
Suppose we want to build a machine that can predict whether any given Turing machine will eventually halt or run forever. This would be enormously useful. Much of debugging is precisely this question: will this program terminate, or will it loop endlessly? Surely, we might hope, there is some clever analysis that can always determine the answer.
Turing proves there is not. The halting problem is undecidable. No Turing machine—no algorithm whatsoever—can correctly determine, for every possible machine and input, whether the computation will halt.
The proof is a masterpiece of diagonal reasoning, closely related to Godel’s self-reference tricks. Suppose, for contradiction, that a halting oracle H exists—a machine that takes as input a description of any machine M and any input I, and outputs “halts” or “loops forever.” Now we construct a devious machine D. When given a description of a machine M, D runs H on the pair (M, M)—asking whether M halts when given its own description as input. If H says “halts,” D enters an infinite loop. If H says “loops forever,” D immediately halts.
Now, what happens when we run D on its own description? If H says D halts on D, then by construction D loops forever. If H says D loops forever on D, then by construction D halts. Either way, H gives the wrong answer. The oracle cannot exist.
This is not a failure of engineering. It is not that we have not tried hard enough, or that our algorithms are not clever enough. The halting problem is mathematically unsolvable. There are limits to what computation can achieve—limits inherent in the concept of computation itself.
Turing has answered Hilbert’s question with a resounding negative. The Entscheidungsproblem is unsolvable. There is no algorithm that can decide, for every mathematical statement, whether it is true or false. Mechanical reason has boundaries that no machine can cross.
But within those boundaries lies an infinite territory. Turing’s paper does not only show what cannot be done; it shows what can. And buried in the technical details is an idea that will transform the world: the universal Turing machine.
Most Turing machines are specialists. One machine adds numbers. Another sorts lists. A third checks whether strings of parentheses are balanced. Each machine has its rules hardwired into its control mechanism, fixed for all time.
But Turing shows that a single machine can simulate any other. The universal machine U takes as input a description of some other machine M, encoded as symbols on the tape, along with the input I that M is supposed to process. Machine U then simulates M running on I, step by step, producing exactly the output that M would produce.
This is the stored-program concept. The program is not separate from the data; it is data. The same machine can become any machine, simply by changing what is written on its tape. Hardware becomes software becomes computation becomes thought.
The paper appears in 1936, in the Proceedings of the London Mathematical Society, under the title “On Computable Numbers, with an Application to the Entscheidungsproblem.” It is dense, technical, and revolutionary. Within its pages lie the theoretical foundations of every computer that will ever be built.
Technical Box: Formal Definition of a Turing Machine
A Turing machine is formally specified by a 7-tuple:
M = (Q, Sigma, Gamma, delta, q_0, q_accept, q_reject)
where:
- Q is a finite set of states
- Sigma is the input alphabet (symbols that can appear on the initial tape)
- Gamma is the tape alphabet, where Sigma is a subset of Gamma and includes a blank symbol
- delta: Q x Gamma -> Q x Gamma x {L, R} is the transition function
- q_0 in Q is the start state
- q_accept in Q is the accept (halt) state
- q_reject in Q is the reject state, distinct from q_accept
The transition function delta(q, a) = (q’, b, D) means: “In state q, reading symbol a, write symbol b, move in direction D (Left or Right), and transition to state q’.”
Example: Binary Increment Machine
This machine adds 1 to a binary number. The input appears on the tape with the least significant bit at the head position.
States: {q_scan, q_carry, q_done} Input alphabet: {0, 1} Tape alphabet: {0, 1, blank}
Transitions: - delta(q_scan, 0) = (q_done, 1, R) — flip 0 to 1, we’re done - delta(q_scan, 1) = (q_carry, 0, L) — flip 1 to 0, carry left - delta(q_carry, 0) = (q_done, 1, R) — place the carry, done - delta(q_carry, 1) = (q_carry, 0, L) — continue carrying - delta(q_carry, blank) = (q_done, 1, R) — extend the number
Trace for input “11” (binary for 3):
Step Tape State Position 0 …_11_ … q_scan rightmost 1 1 …_10_ … q_carry middle 1 2 …_00_ … q_carry blank left 3 …_ 100_ … q_done halt Result: “100” (binary for 4). The machine has computed 3 + 1 = 4.
Turing is not alone in his quest. Across the Atlantic, at Princeton University, another brilliant logician has been pursuing the same quarry.
Alonzo Church is everything Turing is not: established, methodical, deeply embedded in the academic hierarchy. Born in Washington, D.C., educated at Princeton, he has spent his career building the foundations of mathematical logic with painstaking precision. His office is legendarily neat. His lectures are legendarily dry. His contributions to logic are foundational.
In 1936—the same year Turing’s paper appears—Church publishes his own answer to the Entscheidungsproblem. Like Turing, he proves that the decision problem is unsolvable. But his approach is entirely different.
Where Turing imagines machines with tapes and heads, Church invents a purely symbolic system called the lambda calculus. There are no mechanical parts, no tapes, no states. There are only functions, abstraction, and application.
In the lambda calculus, everything is a function. Numbers are functions. Operations are functions. Even the act of applying a function to an argument is itself expressed as a function. The syntax is minimal: you can define functions (using the Greek letter lambda to mark the parameter), and you can apply functions to arguments. That is all.
The number zero, for instance, is a function that takes another function and applies it zero times. The number one applies the function once. The number two applies it twice. Addition becomes function composition. Multiplication becomes iterated addition. From these strange definitions, all of arithmetic emerges—not as something built on top of the lambda calculus but as something expressed within it.
From this stark foundation, Church builds a complete system of computation. He defines what it means for a function to be “effectively calculable”—computable by his lambda calculus—and shows that certain functions are not effectively calculable. The decision problem is one of them.
When Turing’s paper reaches Princeton, Church immediately recognizes its significance—and its unexpected convergence with his own work. The two men have invented different formalisms, starting from different intuitions, yet arrived at the same boundary between the computable and the uncomputable.
This is no coincidence. Within a year, Turing proves that his machines and Church’s calculus are exactly equivalent in computational power. Any function computable by a Turing machine is expressible in the lambda calculus, and vice versa. Two utterly different models of computation turn out to define the same class of computable functions.
The convergence goes further. Emil Post, a Polish-American mathematician, independently develops yet another formalism—production systems based on string rewriting rules. Stephen Kleene formalizes recursive functions. Each approach differs in style and motivation, yet all define the same boundary.
This remarkable agreement across independent investigations is the basis of the Church-Turing thesis: the claim that any reasonable formalization of “effective computability” will capture exactly the same class of functions. The computable is not a matter of definition but a natural kind, a feature of the mathematical universe that multiple paths converge upon.
The implications are profound. Computation is not merely a human invention, a convenient abstraction. It is something real, something discovered rather than created. Just as different cultures independently develop arithmetic because numbers are “out there” in the structure of reality, so the concept of computation emerges inevitably from any serious attempt to understand mechanical procedure.
Or so the thesis claims. It cannot be proved in any formal sense—how would one formalize “reasonable”? But every attempt to challenge it has failed. Every proposed model of computation that might exceed the Turing machine has turned out to be either equivalent (quantum computers, for instance, which we will meet later) or physically unrealizable (hypercomputers that depend on infinite precision or infinite speed).
Turing arrives at Princeton in 1936 to pursue doctoral work under Church’s supervision. The collaboration is productive if awkward—Turing’s intuitive leaps and Church’s careful constructions do not always mesh. Church is methodical, insisting on complete rigor at every step. Turing is intuitive, seeing the destination clearly and impatient with the journey. Yet both are committed to the same goal: understanding the precise boundaries of mechanical reasoning.
Turing’s doctoral thesis, completed in 1938, extends these ideas by defining hierarchies of computability—degrees of unsolvability that reveal a rich structure in the landscape of the uncomputable. Some problems are not merely undecidable but more undecidable than others. The halting problem, for instance, can be used as an oracle to solve problems that no ordinary Turing machine can solve. But give a machine access to that oracle, and new undecidable problems appear. The hierarchy extends infinitely upward, a tower of unsolvability reaching beyond any horizon.
When Turing returns to England in 1938, he carries with him the completed framework for understanding what machines can and cannot do. He has mapped the borders of the computational kingdom.
He does not know it yet, but within a year, he will be asked to defend that kingdom in the most urgent application imaginable.
On September 1, 1939, German tanks roll into Poland. Two days later, Britain declares war on Germany. And a few weeks after that, Alan Turing reports to a Victorian mansion in the Buckinghamshire countryside called Bletchley Park.
The Government Code and Cypher School has assembled here the strangest workforce in British history: mathematicians, linguists, chess champions, crossword puzzle experts. They work in wooden huts scattered across the estate grounds. They observe eccentric schedules, brilliant minds keeping whatever hours suit their thinking. The atmosphere is part Oxford common room, part military installation, part asylum. Their mission is to break the communications codes of the German military. At the heart of that mission lies the Enigma machine.
Enigma is a cipher device of fiendish complexity. It uses a series of rotating wheels, each wired to perform a letter substitution, combined with a plugboard that swaps additional pairs. The combined effect is a polyalphabetic cipher with an astronomical number of possible settings—on the order of 10^23 for the naval version. Each day, German operators set their machines to a new configuration. Breaking even one day’s traffic by brute force is far beyond human capability.
The Polish Cipher Bureau had made remarkable progress against earlier Enigma versions before the war. They developed machines called “bomby” (after a type of ice cream, legend has it) to automate parts of the cryptanalysis. But German improvements to Enigma, particularly the naval version, threatened to make their methods obsolete.
Turing attacks the problem with characteristic originality. He realizes that the cryptanalysts’ goal is not to search all possible settings—that is indeed impossible—but to exploit weaknesses in how Enigma is used. German operators follow procedures. Messages begin with predictable phrases. Weather reports use standard formats. Each regularity is a crack in the cipher’s armor.
The machine Turing designs, which the British call the Bombe (after the Polish bomby), is not a computer in any modern sense. It does not execute stored programs. It does not perform general computation. It is a special-purpose device built for one task: to test Enigma settings against known or guessed plaintext, eliminating impossible configurations until the correct setting emerges.
But the Bombe embodies computational thinking at every level. It processes information systematically. It exploits logical structure. It automates what would be humanly impossible. The machine that emerges from Turing’s design—refined by the brilliant engineer Harold “Doc” Keen at the British Tabulating Machine Company—becomes the foundation of Allied signals intelligence.
By mid-1940, Bletchley Park is breaking German messages with increasing reliability. By 1942, the intelligence flowing from Enigma decrypts—codenamed ULTRA—is shaping Allied strategy across every theater. Historians continue to debate exactly how much the war was shortened by this advantage. Estimates range from two to four years. Millions of lives hang on those numbers.
Turing’s contribution goes beyond the Bombe. He becomes a central figure in the technical leadership of Bletchley Park, contributing to attacks on other cipher systems and helping to establish the statistical methods that underpin modern cryptanalysis. His 1941 memorandum to the Prime Minister, pleading for more resources for Bletchley, is credited with securing Churchill’s direct support.
But even as Enigma falls, the Germans develop more sophisticated systems. The Lorenz cipher, used for high-level strategic communications, is more complex than Enigma by an order of magnitude. Breaking it requires a different approach—and leads to a genuine first in the history of computation.
The machine that emerges is called Colossus. Designed by Tommy Flowers, a Post Office engineer with decades of experience in telephone switching systems, it becomes operational in early 1944—just in time to provide crucial intelligence for the D-Day landings. Colossus is the world’s first large-scale electronic computing device. It uses 1,500 vacuum tubes (later versions use 2,400), achieving speeds impossible with earlier electromechanical technology. It is programmable through switches and plugboards. It reads encrypted messages from paper tape at 5,000 characters per second and counts statistical patterns at electronic speed.
Flowers builds Colossus largely on his own initiative, over the skepticism of his superiors who doubt that so many vacuum tubes could operate reliably together. He is proven spectacularly right. Ten Colossus machines are eventually built, working around the clock to break German high command communications.
Colossus is not a general-purpose computer—it cannot be programmed to perform arbitrary calculations. But it demonstrates that electronic computation is practical. It shows that machines can process information at superhuman rates. And it trains a generation of British engineers in the techniques of electronic computing.
Across the Atlantic, American engineers are pursuing a parallel path. The ENIAC (Electronic Numerical Integrator and Computer), built at the University of Pennsylvania, becomes operational in late 1945. Unlike Colossus, ENIAC is designed for general computation—primarily the calculation of artillery firing tables, though it will later be applied to problems ranging from weather prediction to nuclear weapons design.
ENIAC is a monster: 17,468 vacuum tubes, 70,000 resistors, 6,000 switches, consuming 150 kilowatts of power. Programming it requires physically reconfiguring cables and switches, a process that can take days. But it computes. It processes information. It embodies Turing’s theoretical machines in 30 tons of humming electronics.
The transformation from theory to practice accelerates. John von Neumann, the Hungarian-American polymath who seems to appear wherever important science is happening, visits the ENIAC project in 1944. He is struck by the potential and frustrated by the limitations. Programming a machine by rewiring it is hopelessly impractical. There must be a better way.
The better way is already implicit in Turing’s 1936 paper: the universal machine, which treats the program as data to be read from the tape. Von Neumann synthesizes this insight with the practical lessons of ENIAC in his 1945 report on a proposed new machine, EDVAC (Electronic Discrete Variable Automatic Computer).
The von Neumann architecture that emerges from this report describes the structure of essentially every computer that exists today. There is a memory that stores both program instructions and data. There is a processing unit that fetches instructions from memory, decodes them, and executes them. There is a control unit that manages the flow of execution. Programs and data share the same memory space, the same formats, the same fundamental representation.
This is Turing’s universal machine made practical. The program is no longer frozen in hardware. It is information, stored in memory, manipulated like any other data. You can write programs that read programs. You can compile programs that translate programs. You can build operating systems that manage programs. The entire software industry, with all its layers of abstraction, descends from this single architectural insight.
By 1950, the theoretical has become tangible. Britain has the Manchester Mark 1, which runs its first program in June 1948—the first stored-program computer to operate—and the EDSAC at Cambridge, which becomes the first computer to run a practical service for scientists. America has von Neumann’s machine at the Institute for Advanced Study (affectionately called the MANIAC) and a proliferation of commercial and military projects. The Soviet Union, independently and secretly, is developing its own electronic computers. Ferranti delivers the first commercially sold computer in 1951. The age of practical computation has begun.
And Turing himself is there at Manchester, helping to program the Mark 1. The man who imagined the universal machine is now writing code for a real one. He is working on mathematical problems, on early artificial intelligence experiments, on a paper that asks the provocative question: “Can machines think?” We will return to that paper in Chapter 4.
We have traveled far in this chapter. We began with a young mathematician in Cambridge, puzzling over an abstract question about the limits of mechanical reasoning. We watched him invent an imaginary machine of infinite tape and finite rules, a machine that captures the essence of computation. We saw how that essence was discovered independently, in different forms, by minds across the world—evidence that computation is not merely convention but fundamental truth.
And we followed the strange path from theory to war, from Bletchley Park to ENIAC, from thought experiments to thirty-ton machines. The universal machine that Turing imagined in 1936 exists by 1950—not one but dozens, in laboratories and military installations on both sides of the Iron Curtain.
These machines process symbols. They execute instructions. They compute. But a question remains. We have described computation in terms of symbols and rules, tapes and transitions. But what, exactly, are the machines manipulating? What is this “information” that flows through their circuits?
This is not a philosophical quibble. The mid-twentieth century sees the emergence of a rigorous answer, a mathematical theory that treats information as a measurable quantity, as real as energy or mass. That theory will provide new foundations for computing, communications, and eventually for understanding thought itself.
We turn now to Bell Labs, 1948, and a paper that begins with the deceptively simple words: “The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point.”
The age of information is about to begin.
Next: Chapter 3 - Information as Physics