The Limits of the Computer — Turing, Gödel, Cohen

What can a given formal system or algorithm fail to decide? Gödel showed in 1931 that effectively axiomatized systems strong enough for arithmetic are incomplete; Turing showed in 1936 that no algorithm decides the halting problem in general. Gödel’s 1940 and Cohen’s 1963 complementary relative-consistency results established that CH is independent of ZFC.

About 30 min·5 nodes

Progress0 / 5 (0%)

The path across the map

Select a card to move the map to that location.

STEP 1 · Concept1931No location

Incompleteness Theorems

A consistent, effectively axiomatized formal system strong enough for arithmetic has sentences it cannot prove and, under the theorem's conditions, cannot prove its own consistency.

↓5 years later

STEP 2 · Concept1936Cambridge· Discovery

Computability

The mathematical study of what fixed procedures can compute. In 1936 Church and Turing clarified its power and limits with different formal models.

↓4 years later

STEP 3 · Mathematician1940Princeton· Publication

Kurt Gödel

A logician who established mathematical limits of formal systems. At age 24, Gödel informally announced his first incompleteness result in a Königsberg discussion on 7 September 1930; the paper stating both theorems appeared in January 1931. Under their stated assumptions, effectively axiomatized systems strong enough for arithmetic contain sentences they cannot decide and generally cannot prove their own consistency.

↓8 years later

STEP 4 · Mathematician1948Manchester· Teaching and work

Alan Turing

A mathematician who changed what it means to ask whether a problem is mechanically solvable. His 1936 abstract machine clarified computability and its limits. At Bletchley Park he made central contributions to Bombe design and Enigma cryptanalysis within a large collaborative effort; exact claims about years shortened or lives saved are estimates, not settled measurements. He later worked on computers, machine intelligence, and morphogenesis in Manchester. Convicted in 1952 for a homosexual relationship, he was forced to undergo hormonal treatment. He died from cyanide poisoning in 1954. The inquest ruled suicide, while his mother maintained that it was an accident; the apple beside him was never tested.

↓15 years later

STEP 5 · Concept1963Stanford· Discovery

Continuum Hypothesis

Is there an infinity between the natural numbers and the reals? Gödel’s 1940 and Cohen’s 1963 complementary relative-consistency results established that CH is independent of ZFC.

EXPERT → RESEARCH FRONTIER

The expert stage ends with a better question.

Separate proved results from conjectures, inspect current evidence, and choose a boundary where your own inquiry can begin.

Next takeaway · One open question worth following

Explore open problems