Turing's Toy - The story of a mathematical idea that changed the world
summary
Defines a formal device with a finite-state control, an infinite tape and a read/write head, shows how to serialize any such machine into a “standard description” number and builds a single universal machine that interprets those descriptions. Constructs a self-referential machine H to prove the halting problem undecidable, which settles Hilbert’s Entscheidungsproblem as impossible. Consequence: computable numbers are countable while real numbers are not, and the later ACE implementation successfully runs Turing’s first program.
AI-written summary · about
chapters (24)
- 0:00Intro
- 3:14The "Hilbert Program"
- 5:08Principia Mathematica
- 6:19The Decision Problem Remains...
- 8:05Kurt Gödel
- 10:24Alan Turing
- 11:36The Turing Machine is Born
- 12:55The First Machine
- 14:48Producing a Number
- 17:09Computing 0.001011011101111...
- 24:06The Standardized Table
- 24:47Table in Standard Format
- 25:39Serializing a Table
- 27:14The Universal Machine
- 28:12Description Numbers
- 31:21Philosophy and the Turing Machine
- 34:17Circular and Circle-Free Machines
- 35:52Building the Machine "H"
- 38:12Pseudo Code for "H"
- 43:17Turing's Conclusion
- 44:13Alonzo Church and Lambda Calculus
- 46:18Turing After the Paper
- 47:49David Hilbert and the Nazis
- 48:50Hilbert's Tombstone in Göttingen
related talks
44mTuring's Toy - The story of a mathematical idea that changed the world
41mFinite of sense & infinite of thought
50mImpossible Programs
33mUnlimited Register Machines, Gödelization and Universality
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
31mThe Shoulders of Giants or Uncovering the Foundational Ideas of Lisp
53mThe Shoulders We Stand On
01h 01mThe Gospel According to TCS