Turing Machine

The Turing machine model

A Turing machine consists of three parts:

1. An infinite tape divided into cells, each holding one symbol from a finite alphabet (or blank).
2. A read/write head positioned over one cell at a time.
3. A finite-state control unit that decides what to do based on the current state and the symbol under the head.

On each step, the machine:

• Reads the symbol under the head.
• Writes a (possibly different) symbol.
• Moves the head left or right one cell.
• Transitions to a new state (or halts).

That's it. No arithmetic, no random access, no parallelism. The simplicity is the point — anything you can compute, you can compute with this model.

Example — incrementing a binary number

Tape contents 1011 (binary 11). Goal — produce 1100 (binary 12). The TM scans right to find the end, then walks back flipping 1s to 0s until it finds a 0 (or empty cell), flips it to 1, halts.

State table (start at state q0, head at leftmost):
                Read    Write    Move    Next state
  q0 (scan right)  0       0       R       q0
                   1       1       R       q0
                   blank   blank   L       q1
  q1 (carry)       0       1       —       halt
                   1       0       L       q1
                   blank   1       —       halt

Three states encode binary increment. The same model with more states can compute factorials, sort arrays, run a compiler — anything any computer can do.

The universal Turing machine

Turing's deepest insight (1936) — there exists a single Turing machine that can simulate any other Turing machine, given a description of that machine on its input tape. This is the universal Turing machine. It's the theoretical ancestor of every general-purpose computer — a single piece of hardware (the universal TM, or your CPU) can run any program (the description of any TM, or any binary).

The construction — encode any TM as a string (its state table, alphabet, transitions). The universal TM reads this encoding from its input, then simulates the encoded TM step by step on a separate region of tape. The result is the same as running the encoded TM directly.

This insight justifies modern computing — your laptop doesn't have separate hardware for a browser, a text editor, and a compiler. It has one CPU running different programs, each treated as data by the universal hardware.

The halting problem

Given a TM M and input x, can we always determine whether M(x) eventually halts? Turing proved no — there's no algorithm that decides halting for all (M, x) pairs.

The proof is a beautiful contradiction:

1. Suppose halts(M, x) exists and returns true iff M halts on x.
2. Define diagonal(M) — runs halts(M, M); if it says yes, loop forever; otherwise halt.
3. Ask — does diagonal(diagonal) halt?
   • If halts(diagonal, diagonal) says yes (diagonal halts on itself), then by step 2, diagonal loops forever — contradiction.
   • If it says no, then by step 2, diagonal halts — contradiction.
4. Either case contradicts. Therefore, halts can't exist.

This is one of the most important results in computer science. It implies that many useful properties of programs are undecidable — equivalence, termination, correctness, freedom from crashes. Practical tools work around this by restricting language expressiveness or using heuristics that miss some cases.

Where TMs sit in the hierarchy

Model	Power	Recognizes	Memory
Finite state machine	Weakest	Regular languages	Constant (state only)
Push-down automaton	Adds a stack	Context-free languages	Stack of unbounded size
Linear bounded automaton	TM with bounded tape	Context-sensitive languages	Linear in input
Turing machine	Most powerful	Recursively enumerable	Infinite tape

Each level above the previous adds expressive power. Real computers are practically TMs (finite-memory limit aside) but you can study smaller models for specific tasks — FSMs for tokenization, PDAs for parsing context-free grammars.

Surprising Turing-complete systems

• Conway's Game of Life. A 2D cellular automaton with simple rules — proven Turing-complete by constructing logic gates and memory cells out of glider patterns.
• Magic: the Gathering. The interaction of certain card abilities can encode arbitrary computation. Proven Turing-complete in 2019.
• x86 mov instruction alone. Stephen Dolan showed that just the mov instruction (no arithmetic, no jumps) is Turing-complete. The "movfuscator" compiler exploits this.
• Excel formulas (with iteration enabled). Spreadsheet circular references plus iteration mode allow general-purpose computation.
• HTML + CSS3. Rule 110 (a Turing-complete cellular automaton) is implementable in pure HTML/CSS using checkbox states and selectors.
• SQL with recursive CTEs. Even pure SQL — without procedures, triggers, or user-defined functions — is Turing-complete.
• Conway's "FRACTRAN." A pure list-of-fractions language with one operation (multiply input by the first applicable fraction) is Turing-complete.

