In 1936, Alan Turing proposed a precise mathematical model of what it means to "compute" at all: the Turing machine. It consists of an infinite tape divided into cells, a head that reads and writes one cell at a time and can move left or right, and a finite set of states governed by a transition function: given the current state and the symbol under the head, it specifies what symbol to write, which direction to move, and which state to enter next.

Despite its austerity, the Turing machine can compute anything any modern computer can compute — no more, no less. This is the Church–Turing thesis: any function that is "effectively computable" by some intuitive algorithmic process can be computed by a Turing machine. Every real programming language, however different it looks, is provably equivalent in power to this simple tape-and-head device.

A problem is decidable if some Turing machine, given any input, always halts and correctly answers yes or no. A problem is undecidable if no such machine can exist for it — not because we haven't found a clever enough algorithm yet, but because a proof shows none ever can.

The most famous undecidable problem is the halting problem: given a program and an input, will it eventually halt, or run forever? Turing proved no algorithm can decide this in general, using a proof by contradiction (a diagonal argument): suppose a program HALTS(P, x) existed that always correctly answers whether program P halts on input x. Build a new program PARADOX(P) that calls HALTS(P, P) and does the opposite — loops forever if P halts on itself, halts if it doesn't. Now ask: does PARADOX(PARADOX) halt? Either answer contradicts what HALTS just claimed. So HALTS cannot exist.

This isn't a curiosity — it sets a hard ceiling on computation itself. No antivirus can perfectly detect "will this program misbehave," no compiler can perfectly detect "will this loop terminate," for the same fundamental reason: it would have to solve the halting problem.

We implement a tiny Turing machine as a general simulator, then run it on a program that increments a binary number by one — a real, if minimal, example of a head moving across a tape following rules.

# A Turing machine: states, a transition table, and a tape (dict: position -> symbol).
# Transition table: (state, symbol) -> (new_symbol, move, new_state)   move in {-1, 0, +1}

def run_turing_machine(transitions, start_state, halt_states, tape, head=0, max_steps=10000):
    state = start_state
    steps = 0
    while state not in halt_states and steps < max_steps:
        symbol = tape.get(head, "_")                 # "_" = blank cell
        key = (state, symbol)
        if key not in transitions:
            raise ValueError("no rule for state=%s symbol=%s (machine stuck)" % key)
        new_symbol, move, new_state = transitions[key]
        tape[head] = new_symbol
        head += move
        state = new_state
        steps += 1
    return tape, head, state, steps

# Binary increment: scan right to the end of the number, then add 1 with carries
# moving left, exactly like adding 1 by hand.
transitions = {
    ("scan_right", "0"): ("0", +1, "scan_right"),
    ("scan_right", "1"): ("1", +1, "scan_right"),
    ("scan_right", "_"): ("_", -1, "add_one"),        # found the end, start carrying
    ("add_one", "0"):    ("1",  0, "done"),           # 0 -> 1, no carry, finished
    ("add_one", "1"):    ("0", -1, "add_one"),        # 1 -> 0, carry left
    ("add_one", "_"):    ("1",  0, "done"),           # ran off the left: new leading 1
}

# Tape holds the binary number 101 (=5); increment should give 110 (=6)
tape = {0: "1", 1: "0", 2: "1"}
final_tape, head, state, steps = run_turing_machine(transitions, "scan_right", {"done"}, tape)
result = "".join(final_tape.get(i, "_") for i in range(min(final_tape), max(final_tape) + 1))
print(result.strip("_"))     # -> "110"  (5 + 1 = 6, computed one cell at a time)

Notice how primitive each step is — read a cell, write a cell, move one square, change state — and yet chaining thousands of such steps performs real arithmetic. Computation is not one grand leap of intelligence; it's an enormous number of tiny, mechanical, well-defined steps.