Unlimited Register Machines, Gödelization and Universality
summary
Claim: a concrete universal URM via Gödelization exists and is implemented. Programs and register lists encode as numbers using a binary pair → list scheme, decoded and executed by a simulator written in Closure (and a slower JS port). The universal simulator runs on only 10 working registers, adds a few cheat ops (copy/push/pop) and shows it can simulate and compute 2+3=5; copy/push are implementable with the primitive inc/dec/branch but large numeric encodings make JS execution very slow.
AI-written summary · about
chapters (10)
- 0:00Start
- 4:29Our first program
- 8:07Graphical Representation
- 14:31Coding Pairs
- 20:34Coding Instructions
- 24:43Coding a program
- 25:53Wishful thinking
- 32:14push XL
- 35:04Next Steps
- 37:08Questions?
related talks
46mBlueprints for a Universal Reasoning Machine
20mSimulating computational complexity
27mProvably Correct, Asymptotically Efficient, Higher-Order Reverse-Mode Automatic
21mHow hard can it be! Practical uses of complexity theory
19mAll Together Now! Programming the Quantum Computer
01h 39mIsomorphic Reasoning: Counting with Types Part 1
41mQuantum Computing Deep Dive
47mBig Ideas in Program Synthesis