Project SherlockEst. Knowledge

Paper

1936

On Computable Numbers, with an Application to the Entscheidungsproblem

Alan Turing

Defines the universal machine and proves the halting problem undecidable — the founding document of computer science.

Before you start

Assumes: no computer science, but genuine comfort with formal proof, and patience for 1936 notation

If this is the wrong level

Too hard? Start hereMath's Fundamental FlawDerek Muller (Veritasium), 2021Traces the route from Cantor's diagonal argument through Godel's incompleteness theorems to Turing's halting problem, arguing they are three faces of one limit on formal systems.

Filed under Foundations & Logic in Mathematics.