The Birth of Computation

Computation and Turing Machines · v1.2.1

2026-09-13 13:19:27

Outline of key topics

• The mechanical precursors: Babbage’s Analytical Engine and Lovelace’s insight
• Hilbert’s challenge: the 10th Problem and the Entscheidungsproblem
• Gödel’s incompleteness theorem and the first negative answer
• Turing’s formalization of mechanical procedure
• Church’s lambda calculus and the Church-Turing thesis

The through-line of the unit is a single question — can mathematics be decided mechanically — and the fact that answering it required first inventing a definition of “mechanically”.

Before the beginning

Babbage’s Analytical Engine

Charles Babbage and the Engine’s mechanism.

The first mechanical computer

• designed to evaluate polynomial functions
• cost £17,000
• under construction for ten years
• terminated before completion, when the British Treasury lost confidence

The Engine’s machinery

What the machine is made of

• gears, rods and cams
• no electricity, no transistor
• computation carried out by clockwork

Lovelace and the first algorithm

Ada Lovelace and her tabulation table.

Beyond arithmetic

• recognised the Engine’s potential beyond arithmetic
• wrote one of the first algorithms ever written
• a tabulation method computing the Bernoulli number sequence

Lovelace on the Engine’s reach

[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…

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.

Countess of Lovelace Augusta Ada King, 1843

The claim in the passage

• The Engine’s operations are not tied to numbers
• A domain whose relations can be expressed in the Engine’s notation can be operated on by the Engine
• Pitch and harmony are such a domain: the output is music, not a numerical result
• Computation is symbol manipulation according to rules, with number as one instance of a symbol

This is the premise lambda calculus is built on directly.

Worth returning to explicitly when Church’s system appears later in the unit: lambda calculus computes by substituting symbols, with no notion of number built in — the thing Lovelace anticipated a century earlier.

Hilbert’s challenge

Two questions, thirty years apart

David Hilbert.

What was asked

• 1900 — the 10th Problem, on deciding integer solutions of Diophantine equations
• 1928 — the Entscheidungsproblem, on deciding sentences of first-order logic

The 10th Problem, 1900

A Diophantine equation has a polynomial left-hand side with integer coefficients and finitely many unknowns at integer powers, and zero on the right:

\[x^2 + 78xy - y^6z = 0\]

• Hilbert asked for a procedure deciding, for an arbitrarily given such equation, whether integer solutions exist
• The procedure must work for every equation of this form, not for a family chosen in advance

The Entscheidungsproblem, 1928

• Given first-order logic and a set of consistent axioms, is it always possible to decide whether a sentence is true or false?
• The question is whether solutions to mathematical problems can be procedurally derived, always, provided the system is properly well-defined
• Its scope is all of mathematics expressible in first-order logic, not one problem within it

The undefined term

• “Procedurally derived” and “mechanically decided” presuppose a precise notion of procedure
• No such notion existed in 1928
• The Entscheidungsproblem is a question about computation, asked before the term had a formal meaning

Answering Hilbert required inventing the definition first.

Gödel and the first blow

Gödel’s answer, 1931

Kurt Gödel.

The result

• the Entscheidungsproblem answered negatively, three years after it was posed
• established by construction, not by a general argument
• the construction rests on integer arithmetic being axiomatizable in first-order logic

The construction

• Gödel formulated a logical sentence describing a specific property of a number, now called Gödel’s number
• The sentence cannot be derived by logical deduction from the axioms
• The property it describes nonetheless holds: the sentence is true but unprovable within the system
• A consistent formal system containing such a sentence is called incomplete

The consequence for Hilbert

• A set of consistent axioms can be asserted, and a question posed in first-order logic that cannot be decided true or false within that system
• The sentence is unsolvable because no derivation exists, not because none has been found
• Hilbert’s demand for a universal decision procedure cannot be met

The consequence for the 10th Problem

• Many problems in integer arithmetic are solvable within mathematical logic
• The general Diophantine equation problem — Hilbert’s own 1900 question — is not: it is undecidable over the integers
• Relaxing the solution space to the real numbers makes it decidable again

The undecidability is specific to the integers.

Turing formalizes computation

Turing’s machine, 1936

The Turing Machine.

The formalization

• at 24, Alan Turing formalized reasoning as computation
• defined concretely as a mechanical device: the Turing Machine
• precise enough to be reasoned about mathematically

Reproducing incompleteness

• Turing reproduced Gödel’s 1931 incompleteness result using the machine
• The same conclusion, reached from within a mechanical framework rather than a purely logical one
• Turing’s proof is described as much closer to today’s concept of programming than Gödel’s

Why the machine matters beyond Hilbert

• The Entscheidungsproblem depends on the phrase “mechanical procedure”
• The Turing Machine gives that phrase something precise to refer to
• Every later question about what can and cannot be computed becomes a question about this machine, or about a system proven equivalent to it

Turing is widely considered the father of theoretical computer science.

Church and the second formalization

Church’s lambda calculus, 1936

Alonzo Church.

The second system

• a string rewrite system for reasoning about mathematical functions, their definitions and their actions
• called the Lambda Calculus
• Church was Turing’s PhD advisor at Princeton, before the Second World War

The equivalence and its bound

• Lambda Calculus and the Turing Machine were soon discovered to be equivalent
• Together they model the most powerful computation possible: one universal upper bound on the ability of computation
• A system computing everything either can compute is Turing complete

The Church-Turing thesis

The claim

No system computes more than this bound.

Where its weight comes from

• Turing’s machine: a tape, a head, a table of rules
• Church’s calculus: function definitions and a substitution rule, with no notion of machine at all

Two systems built from such different machinery agreeing on one boundary is treated as evidence the boundary is a fact about computation.

Church’s answer to Hilbert

• Church used the Lambda Calculus for the purpose Turing used the machine: proving the Entscheidungsproblem unsolvable
• Both routes delivered the same answer, independently, in the same year
• Not every first-order logic assertion can be mechanically decided

This is the point at which to connect back to Lovelace: Church’s system computes by symbol substitution, with numbers nowhere in its machinery — exactly the kind of non-numeric operation her passage describes.

Where this course goes

The result this unit builds toward

• Two independently invented formal systems, arrived at in the same year
• Both define the same boundary of computability
• That boundary, Turing Completeness, sets the shape of what the course covers next

The Turing Machine units

• The module’s later units build Turing’s machine in full
• Its states, its tape, its transition rules
• What it means for a language to be decided, or merely recognized, by a machine
• The Limits of Computation returns to the negative answer Gödel and Church reached, and asks what it means for a problem to have no algorithm at all

The Lambda Calculus module

• A later module does for Church’s system what those units do for Turing’s
• Terms and reduction, the calculus’ two ingredients
• How ordinary constructs — booleans, integers, recursion — are built from nothing but functions

Both modules are formal treatments of the two systems introduced here.

Summary

Summary

• Babbage’s Analytical Engine; Lovelace saw past number to symbols
• Hilbert’s Entscheidungsproblem: is mathematics mechanically decidable?
• Gödel answered no: truths a consistent arithmetic system cannot prove

• Hilbert’s 10th Problem inherits that undecidability over the integers
• Turing and Church formalized computation independently in 1936, and agreed
• Their agreement evidences the Church-Turing thesis

Where next

The Birth of Programming Languages — the next unit in this module.

• von Neumann’s EDVAC turning the abstract machine into physical architecture
• The major language paradigms that followed, from FORTRAN and Lisp onward