Universal Machines

One machine to run them all

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• A universal Turing machine can simulate any other Turing machine.
• This is the principle of the stored-program computer.
• Church–Turing thesis: Turing machines capture everything that can be computed.

Steps

1. Rules as data
2. The Church–Turing thesis
3. Accidentally universal
4. Programs are countable
5. A universal pattern
6. Faster, not stronger