Chapter 2: The Universal Machine
Цей контент ще не доступний вашою мовою.
Cast of characters
| Name | Lifespan | Role |
|---|---|---|
| David Hilbert | 1862–1943 | Göttingen mathematician; with Ackermann’s 1928 Grundzüge der theoretischen Logik (ch. 3) and his Bologna ICM address that same year, posed the Entscheidungsproblem. |
| Kurt Gödel | 1906–1978 | Vienna logician; the 1931 Monatshefte paper (Theorem VI) showed any ω-consistent recursive extension of Principia Mathematica contains formulas neither provable nor disprovable — demolishing completeness while leaving decidability standing. |
| Alonzo Church | 1903–1995 | Princeton assistant professor; lambda-calculus founder; presented the negative answer to the AMS on April 19, 1935 and published it in Am. J. Math. April 1936 — first to the result. |
| Stephen Cole Kleene | 1909–1994 | Church’s just-graduated Princeton Ph.D.; joint developer of λ-definability; independently proved λ-definability equivalent to Gödel-Herbrand recursiveness. |
| Alan Turing | 1912–1954 | Fellow of King’s College, Cambridge (1935); independently solved the Entscheidungsproblem via the a-machine model in “On Computable Numbers” (received LMS 28 May 1936); §6 introduced the universal computing machine. |
| Max Newman | 1897–1984 | Cambridge mathematician; his foundations-of-mathematics lectures introduced Turing to the Entscheidungsproblem; wrote to Church recommending Turing for Princeton. |
Timeline (1928–1938)
timeline title The Entscheidungsproblem from Hilbert to Princeton 1928 : Hilbert and Ackermann publish Grundzüge der theoretischen Logik (Berlin) : Hilbert's Probleme der Grundlegung address at the Bologna ICM 1931 : Gödel publishes Über formal unentscheidbare Sätze in Monatshefte 38 1935 : April 19 — Church presents An Unsolvable Problem to the AMS 1936 : March — Church's JSL note extends the result to Hilbert-Ackermann's first-order logic : April — Church 1936 published in Am. J. Math. : May 28 — LMS receives Turing's On Computable Numbers : August 28 — Turing finishes the appendix from the Graduate College, Princeton : November 12 — Turing's paper read before the LMS 1937 : Turing 1936 published in Proc. London Math. Soc. (2) 42 : March — Church's JSL review of Turing 1936 coins "Turing machine" 1938 : Turing submits Systems of Logic Based on Ordinals (supervisor: Church) : Summer — Turing returns to BritainPlain-words glossary
- Entscheidungsproblem — German for “decision problem.” Hilbert’s 1928 demand for a mechanical procedure that, given any first-order logical formula, decides in finite time whether the formula is provable. The chapter’s load-bearing question.
- Lambda calculus (λ-calculus) — Church’s symbolic system for defining mathematical functions, developed from the late 1920s onward. A function is written as a λ-expression; what gets computed is what reduces to a normal form by a finite chain of conversion rules.
- a-machine — Turing’s term for his abstract device: a finite-state scanner moving along an infinite tape divided into squares, reading and writing one symbol at a time per a finite table of m-configurations. Church’s 1937 review renamed it the “Turing machine.”
- Universal computing machine (U) — Turing’s fixed machine for simulating any other computing machine from an encoded description on its tape. Introduced in §6 of Turing 1936.
- Recursive function — A function definable from basic arithmetic operations by a finite sequence of substitutions, primitive-recursive constructions, and minimization. Built up by Gödel and Herbrand by 1934; Kleene proved it equivalent to λ-definability.
- Church-Turing thesis — The philosophical claim that recursive, λ-definable, and Turing-computable functions all capture the intuitive notion of “effectively calculable.” A thesis, not a theorem; asserted in §7 of Church 1936 and the appendix of Turing 1936.
The challenge was laid out clearly, in the third chapter of a textbook that would come to define the foundational crisis of early twentieth-century mathematics. In Grundzüge der theoretischen Logik, published in Berlin in 1928, David Hilbert and Wilhelm Ackermann systematically formulated what they called the Entscheidungsproblem. The problem asked a seemingly straightforward question about the absolute limits of formal logic: is there a “general process” for determining whether any given formula of the functional calculus is provable? The ambition was concrete: a finite procedure that any sufficiently patient computer — a human one, in 1928 — could mechanically execute, taking a logical formula as input and emitting a single bit of output (provable or not provable) without recourse to ingenuity or insight.
Hilbert, the most influential mathematician of his generation, had spent the preceding decades trying to secure the foundations of mathematics against the creeping paradoxes of set theory. His broader program rested on the hope that all mathematical truths could be formalized into a rigorous, mechanical system. In historical retrospectives, Hilbert’s ambition is often decomposed into three distinct requirements: completeness, ensuring that every true mathematical statement could be proved within the system; consistency, ensuring that the system could never prove a contradiction; and decidability, the demand that a mechanical procedure must exist to determine the truth or falsity of any formal assertion. The Entscheidungsproblem was the demand for decidability. Unlike completeness, which spoke to what the system could in principle demonstrate, decidability spoke to what a machine could in finite time decide. If it could be solved positively, mathematics would be reducible, in principle, to the mechanical execution of a finite set of rules.
The first two pillars of Hilbert’s program collapsed almost immediately. In October 1930, Kurt Gödel, a young Austrian mathematician, announced a devastating discovery to the Vienna Academy of Sciences. The following year, he published the detailed proof in Monatshefte für Mathematik und Physik, in an austere paper of dense formal logic titled “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.”
Gödel’s paper demolished both completeness and consistency-from-within. His Theorem VI stated that any ω-consistent recursive extension of Principia Mathematica contains arithmetical formulas that are neither provable nor disprovable within the system itself. Gödel meticulously demonstrated that neither such a statement nor its negation could be proved by the system’s own rules, provided the system was ω-consistent — the technical condition Theorem VI required, which Rosser would later strengthen to plain consistency in 1936. The dream of a complete formal system was permanently dead.
The proof rested on a coding device of remarkable economy. Gödel devised a numbering scheme that assigned every symbol, every formula, and every proof in the language of Principia Mathematica a distinct natural number, so that statements about what the system could prove became, formally, statements about ordinary arithmetic — claims the system itself could express. From inside this arithmetised metalanguage Gödel built the formula r: a sentence that, decoded, asserted its own unprovability. If the system proved r, it had proved a statement that denied the existence of any such proof. If it proved r’s negation, it had asserted that an unprovable formula was provable. Provided the system was consistent, neither branch was open. Some arithmetical truth, Gödel had shown, lay beyond the reach of every consistent formal axiomatisation strong enough to express it.
Yet, as devastating as Gödel’s incompleteness theorem was to the mathematical orthodoxy of 1931, it did not entirely close the book on Hilbert’s foundational questions. Gödel had proved that formal systems have blind spots, but he had not proved that it was impossible to identify where those blind spots were. Decidability—the Entscheidungsproblem—was technically a separate question. Was there a mechanical procedure that could examine a statement and correctly report whether it was provable or unprovable?
This gap was explicitly recognized by the very people who would eventually close it. Alan Turing himself drew the distinction carefully. “It should perhaps be remarked that what I shall prove is quite different from the well-known results of Gödel,” Turing would write five years later. “On the other hand, I shall show that there is no general method which tells whether a given formula is provable.” Gödel had proved that mathematics was incomplete. It would take two other mathematicians, working independently and on opposite sides of the Atlantic, to prove that mathematics was also undecidable.
The Parallel Discovery
Section titled “The Parallel Discovery”The first person to prove the unsolvability of the Entscheidungsproblem was Alonzo Church, an assistant professor of mathematics at Princeton University. Working with his former student Stephen Cole Kleene, Church had spent the early 1930s developing a new formal system called the lambda calculus. Through a series of stepping-stone publications in the Annals of Mathematics and the American Journal of Mathematics, Church and Kleene refined the lambda calculus until it was robust enough to serve as a rigorous theory of computability. The framework had emerged from Church’s earlier work on the foundations of logic in the late 1920s and matured through joint development with Kleene across the early 1930s, with the technical machinery carried forward in increments by Church’s contribution to Annals of Mathematics volume 34 in 1933 and Kleene’s longer paper in American Journal of Mathematics volume 57 in 1935. By 1935 it was the established framework for the small Princeton circle’s work on computability.
On April 19, 1935, Church presented his findings to the American Mathematical Society. A full year later, in April 1936, the detailed formal proof appeared in the American Journal of Mathematics under the title “An Unsolvable Problem of Elementary Number Theory.” A more compact companion piece, explicitly extending the result to Hilbert and Ackermann’s formulation, appeared concurrently in the Journal of Symbolic Logic in March 1936.
The year-long interval between presentation and publication is itself part of the story. Church’s argument had been circulating among foundational logicians for over a year by the time Turing’s manuscript reached London. The chronology mattered: Church had reached the negative answer first, and the published record fixed that priority before the second proof of the same theorem was even committed to type.
Church’s 1936 paper is a masterpiece of abstract formal logic. In its seventh section, titled “The notion of effective calculability,” Church made a crucial conceptual leap. He proposed that the intuitive, informal idea of an “effectively calculable” function should be strictly identified with the formally defined class of recursive functions, or equivalently, with the functions definable in his lambda calculus. Church was careful to frame this equivalence not as a mathematical theorem that could be proved, but as a foundational definition. “This definition is thought to be justified by the considerations which follow,” Church wrote, “so far as positive justification can ever be obtained for the selection of a formal definition to correspond to an intuitive notion.” This philosophical assertion is what modern computer science refers to as Church’s thesis.
Having locked down the definition of computability, Church proceeded to prove its limits. His Theorem XVIII established that the property of a well-formed formula having a normal form is not a recursive property. From there, Theorem XIX delivered the fatal blow. “There is no recursive function of two formulas A and B,” Church wrote, “whose value is 2 or 1 according as A conv B or not” — no algorithm, in modern terms, capable of deciding whether two well-formed lambda-formulas could be reduced to one another by a finite chain of conversion rules. The undecidability of conversion was, in turn, the lever by which Church pried open the decision problem of Principia Mathematica itself. The paper concluded with a direct corollary targeting the heart of Hilbert’s remaining program. The Entscheidungsproblem of any ω-consistent system strong enough to allow certain comparatively simple methods of definition and proof—explicitly singling out the system of Principia Mathematica—was mathematically unsolvable.
Church’s proof was correct, exhaustive, and rigorously complete. He had arrived at the negative answer to the Entscheidungsproblem first. Yet his formulation, expressed entirely in the dense, austere syntax of the lambda calculus, did not mention computing machinery at all. The proof was a triumph of formal logic, but it lacked a physical metaphor. It was an argument about the interconvertibility of abstract symbols. In Church’s own 1937 review of Turing’s paper, he favoured Turing’s machine model for its intuitive effectiveness — an early acknowledgement that the lambda calculus, mathematically unassailable, did not on its own offer the conceptual bridge to a physical apparatus that Turing’s a-machine had supplied. The translation of this abstract impossibility result into a physical architecture would come from a young graduate student working entirely independently in England.
The Paper Tape
Section titled “The Paper Tape”At King’s College, Cambridge, Alan Turing had been elected a fellow in 1935, at the remarkably young age of twenty-two, on the strength of a dissertation concerning the Central Limit Theorem. According to standard biographical accounts, Turing had attended lectures on the foundations of mathematics given by Max Newman, which likely served as his introduction to the Entscheidungsproblem. Working alone for the better part of a year, completely unaware of the lambda calculus circulating in Princeton, Turing attacked the problem by stripping the act of computation down to its most primitive, mechanical essence. The image at the centre of his paper was not, in the first instance, a machine: it was a clerk — a person reading symbols off a sheet of paper, consulting a fixed table of rules, and writing fresh symbols in response. What he produced was the rigorous mathematical translation of this human clerk into a finite formal specification, and only then a piece of imagined hardware that could execute the specification automatically.
Turing’s manuscript, “On Computable Numbers, with an Application to the Entscheidungsproblem,” was received by the London Mathematical Society on May 28, 1936. Rather than relying on recursive functions or abstract symbolic logic, Turing grounded his proof in a thought experiment about a hypothetical machine.
In the opening section of his paper, Turing introduced what he called the “computing machine” (and later, the “a-machine,” for automatic machine). “We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions,” Turing wrote. He stripped away all human intuition, leaving only a scanner moving along a one-dimensional tape divided into squares. “The machine is supplied with a ‘tape’ (the analogue of paper) running through it, and divided into sections (called ‘squares’) each capable of bearing a ‘symbol’.” At any given moment, the machine’s behavior was completely determined by two factors: its current internal state — which Turing called its “m-configuration” — and the single symbol currently visible under the scanner. From that pair, a finite table specified three things: the symbol the scanner should write back into the present square (perhaps the same symbol, perhaps a fresh one); the direction the tape should move next (one square left, one square right, or stationary); and the next m-configuration the machine should adopt. There were no clocks. There were no random fluctuations. There was no operator. The entire dynamics of the system were encoded in that single finite table, which Turing rendered explicitly for several worked examples in the early sections of his paper.
Turing made one further preliminary distinction. “If at each stage the motion of a machine … is completely determined by the configuration,” he wrote in section two, “we shall call the machine an ‘automatic machine’ (or a-machine).” A separate class — the “choice machine,” which left some moves to be resolved by an external operator — was set aside; everything that followed concerned the strictly automatic case.
Within the class of automatic machines Turing drew a further sharp distinction between two types. A machine that only ever printed a finite number of output symbols (figures of the first kind) and then ceased to produce more was labeled “circular.” A machine that continued to print output symbols infinitely was “circle-free.” The computable numbers, Turing argued, were precisely those sequences produced by circle-free machines.
Having established this mechanical vocabulary, Turing proceeded to his paper’s eighth section, where he unleashed a diagonal argument to prove that certain machines could never exist. He posed a question: could one invent a general-purpose machine, called D, that could examine the blueprint of any other machine and successfully decide whether that machine was circle-free? Through a rigorous logical contradiction, Turing showed that if machine D existed, it could be used to construct a paradoxical machine that defied its own operational rules. “Thus both verdicts are impossible,” Turing concluded, “and we conclude that there can be no machine D.”
He then generalized this finding into what would become the cornerstone of theoretical computer science. There could be no machine E, Turing proved, “which, when supplied with the S.D [standard description] of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say).” In modern computer science textbooks, this concept is universally known as the Halting Problem, a didactic name popularized in 1958 by the mathematician Martin Davis. Turing himself never used the word “halting,” framing his proof strictly around the concepts of circle-freeness and the printing of specific symbols.
The final step was to bring this mechanical impossibility back to Hilbert. In the paper’s eleventh section, Turing reduced the Entscheidungsproblem to the print-symbol problem. He demonstrated how to construct a logical formula, Un(M), which would be provable within the functional calculus if and only if a given computing machine M ever printed the symbol 0. Because his eighth section had just proved that no general mechanical process could determine whether M prints 0, it necessarily followed that no general process could determine whether the formula Un(M) was provable. The conclusion was absolute: “the Hilbert Entscheidungsproblem can have no solution.”
The reduction unfolded in two short lemmas. Lemma 1 demonstrated that for any computing machine M, the formula Un(M) was provable in the functional calculus K precisely when M ever printed the symbol 0; Lemma 2 reversed the implication. Stitched together, the two lemmas converted the print-symbol question — which section eight had just shown to be mechanically undecidable — into a question about formal provability. Hilbert had asked whether the truths of mathematics were reducible to a procedure. Turing answered that there was no procedure here. The negative result Church had reached through the symbolic combinatorics of the lambda calculus, Turing had reached through a finite-state device reading a tape.
The Birth of Software
Section titled “The Birth of Software”The unsolvability of the Entscheidungsproblem was the stated goal of Turing’s paper, but the paper’s enduring historical legacy lies nestled in its sixth section. It was here, almost as a mechanical convenience to facilitate his broader proof, that Turing introduced a concept that would quietly revolutionize human technology.
“It is possible to invent a single machine which can be used to compute any computable sequence,” Turing wrote. He called this theoretical construct the universal computing machine.
Prior to this paragraph, computation had been imagined as a realm of bespoke, single-purpose mechanisms. A machine was physically configured to perform one specific calculation. If you wanted to compute a different sequence, you had to build a different machine with a different table of m-configurations.
Turing shattered this assumption. He observed that the table of instructions governing any specific computing machine M could itself be encoded as a string of letters and numbers—what he called its standard description, or S.D. Because the S.D was just a sequence of symbols, it could be written out onto the squares of a paper tape. Therefore, one could construct a single, fixed-hardware universal machine, U. “If this machine U is supplied with a tape on the beginning of which is written the S.D of some computing machine M,” Turing explained, “then U will compute the same sequence as M.”
In section seven, Turing committed nearly five pages of his paper to the detailed instruction table that defined U’s behavior. Each row specified an m-configuration, the symbol presently scanned, the symbol to be written in its place, the direction of head movement, and the next state. The table was finite. It could, in principle, be transcribed by any sufficiently patient clerk and verified line by line. Turing’s purpose in section seven was to put the universal machine beyond the reach of accusation: it was not a hand-waved metaphor invoked for proof’s sake but an explicit mechanism whose behavior could be checked symbol by symbol. He had described, with the rigor a draftsman applies to a load-bearing beam, the mathematical specification of a programmable computer more than a decade before any such machine existed in copper and steel.
The architectural implications of the universal computing machine were profound. By demonstrating that a machine’s instruction table could be encoded onto the very same tape that held its input data, Turing collapsed the fundamental substrate distinction between the mechanism of control and the material being controlled. The hardware of the machine — its physical read/write head and its internal state register — could remain entirely fixed. The machine’s behavior would be dictated entirely by the “program” fed to it as data. The data, in turn, was indistinguishable from the program.
Before 1936, the physical artefacts of calculation embodied two distinct categories of object. There were programs — physically embodied as the gear ratios of a mechanical calculator, the patches in a tabulator’s plugboard, or the cams of a music box — and there were data, the workpieces those programs operated on. The two were ontologically separate: a program was something built; data was something processed. Turing’s universal machine erased that distinction. The instruction table of any machine M, encoded as an S.D, was a finite string of symbols. Strings of symbols were exactly the kind of thing a computing machine read and wrote. To run M, one supplied U with M’s S.D as input, and the universal machine ran it. Programs were a species of data. Data could become a program. Both lived on the same paper tape, indistinguishable in form.
Turing did not invent the physical computer in 1936. The chapter of history detailing how engineers translated these abstract concepts into vacuum tubes and silicon, struggling through the physical bottlenecks of memory and processing speed, belongs to the post-war efforts of the 1940s. It would be an anachronism to claim that the universal computing machine of 1936 was the blueprint for the EDVAC or the ENIAC. What Turing did in 1936 was mathematically describe the fundamental architectural object that makes the category of “software” logically coherent.
What §6 produced was a complete mathematical specification of an architecture. The hardware was finite. The behavior was deterministic. The input format — a tape carrying the S.D of some machine M — was defined; the operational semantics — the table for U printed in section seven — was defined. What was missing was a physical instance. No vacuum-tube assembly, no relay bank, no electromechanical contraption in any laboratory in 1936 answered to the universal machine’s specification. The architecture existed the way an unbuilt building exists in an architect’s drawings: completely described, entirely insubstantial. More than a decade before any engineer would wire together a physical stored-program machine, Turing had mapped the theoretical territory in which they would build. Bridging from specification to instance is the work of the next several chapters of this book.
The Princeton Connection
Section titled “The Princeton Connection”The story of the universal machine’s reception is ultimately a story of the fragile, analog infrastructure of 1930s mathematics. There were no digital networks to synchronize discoveries; there were only the transatlantic postal steamers carrying academic journals between England and the United States, with transit times often stretching to a week or more.
Mid-1930s foundational mathematics ran on the speed of mail. Issues of the Proceedings of the London Mathematical Society and the American Journal of Mathematics travelled by ship between Britain and the United States, and the discovery of an overlap between Church’s and Turing’s results travelled at the cadence of journal publication and personal correspondence rather than instant exchange.
Sometime between the London Mathematical Society receiving Turing’s manuscript on May 28, 1936, and the end of August, Turing learned of Alonzo Church’s parallel work. In a footnote added to the first page of his paper, Turing acknowledged Church’s “recent paper” in the American Journal of Mathematics, as well as the companion note in the Journal of Symbolic Logic.
Rather than withdrawing his own manuscript in the face of Church’s priority, Turing realized that his mechanical approach and Church’s symbolic approach were describing the exact same mathematical frontier. He drafted a three-page appendix to his paper over the months that followed. Dated “Added 28 August, 1936,” the appendix was titled “Computability and effective calculability.” It opened with an explicit statement of its purpose: “The theorem that all effectively calculable (λ-definable) sequences are computable and its converse are proved below in outline.” Turing’s strategy was to show two directions of inclusion separately — the easy direction, that every Turing-computable sequence had a corresponding lambda expression, and the harder direction, that every λ-definable sequence was producible by some Turing machine. With both inclusions established, λ-definability and computability were not merely co-extensive labels but provably the same mathematical class.
The appendix carried a telling return address: “The Graduate College, Princeton University, New Jersey, U.S.A.”
By the autumn of 1936, Turing had crossed the Atlantic to study under Church at Princeton. (According to standard biographical accounts of Turing’s Princeton residency, his arrival in the United States marked the beginning of a two-year period during which he held a Procter Visiting Fellowship and submitted his doctoral thesis, “Systems of Logic Based on Ordinals,” under Church’s supervision in 1938.)
The mathematical community quickly synthesized the parallel discoveries. In March 1937, Alonzo Church published a brief review of Turing’s paper in the Journal of Symbolic Logic. It was in this review that Church famously coined the term “Turing machine” to describe Turing’s a-machine. More importantly, Church conceded that Turing’s mechanical formulation possessed a distinct conceptual advantage over his own lambda calculus. Computability by a Turing machine, Church wrote, “has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately.”
With Turing’s appendix, the theoretical foundations of computer science locked into place. The triangle of formal equivalences was complete: Church’s λ-definability, the Gödel-Herbrand framework of general recursiveness (which Kleene had recently proven equivalent to λ-definability), and Turing-computability all perfectly bounded the exact same class of mathematical functions.
The mathematical proof of their equivalence was a theorem; Turing’s appendix demonstrated it, and Kleene’s prior equivalence between λ-definability and Gödel-Herbrand recursiveness had closed the third side of the triangle. The philosophical assertion that this specific, formal class of functions perfectly captured the informal, human intuition of what it meant to be “effectively calculable” — that was, and remained, a thesis. Today the proposition is known as the Church-Turing thesis, honoring both the man who first formalised the boundary and the man who gave the boundary its most enduring mechanical metaphor.
The year 1936 was not the year the computer was invented. No physical machine was built, no wires were soldered, and no vacuum tubes were illuminated. The universal computing machine existed only as a sequence of logical propositions printed on the pages of the Proceedings of the London Mathematical Society. But 1936 was the year that computation ceased to be merely an activity that humans performed, and became instead a rigorously defined mathematical object. The Entscheidungsproblem had fallen. The era of software had quietly begun.