Unlimited Register Machines, Gödelization and Universality
summary
Defines an Unlimited Register Machine formalism and shows a working Clojure DSL and interpreter that executes URM programs, adds convenience instructions (push, pop, copy) to avoid astronomic runtimes, and implements Gödelization to turn programs into numbers by encoding pairs and lists. Demonstrates encoding the add program as a single huge number and evaluating it (e.g. 5+5 produces 10), outlines how parity marks instruction types, and sketches a concrete Universal URM construction aimed at a mechanized undecidability proof.
AI-written summary · about
chapters (8)
- 0:00Introduction to URMs
- 1:09Defining register machines
- 5:22Executing programs
- 9:53Multiplication and complexity
- 13:14Building a Clojure DSL
- 15:15Universality and Gödelization
- 20:22Data encoding techniques
- 25:07Universal machine conclusion
related talks
50mTuring's Toy - The story of a mathematical idea that changed the world
31mThe Shoulders of Giants or Uncovering the Foundational Ideas of Lisp
50mImpossible Programs
44mTuring's Toy - The story of a mathematical idea that changed the world
01h 23mGerald Jay Sussman keynote and discussion
31mOrthogonal Remarks
41mFinite of sense & infinite of thought
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back