JavaScript: simulating a tiny Turing machine

class TuringMachine {
  constructor(transitions, startState, blank = '_') {
    this.transitions = transitions;  // {[state, symbol]: [newSymbol, move, newState]}
    this.tape = new Map();           // sparse tape — index → symbol
    this.head = 0;
    this.state = startState;
    this.blank = blank;
    this.halted = false;
  }

  read()       { return this.tape.get(this.head) ?? this.blank; }
  write(s)     { this.tape.set(this.head, s); }
  move(dir)    { this.head += (dir === 'R' ? 1 : -1); }

  step() {
    const symbol = this.read();
    const key = `${this.state},${symbol}`;
    const transition = this.transitions[key];
    if (!transition) { this.halted = true; return; }
    const [newSymbol, move, newState] = transition;
    this.write(newSymbol);
    this.move(move);
    this.state = newState;
  }

  run(maxSteps = 10000) {
    for (let i = 0; i < maxSteps && !this.halted; i++) this.step();
    return this.tapeAsString();
  }

  tapeAsString() {
    if (this.tape.size === 0) return this.blank;
    const indices = [...this.tape.keys()].sort((a, b) => a - b);
    const min = indices[0], max = indices[indices.length - 1];
    let result = '';
    for (let i = min; i <= max; i++) result += this.read.call({ tape: this.tape, head: i, blank: this.blank });
    return result;
  }
}

// Increment a binary number
const tm = new TuringMachine({
  'q0,0': ['0', 'R', 'q0'],
  'q0,1': ['1', 'R', 'q0'],
  'q0,_': ['_', 'L', 'q1'],
  'q1,0': ['1', 'R', 'halt'],
  'q1,1': ['0', 'L', 'q1'],
  'q1,_': ['1', 'R', 'halt'],
}, 'q0');

// Initialize tape with '1011'
'1011'.split('').forEach((c, i) => tm.tape.set(i, c));
tm.run();
console.log(tm.tapeAsString());  // '1100' — 11 + 1 = 12 in binary

Why Turing machines matter today

• Defines what's computable. Anything computable in any language is computable on a Turing machine. The boundary between solvable and unsolvable problems is the boundary between "Turing-computable" and "not."
• Establishes undecidability of many practical problems. Halting, equivalence, termination, "will this program produce output X" — all undecidable. Static analyzers and type checkers exist within this constraint.
• Foundation of complexity theory. P, NP, PSPACE, EXPTIME — all defined relative to Turing machines (or non-deterministic TMs for NP). The P vs NP question is "are these two classes equal?"
• Reference model for new computational paradigms. Quantum computing, DNA computing, neural computing — each is judged by what TMs they can simulate and how efficiently.
• Practical relevance via reductions. Showing a problem is "as hard as" the halting problem (undecidable) or "as hard as" 3-SAT (NP-complete) tells you the tractability boundary you're up against.

Common misconceptions

• "Turing machines are just one model among many." Yes, but every other model we've found computable is equivalent to a TM. Turing-completeness is a robust notion — independent of the specific model.
• "Real computers are Turing-complete." Almost — real computers have finite memory, so they're technically less powerful (they can't recognize languages requiring unbounded memory). For practical purposes, we treat them as TM-equivalent.
• "Turing-complete = able to do anything." Turing-complete systems can express any computation. They can't break the halting problem, exceed cryptographic security bounds, or violate the laws of physics. "Computable" is a precisely defined formal notion.
• "Turing machines are slow because of one-cell-at-a-time." They're slow per step but the total complexity (steps to compute X) is the same as on real machines, modulo polynomial factors. Theoretical complexity classes ignore polynomial differences.
• "The halting problem only applies to academic problems." No — many practical questions reduce to halting. "Will this regex always match in linear time?" "Does this smart contract always terminate?" "Are these two compiler optimizations equivalent?" — all undecidable in general.
• "Quantum computers exceed Turing machines." No — quantum computers can be simulated by TMs (with exponential slowdown for some problems). They might be exponentially faster on specific problems, but they don't compute anything a TM can't compute, just sometimes faster.