Lecture notes — The Birth of Computation
ver. 1.2.1, birth_of_computation
ver. 1.2.1 · 2026-09-13 03:10 UTC
Where this fits
This is the first unit of the curriculum. Nothing is assumed beyond ordinary mathematical literacy: what a function is, what an equation is, what it means for a statement to be true or false. Every later unit in the course — Turing machines, lambda calculus, Clojure, Kotlin — takes for granted that “computable” has a precise mathematical meaning. This unit is where that meaning came from.
Learning outcomes
place-babbage-and-lovelace— Place Babbage’s Analytical Engine and Lovelace’s insight as the mechanical precursors to computation.state-hilberts-challenge— State Hilbert’s Entscheidungsproblem as a demand for a mechanical decision procedure.explain-godels-consequence— Explain what Gödel’s incompleteness theorem showed and why it struck the first blow against Hilbert’s program.explain-turings-formalization— Explain how Turing’s machine gave mechanical computation a precise mathematical definition.explain-churchs-lambda-calculus— Explain Church’s lambda calculus as an independent formalization of computable functions.state-church-turing-thesis— State the Church-Turing thesis and what it means for two independently invented systems to agree.connect-history-to-course— Connect this history to the two modules that follow it in the course.
Concepts introduced
- Analytical Engine — the mechanical computer Charles Babbage designed to evaluate polynomial functions, and the machine Ada Lovelace wrote algorithms for.
- Hilbert’s Problems — the list of unsolved mathematical problems David Hilbert posed in 1900, including the 10th Problem on Diophantine equations.
- Entscheidungsproblem — Hilbert’s 1928 question of whether every first-order logic statement can be mechanically decided true or false.
- Gödel’s Incompleteness — Kurt Gödel’s 1931 theorem that any consistent formal system capable of arithmetic contains true statements it cannot prove.
- Turing Machine — Alan Turing’s 1936 abstract mechanical model, precise enough to reason about mathematically.
- Lambda Calculus — Alonzo Church’s 1936 formal system for defining and evaluating functions by substitution.
- Church-Turing Thesis and Turing Completeness — the claim that Turing machines and lambda calculus mark the same, universal upper bound on computation.
Before the beginning
Charles Babbage designed the Analytical Engine, the first mechanical computer, with the goal of computing polynomial functions. It cost £17,000 and was terminated after ten years, before completion, when the British Treasury lost confidence in the project.
Ada Lovelace recognised the Analytical Engine’s potential beyond arithmetic. She developed one of the first algorithms ever written for it, using a tabulation method to compute the Bernoulli number sequence.
Lovelace went further than the machine’s original purpose. She wrote:
[The Analytical Engine] might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine…
Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.
Her claim was that the Engine’s operations were not tied to numbers. If a domain’s relations — pitch, harmony — could be expressed in the Engine’s notation, the Engine could operate on that domain, producing music rather than a numerical result. This is the premise lambda calculus, later in this unit, is built on directly: computation as symbol manipulation according to rules, with numbers as one instance of a symbol rather than the subject matter itself.
Charles Babbage, and the mechanism of the Analytical Engine he designed to evaluate polynomial functions. The Engine was never completed: after a decade of construction and £17,000 of funding, the British Treasury withdrew its confidence in the project.
The Analytical Engine’s machinery — gears, rods and cams. There is no electricity anywhere in the design and no transistor; the arithmetic is carried out entirely by clockwork, which is what makes the Engine a mechanical computer rather than a calculating aid.
Ada Lovelace, and the tabulation table she wrote for the Analytical Engine. The table computes the Bernoulli number sequence, and is one of the first algorithms ever written for a machine.
Learning outcomes
- place-babbage-and-lovelace Place Babbage’s Analytical Engine and Lovelace’s insight as the mechanical precursors to computation.
Concepts
- analytical-engine designed by Babbage to evaluate polynomial functions, funded at £17,000, and the machine Lovelace’s Bernoulli-number algorithm and symbolic-manipulation insight were both written for
Hilbert’s challenge
David Hilbert asked two related questions, thirty years apart.
In 1900, Hilbert posed his 10th Problem. A Diophantine equation is an equation whose left-hand side is a polynomial with only integer coefficients and finitely many unknowns raised to integer powers, and whose right-hand side is zero — for example, \(x^2 + 78xy - y^6z = 0\). Hilbert asked whether there is a procedure to decide, for an arbitrarily given Diophantine equation, whether it has integer solutions.
In 1928, before the 10th Problem was fully understood, Hilbert posed a broader question: the Entscheidungsproblem. Given first-order logic and a set of consistent axioms, is it possible to always decide whether a sentence is true or false? It questions whether solutions to mathematical problems can be procedurally derived, always, provided the mathematical system is properly well-defined.
The Entscheidungsproblem is a question about computation itself, asked before the term had a formal meaning. “Procedurally derived” and “mechanically decided” presuppose a precise notion of procedure that did not yet exist in 1928. Answering the question required inventing that notion first — which is what the rest of this unit is about.
David Hilbert, who posed both questions this section turns on: the 10th Problem in 1900, on deciding whether a Diophantine equation has integer solutions, and the Entscheidungsproblem in 1928, on deciding sentences of first-order logic.
Learning outcomes
- state-hilberts-challenge State Hilbert’s Entscheidungsproblem as a demand for a mechanical decision procedure.
Concepts
- hilberts-problems the 1900 list of challenge problems, including the 10th Problem on deciding integer roots of Diophantine equations
- entscheidungsproblem the 1928 question of whether every first-order logic sentence can always be decided true or false
Gödel and the first blow
Kurt Gödel answered Hilbert’s Entscheidungsproblem negatively in 1931, three years after Hilbert posed it — and did so by construction rather than by a general argument.
It is well known that integer arithmetic is axiomatizable in first-order logic. Gödel formulated a logical sentence describing a specific property of a number, now called Gödel’s number. He showed that this sentence cannot be derived by logical deduction from the axioms, and yet the property it describes holds — the sentence is true, but unprovable within the system. A consistent formal system in which such a sentence exists is called incomplete.
The consequence: it is possible to assert a set of consistent axioms and pose a question in first-order logic that cannot be decided, either true or false, within that system. The sentence is unsolvable, not because no one has found the derivation, but because none exists.
A related consequence follows for the 10th Problem directly. Many problems in integer arithmetic can be solved easily, but some cannot be solved within mathematical logic — and the surprise is that the general Diophantine equation problem, Hilbert’s own 1900 question, is among them. It is undecidable over the integers, though it becomes decidable if the solution space is relaxed to the real numbers.
Kurt Gödel, whose 1931 incompleteness theorem answered the Entscheidungsproblem negatively. He established the result by explicit construction — a sentence that is true of the numbers and underivable from the axioms — rather than by a general argument.
Learning outcomes
- explain-godels-consequence Explain what Gödel’s incompleteness theorem showed and why it struck the first blow against Hilbert’s program.
Concepts
- godels-incompleteness a consistent formal system capable of integer arithmetic contains statements that are true but unprovable within it, constructed explicitly via Gödel’s number
- entscheidungsproblem answered in the negative: not every first-order sentence can be decided true or false
- hilberts-problems the general Diophantine equation problem, Hilbert’s 10th, inherits Gödel’s undecidability
Turing formalizes computation
In 1936, at 24, Alan Turing formalized reasoning as computation, defining it concretely as a mechanical device now known as the Turing Machine. Turing is widely considered the father of theoretical computer science and artificial intelligence.
With the Turing Machine, Turing was able to reproduce the incompleteness result of Gödel — arriving at the same conclusion Gödel had reached in 1931, but from within a mechanical framework rather than a purely logical one. Turing’s proof of incompleteness is described as much closer to today’s concept of programming than Gödel’s was.
That closeness is the reason the Turing Machine matters beyond settling Hilbert’s question. It gave “mechanical procedure” — the phrase the Entscheidungsproblem depends on — something precise to refer to. Every later question about what can and cannot be computed is now a question about this machine, or a system proven equivalent to it.
The Turing Machine, illustrated alongside the discussion of Turing’s incompleteness result. Reproducing Gödel’s conclusion inside a mechanical framework is what gave the phrase “mechanical procedure” something precise to refer to.
Learning outcomes
- explain-turings-formalization Explain how Turing’s machine gave mechanical computation a precise mathematical definition.
Concepts
- turing-machine the 1936 abstract mechanical model Turing used to formalize algorithmic reasoning and reproduce Gödel’s result in a programming-oriented framework
- godels-incompleteness reproduced by Turing using the machine, rather than Gödel’s original purely logical construction
Church and the second formalization
Also in 1936, Alonzo Church proposed a string rewrite system for formally reasoning about mathematical functions, their definitions and their actions. This rewrite system is Lambda Calculus. Church was Turing’s PhD advisor at Princeton, before the Second World War.
Lambda Calculus and the Turing Machine were soon discovered to be equivalent. Together, Church and Turing’s systems model the most powerful computation possible: they define the same universal upper bound on the ability of computation. This bound is called Turing Completeness — a system that can compute everything a Turing Machine or Lambda Calculus can compute is Turing complete.
The belief that no system can compute more than this bound is the Church-Turing Thesis. Its evidential weight comes specifically from the independence of the two systems: Turing’s machine is built from a tape, a head and a table of rules; Church’s calculus is built from function definitions and a substitution rule, with no notion of “machine” at all. That two systems built from such different machinery agree on the same boundary is treated as evidence the boundary is a fact about computation, not an artifact of either system’s particular design.
Church used his own system for the purpose Turing used his: proving the unsolvability of the Entscheidungsproblem. Both routes, independently, delivered the same answer to Hilbert’s 1928 question: no, not every first-order logic assertion can be mechanically decided.
Alonzo Church, Turing’s PhD advisor at Princeton. His Lambda Calculus reaches the same boundary as the Turing Machine from entirely different machinery: function definitions and a substitution rule, with no notion of a machine in it at all.
Learning outcomes
- explain-churchs-lambda-calculus Explain Church’s lambda calculus as an independent formalization of computable functions.
- state-church-turing-thesis State the Church-Turing thesis and what it means for two independently invented systems to agree.
Concepts
- lambda-calculus Church’s 1936 rewrite system for functions, proven computationally equivalent to the Turing Machine
- turing-machine shown equivalent to Lambda Calculus, establishing the shared upper bound of computation
- church-turing-thesis the claim that this shared bound, Turing Completeness, is the universal limit no computational system exceeds
- entscheidungsproblem answered unsolvable a second time, independently, by Church using Lambda Calculus
Where this course goes
Two independently invented formal systems, arrived at in the same year, define the same boundary of computability. That is the result this unit has been building toward, and it sets the shape of what follows: two more units in this module, and a later module in the course.
The next two units in this module build Turing’s machine in full: its states, its tape, its transition rules, and what it means for a language to be decided or merely recognized by one. The Lambda Calculus module, later in the course, does the same for Church’s system: terms, reduction, and how ordinary constructs such as booleans, integers and recursion are built from nothing but functions. Both are formal treatments of the two systems introduced here.
The next unit in this module, The Limits of Computation, returns to the boundary Gödel and Church located — the Entscheidungsproblem’s negative answer — and asks what it means, precisely, for a problem to have no algorithm at all.
Learning outcomes
- connect-history-to-course Connect this history to the two modules that follow it in the course.
- state-church-turing-thesis State the Church-Turing thesis and what it means for two independently invented systems to agree.
Conclusion
Charles Babbage designed the Analytical Engine, and Ada Lovelace saw past its arithmetic.
Lovelace’s insight that the Engine could manipulate any domain whose relations could be expressed in its notation, not numbers specifically, anticipates the premise lambda calculus is built on: computation as symbol manipulation, with number as one instance rather than the subject.
Hilbert’s Entscheidungsproblem asked whether mathematics could be mechanically decided, and Gödel answered first, negatively.
Gödel’s 1931 incompleteness theorem showed that a consistent formal system capable of arithmetic contains true statements it cannot prove — a purely logical result that also settled Hilbert’s 10th Problem, since the general Diophantine equation question inherits the same undecidability.
Turing and Church formalized “mechanical procedure” independently, in 1936, and agreed.
The Turing Machine and Lambda Calculus were shown computationally equivalent despite sharing no machinery. Their agreement is the evidence for the Church-Turing thesis: that this shared boundary, Turing Completeness, is the universal limit of computation.
The next unit, The Limits of Computation, stays with the negative answer Gödel and Church both reached and asks what proving it precisely requires — a question this unit’s Turing Machine and Lambda Calculus are the tools for answering.
References
- Course material, Ken Pu