The limits of computation

est 40h · logged 0h · started — · touched —

Turing's 1936 "On Computable Numbers" as the computational twin of Gödel's incompleteness theorems: what a machine can compute, the undecidable halting problem, P vs NP, and the Kolmogorov/Chaitin/Solomonoff development of algorithmic information theory.

next action

done when you can

Describe a Turing machine and why it's universal.State the halting problem and explain why it's undecidable.Explain P vs NP in plain language.State what Kolmogorov complexity measures and why it's non-computable.Connect this to Gödel: computation and formal systems are two faces of the same limit.

resources

●The Nature of Computation— Cristopher Moore & Stephan Mertensanchor · book
●The Annotated Turing— Charles Petzoldcompanion · book
○Short essays on algorithmic information theory— Gregory Chaitincompanion · paper
○Introduction to the Theory of Computation— Michael Sipseroptional · book

sessions

unlocks Unit 5 (quantum computation extends this). Unit 3 of the Information page (algorithmic information). Deep integration with the Philosophy of Mind page's Unit 1 (the brain as computation question).

open in notion ↗