Turing Machine

Alan Turing’s machine (1936)

Before electronic computers existed, Alan Turing asked: what does it mean to compute? His answer was an imaginary machine so simple that it obviously can be built, yet able to carry out any algorithm.

A Turing machine has:

1. an infinite tape divided into cells, each holding one symbol (or a blank ␣),
2. a head that reads and writes one cell and moves left or right,
3. a finite set of states, including halting states,
4. a rule table: (current state, symbol read) → (symbol to write, move L/R, next state).

That’s all. In the 3D model, the diamond is the head (with its current state above it), and the code panel lists the rule table — the highlighted line is the rule being applied.

Example 1: binary +1

Rules:

Walk to the end, then add 1 exactly as you would on paper: 1 + 1 = 0 carry 1, until a 0 or blank absorbs the carry. 1011 (11) → 1100 (12).

Example 2: unary addition

Numbers are written in unary: 3 = 111. To compute 111+11, replace the + with a 1 and erase one 1 from the end → 11111 (5).

Example 3: is it a palindrome?

Erase the first symbol and remember it in the state (have0 / have1), run to the end, check that the last symbol matches, erase it, run back to the start — and repeat. If everything matched, accept. This takes O(n²) steps because the head travels back and forth.

Why Turing machines matter

• Church–Turing thesis: anything computable by an algorithm can be computed by a Turing machine. Your laptop, a phone and a supercomputer are all “just” fast Turing machines (with finite tape).
• Universal Turing machine: one Turing machine can simulate any other, given its rule table on the tape — the idea behind stored-program computers.
• Limits of computation: some problems can’t be solved by any algorithm. The famous halting problem — “will this program ever stop?” — is undecidable.

The halting problem in one paragraph

Suppose a program halts(P, x) could always answer correctly. Build trouble(P): if halts(P, P) says yes, loop forever; otherwise stop. Now ask: does trouble(trouble) halt? Either answer contradicts itself — so halts cannot exist.

Code: a tiny Turing machine simulator

def run_tm(rules, tape, state, halt, max_steps=1000):
    tape = dict(enumerate(tape))           # sparse "infinite" tape
    head = 0
    for _ in range(max_steps):
        if state in halt:
            break
        sym = tape.get(head, "_")
        write, move, state = rules[(state, sym)]
        tape[head] = write
        head += 1 if move == "R" else -1
    cells = [tape[i] for i in range(min(tape), max(tape) + 1)]
    return "".join(cells).strip("_"), state

increment = {
    ("right", "0"): ("0", "R", "right"), ("right", "1"): ("1", "R", "right"),
    ("right", "_"): ("_", "L", "carry"),
    ("carry", "1"): ("0", "L", "carry"), ("carry", "0"): ("1", "L", "done"),
    ("carry", "_"): ("1", "L", "done"),
}
print(run_tm(increment, "1011", "right", {"done"}))   # ('1100', 'done')

Common mistakes

• Forgetting a rule for some (state, symbol) pair — the machine then halts unexpectedly.
• Moving the head off the written part and forgetting that the tape is full of blanks there.
• Thinking a Turing machine is a real device — it’s a mathematical model (although people have built physical ones for fun).