Unlocking Computability: Unlimited Register Machines, Gödelization & Universality 🔍

Lot's of people know about Turing Machines and the Lambda Calculus and that they both can express any computable function, but often don't really understand what that means. An Unlimited Register Machine is a simple model of a computer, still quite idealised, that is turing equivalent also.

The philosopher Dan Dennett, in his book Intuition Pumps and Other Tools For Thinking, devotes a rather large section to URMs titled The Seven Secrets Of Computing Power Revealed. The hope is that by simulating the simplest possible register machine and building up to complex algorithms you can understand what it means to compute.

In the talk I treat math(s) and 'programming' as equal citizens in terms of explaining the idea and end with an easy to understand concrete implementation of a Universal URM (via a neat way of Gödelizing programs, ie turning them into numbers)