Turing's Toy - The story of a mathematical idea that changed the world
summary
A clear, concrete retelling of how Turing formalizes computation with a three-part machine (finite states, infinite tape, read/write head) and then shows there is no algorithm to decide provability: he defines description numbers, builds a universal Turing machine that interprets them, and uses a self-referential construction (machine A/“age”) to force a contradiction, proving the halting/decidability problem unsolvable and connecting that result back to Hilbert, Gödel and Church.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 3:57The Hilbert Program
- 6:01The PreSPEA Mathematica
- 10:26Alan Turing
- 11:16The Turing Machine
- 12:16State Machines
- 21:45Expression
- 23:19Standard Description
- 24:41Universal Machine
- 25:48Description Number
- 27:57Circular and Circle Free
- 29:14Machine Age
- 31:30Pseudocode
- 35:54The halting problem
- 37:05Alonzo Church
related talks
50mTuring's Toy - The story of a mathematical idea that changed the world
41mFinite of sense & infinite of thought
50mImpossible Programs
31mThe Shoulders of Giants or Uncovering the Foundational Ideas of Lisp
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
01h 01mThe Gospel According to TCS
53mThe Shoulders We Stand On
43mWhat is a computer program? Historical & philosophical reflections