Impossible Programs
summary
Claim: some programs are provably impossible. Using self‑interpreters and simple program constructions the talk shows how does-it-say-no and do-the-opposite force nontermination and prove the halting problem undecidable by reduction. Tools: universality (implement interpreters in other languages), encoding programs as data, Rice’s theorem, the Omega combinator and a Goldbach example (conjectured since 1742 and checked up to 4 quintillion). Consequence: no general automatic checker can always decide interesting runtime properties like “prints Hello World.”
AI-written summary · about
chapters (9)
- 0:00Start
- 4:53Universal Systems
- 23:54Removing Unlimited Iterations
- 29:54Halting Problem
- 30:20Does this Program Always Finish
- 42:39Turing Reduction
- 45:50Computational Irreducibility
- 46:15Girdle's First Incompleteness Theorem
- 48:31Unreachable Code Elimination
related talks
50mTuring's Toy - The story of a mathematical idea that changed the world
44mTuring's Toy - The story of a mathematical idea that changed the world
01h 01mKeynote: Six Impossible Things
01h 01mThe Gospel According to TCS
33mUnlimited Register Machines, Gödelization and Universality
41mFinite of sense & infinite of thought
43mWhat is a computer program? Historical & philosophical reflections
31mThe Shoulders of Giants or Uncovering the Foundational Ideas of Lisp