The Birth of Computation
ver. 1.0.0, birth_of_computation
How the modern, mathematical notion of computation arose and what it lets us prove
This unit traces the origin of “computation” as a precise mathematical concept: from Babbage and Lovelace’s mechanical insight, through Hilbert’s demand for a mechanical decision procedure and Gödel’s limitation on formal systems, to Turing’s machine and Church’s lambda calculus and their agreement (the Church–Turing thesis). By the end, a learner can explain these milestones and their implications for what can and cannot be decided algorithmically.
The unit tells the origin story of computation as a rigorous mathematical object. It begins with Babbage’s Analytical Engine and Ada Lovelace’s insight that a mechanical device could manipulate symbols, not just numbers, opening the idea of programmable machinery. It then presents David Hilbert’s program—especially his Entscheidungsproblem—which asks for a fixed, mechanical procedure to decide the truth of mathematical statements.
Kurt Gödel’s incompleteness theorem is explained next: in any consistent formal system rich enough to express arithmetic there are true statements that cannot be proven within the system. This result delivers the first serious obstacle to Hilbert’s hope for a complete mechanical decision procedure.
Alan Turing provides a precise mathematical model of “mechanical procedure” by defining the abstract Turing machine: a finite set of states and rules operating on an infinite tape. Turing uses this formal model to re‑derive Gödel‑style limits, demonstrating that undecidability is an inherent feature of computation, not an artifact of informal definitions. Independently, Alonzo Church develops the lambda calculus, a minimalist formalism for functions and substitution. The two formalisms are shown to be computationally equivalent, a convergence captured by the Church–Turing thesis: the informal notion of “effectively calculable” coincides with what those formal systems compute.
By the end of the unit, learners can place these historical developments in context, state Hilbert’s Entscheidungsproblem, explain Gödel’s barrier to complete formalization, describe Turing machines and lambda calculus as precise models of computation, state the Church–Turing thesis and why independent agreement matters, and connect these ideas to further study of Turing machines and lambda calculus and to the fundamental limits on algorithmic decidability explored in the next unit.
Materials
Source document
- Course material, Ken Pu