A UNIVERSAL TURING MACHINE U TAKES AS INPUT A DESCRIPTION OF ANOTHER TURING MACHINE M TOGETHER WITH AN INPUT w, AND SIMULATES M ON w. U( ⟨M, w⟩ ) behaves exactly as M(w) · If M accepts w, U accepts. · If M rejects w, U rejects. · IF M LOOPS ON w, U LOOPS. THE THIRD LINE IS NOT A DEFECT. U cannot do better than the machine it simulates, and the later topics show that no machine could. ── THE PREREQUISITE: ENCODING A MACHINE AS A STRING ──────── U's input is a string, so M must be written as one. A standard binary encoding: · state qᵢ encoded as 0ⁱ · tape symbol Xⱼ encoded as 0ʲ · direction L = D₁, R = D₂ encoded as 0ᵏ · a transition δ(qᵢ, Xⱼ) = (qₖ, Xₗ, Dₘ) encoded as 0ⁱ 1 0ʲ 1 0ᵏ 1 0ˡ 1 0ᵐ · transitions separated by 11 A WORKED ENCODING. Take a machine with two transitions: δ(q₁, X₁) = (q₂, X₂, R) → 0 1 0 1 00 1 00 1 00 δ(q₂, X₂) = (q₃, X₁, L) → 00 1 00 1 000 1 0 1 0 Concatenating with the 11 separator gives 010100100100 11 0010010001010 A 27-BIT STRING THAT COMPLETELY DESCRIBES THE MACHINE. THREE CONSEQUENCES FOLLOW IMMEDIATELY, and they carry the whole of the rest of the section: 1. EVERY TURING MACHINE IS A FINITE BINARY STRING. 2. THEREFORE TURING MACHINES ARE **COUNTABLE** — they can be listed M₁, M₂, M₃, … by reading their encodings as binary numbers. Strings that are not valid encodings are taken to denote a trivial machine that halts immediately, WHICH MAKES THE ENUMERATION TOTAL: every index i denotes some machine Mᵢ. 3. A MACHINE CAN BE GIVEN ANOTHER MACHINE — OR ITSELF — AS INPUT. THE THIRD IS THE ONE THAT LEADS TO THE HALTING PROBLEM. ── HOW U WORKS ───────────────────────────────────────────── A convenient construction uses THREE TAPES: TAPE 1 — the ENCODING of M, ⟨M⟩, never altered. This is the "program". TAPE 2 — a copy of M's tape, holding w initially and updated as the simulation proceeds. This is the "data". TAPE 3 — M's CURRENT STATE, held as 0ⁱ. This is the "program counter". THE SIMULATION LOOP: 1. Read the symbol under the head on tape 2. 2. Read the current state from tape 3. 3. SCAN TAPE 1 for a transition matching that (state, symbol) pair. 4. If none is found, HALT as M would. 5. Otherwise, WRITE the new symbol on tape 2, MOVE tape 2's head, and UPDATE tape 3 with the new state. 6. Repeat. THE COST: each simulated step requires scanning the encoding of M, so U runs with a SLOWDOWN proportional to |⟨M⟩| — A CONSTANT FACTOR for any fixed M, since the machine's description does not grow with the input. (Converting the three-tape U to a single tape adds the usual quadratic factor of the multi-tape topic.) THE STRUCTURAL POINT IS WORTH NAMING: TAPE 1 HOLDS THE PROGRAM, TAPE 2 THE DATA, TAPE 3 THE PROGRAM COUNTER. THAT IS THE ARCHITECTURE OF EVERY COMPUTER EVER BUILT, described a decade before one existed.

