The universal machine U

Parent: examples

One fixed machine that runs every machine. U(⟨M⟩, x) keeps three regions on its tape:

• M's work tape,
• M's current state,
• the encoded transition table ⟨M⟩.

Each step, U reads M's scanned symbol, looks up the matching rule inside ⟨M⟩, and applies it (write / move / change M's state). The crucial shift: here δ is not fixed hardware — it's data on the tape.

This is the seed of two huge ideas:

• data = program (a machine's description is just input) → the stored-program computer (von Neumann);
• a machine can take its own description as input → self-reference, which makes the halting-problem statable and the busy-beaver / diagonal arguments possible.

The simple examples show a fixed δ as a table; U shows that same table living on the tape, so one piece of hardware is Turing-complete for all tables at once.