── THE STORED-PROGRAM PRINCIPLE ──────────────────────────── A PROGRAM IS JUST DATA. The encoding ⟨M⟩ is a string like any other. It can be stored on a tape, read, copied, modified, or passed as input. THIS IS THE MOST CONSEQUENTIAL IDEA IN COMPUTING, and everything below is a direct descendant: · GENERAL-PURPOSE COMPUTERS — one machine, many programs · OPERATING SYSTEMS — programs that run other programs · COMPILERS AND INTERPRETERS — programs that read programs as input · VIRTUAL MACHINES AND EMULATORS — the JVM is a universal machine for its bytecode · SELF-MODIFYING CODE, and its descendants JIT compilation and dynamic optimisation · VIRUSES AND MALWARE — programs treating other programs as data to be altered · METAPROGRAMMING, reflection, and code generation THE VON NEUMANN ARCHITECTURE — instructions and data sharing one memory — IS THE ENGINEERING FORM OF THIS IDEA, and it is why a buffer overflow can execute injected data as code: THE HARDWARE CANNOT TELL THEM APART, BECAUSE IN PRINCIPLE THERE IS NO DIFFERENCE. ── THE UNIVERSAL LANGUAGE ────────────────────────────────── L_u = { ⟨M, w⟩ : M accepts w } L_u IS RECURSIVELY ENUMERABLE — U recognises it, by simulation. L_u IS **NOT** RECURSIVE — this is the halting problem, and it is the standard example of the strict containment RECURSIVE ⊊ RE established earlier. NOTE THE STRUCTURE OF THAT PAIR OF FACTS: THE UNIVERSAL MACHINE PROVES THE POSITIVE HALF, AND THE DIAGONAL ARGUMENT BELOW PROVES THE NEGATIVE HALF. Together they place L_u exactly. ── WHY UNIVERSALITY MAKES UNDECIDABILITY POSSIBLE ────────── THE ENCODING IS WHAT ENABLES SELF-REFERENCE, and self- reference is what produces the paradox. Because ⟨M⟩ is a string, one may ask what M does when RUN ON ITS OWN DESCRIPTION — M(⟨M⟩). That question is meaningful only because of the encoding. THE DIAGONAL ARGUMENT, in outline: Suppose a machine H decides halting: H(⟨M⟩, w) says whether M halts on w. Build D as follows: "On input ⟨M⟩: run H on (⟨M⟩, ⟨M⟩) if H says M HALTS on ⟨M⟩, then LOOP FOREVER if H says M LOOPS on ⟨M⟩, then HALT" NOW ASK WHAT D DOES ON INPUT ⟨D⟩: if D halts on ⟨D⟩, then by construction D loops — CONTRADICTION if D loops on ⟨D⟩, then by construction D halts — CONTRADICTION Therefore H cannot exist. ∎ THE ARGUMENT IS EXACTLY CANTOR'S DIAGONAL ARGUMENT AND EXACTLY THE LIAR PARADOX, in computational dress. D is a machine that does the opposite of whatever it is predicted to do, and its existence depends entirely on being able to feed a machine its own description. ── SMALL UNIVERSAL MACHINES ──────────────────────────────── A recreational but instructive line of research: how small can a universal machine be? Turing's original was large. Minsky found a 7-state, 4-symbol universal machine in 1962. The record now stands at a 2-state, 3-symbol machine, whose universality was proved in 2007 — though the proof's use of an infinite non-repeating initial tape is disputed. THE LESSON IS THE ONE FROM THE TURING-COMPLETENESS TOPIC: UNIVERSALITY IS ACHIEVED WITH ASTONISHINGLY LITTLE MACHINERY. A system needs only a means of branching and unbounded storage, which is why Turing completeness turns up unintentionally in template systems, spreadsheet formulas and card games. ── THE SUMMARY ───────────────────────────────────────────── ONE MACHINE CAN DO EVERYTHING ANY MACHINE CAN DO. THE POSITIVE READING is the computer industry: build one general machine and program it. THE NEGATIVE READING is undecidability: because a machine can reason about machines, it can be asked about itself — and some such questions have no consistent answer. BOTH FOLLOW FROM THE SAME FACT, that a program is a string. THE MOST POWERFUL IDEA IN COMPUTING AND ITS DEEPEST LIMITATION ARE THE SAME IDEA.