Turing Machines — The Model of Every Computer, Designing TMs, Variants and the Church–Turing Thesis

In 1936, before electronic computers existed, Alan Turing asked: what does it mean to compute? His answer — a simple imaginary machine with a tape — turned out to capture everything any computer can do. Your laptop, a supercomputer and a quantum computer can compute exactly the same set of functions as a Turing machine (just at different speeds).

1. The machine

• An infinite tape of cells, each holding a symbol (blank _ by default).
• A head that reads/writes one cell and moves left or right.
• A finite set of states, including accept and reject states.
• A transition function: δ(state, symbol) = (new state, symbol to write, move L/R).

Compared with earlier machines:

2. A Turing machine simulator

def run_tm(delta, tape, start="q0", accept="acc", reject="rej", max_steps=10_000, show=False):
    cells = dict(enumerate(tape))
    head, state, steps = 0, start, 0
    while state not in (accept, reject) and steps < max_steps:
        sym = cells.get(head, "_")
        if (state, sym) not in delta:
            state = reject
            break
        state, write, move = delta[(state, sym)]
        cells[head] = write
        head += 1 if move == "R" else -1
        steps += 1
        if show:
            lo, hi = min(cells), max(cells)
            t = "".join(cells.get(i, "_") for i in range(lo, hi + 1))
            print(f"  {state:4} {t}  head@{head - lo}")
    lo, hi = min(cells), max(cells)
    result = "".join(cells.get(i, "_") for i in range(lo, hi + 1)).strip("_")
    return state == accept, result, steps

# Binary increment: go to the right end, then add 1 with carry
inc = {("q0", "0"): ("q0", "0", "R"), ("q0", "1"): ("q0", "1", "R"), ("q0", "_"): ("q1", "_", "L"),
       ("q1", "1"): ("q1", "0", "L"),                     # 1 + carry = 0, carry on
       ("q1", "0"): ("acc", "1", "L"),                    # 0 + carry = 1, done
       ("q1", "_"): ("acc", "1", "L")}                    # ran off the left: new leading 1

for n in [5, 7, 11, 0]:
    ok, out, steps = run_tm(inc, bin(n)[2:])
    print(f"{bin(n)[2:]:>5} + 1 = {out:>5}  ({int(out, 2)}) in {steps} steps")

  101 + 1 =   110  (6) in 6 steps
  111 + 1 =  1000  (8) in 8 steps
 1011 + 1 =  1100  (12) in 8 steps
    0 + 1 =     1  (1) in 3 steps

3. A TM for aⁿbⁿcⁿ (not context-free!)

Strategy — "cross off one of each per pass":

1. Replace the first a with X, move right to the first b, replace with Y, move right to the first c, replace with Z.
2. Go back to the left and repeat.
3. When no a is left, check that only Ys and Zs remain.

def run_tm(delta, tape, start="q0", accept="acc", reject="rej", max_steps=10_000):
    cells = dict(enumerate(tape)); head, state, steps = 0, start, 0
    while state not in (accept, reject) and steps < max_steps:
        sym = cells.get(head, "_")
        if (state, sym) not in delta:
            return False, steps
        state, write, move = delta[(state, sym)]
        cells[head] = write; head += 1 if move == "R" else -1; steps += 1
    return state == accept, steps

abc = {
    ("q0", "a"): ("q1", "X", "R"), ("q0", "Y"): ("q4", "Y", "R"), ("q0", "_"): ("acc", "_", "R"),
    ("q1", "a"): ("q1", "a", "R"), ("q1", "Y"): ("q1", "Y", "R"), ("q1", "b"): ("q2", "Y", "R"),
    ("q2", "b"): ("q2", "b", "R"), ("q2", "Z"): ("q2", "Z", "R"), ("q2", "c"): ("q3", "Z", "L"),
    ("q3", "a"): ("q3", "a", "L"), ("q3", "b"): ("q3", "b", "L"), ("q3", "Y"): ("q3", "Y", "L"),
    ("q3", "Z"): ("q3", "Z", "L"), ("q3", "X"): ("q0", "X", "R"),
    ("q4", "Y"): ("q4", "Y", "R"), ("q4", "Z"): ("q4", "Z", "R"), ("q4", "_"): ("acc", "_", "R"),
}
for w in ["abc", "aabbcc", "aaabbbccc", "aabbc", "abcabc", "acb", ""]:
    ok, steps = run_tm(abc, w)
    print(f"{w or 'ε':10} {'ACCEPT' if ok else 'reject':7} ({steps} steps)")

from itertools import product
expected = lambda w: (n := len(w) // 3) * 3 == len(w) and w == "a" * n + "b" * n + "c" * n
agree = all(run_tm(abc, "".join(t))[0] == expected("".join(t)) for k in range(10) for t in product("abc", repeat=k))
print("agrees with a^n b^n c^n on all strings up to length 9:", agree)

abc        ACCEPT  (8 steps)
aabbcc     ACCEPT  (23 steps)
aaabbbccc  ACCEPT  (46 steps)
aabbc      reject  (13 steps)
abcabc     reject  (7 steps)
acb        reject  (1 steps)
ε          ACCEPT  (1 steps)
agrees with a^n b^n c^n on all strings up to length 9: True

The step counts grow roughly with n² — TMs are simple, not fast. Their purpose is to define what is computable, not to be efficient.

4. Variants don't add power

All of these recognise exactly the same languages as the basic TM (they can simulate each other):

5. The universal Turing machine

A universal TM U takes as input the description of any TM M plus an input w, and simulates M on w. That is the stored-program computer: one machine that runs any program given as data — the same idea as the von Neumann architecture (COA track) and as an interpreter like Python itself.

6. The Church–Turing thesis

Every function that can be computed by any effective procedure (any algorithm) can be computed by a Turing machine.

It's a thesis, not a theorem — "algorithm" is an informal idea — but every model of computation ever proposed (lambda calculus, recursive functions, register machines, modern programming languages) has turned out to be equivalent. A language or system that can simulate a TM is called Turing-complete — Python, Java, C, JavaScript, SQL with recursive queries, and even spreadsheets and Minecraft redstone are.

7. Decidable vs recognisable

• A TM decides L if it halts on every input with the right answer → L is decidable (recursive).
• A TM recognises L if it accepts exactly the strings in L, but may loop forever on strings not in L → L is recognisable (recursively enumerable).

Some languages are recognisable but not decidable — and some aren't even recognisable. That's the final lesson.

Common mistakes

• Thinking a TM is a physical machine design — it's a mathematical model.
• Assuming nondeterministic TMs recognise more languages (they don't; they may be faster).
• Forgetting a TM can loop forever (that's why "decides" and "recognises" differ).
• Treating the Church–Turing thesis as a proven theorem.

Quick recap

• TM = infinite tape + head (read/write, move L/R) + finite states; δ(q, s) = (q′, s′, L/R).
• TMs can do what DFAs/PDAs can't, e.g. aⁿbⁿcⁿ, arithmetic, any algorithm.
• Variants (multi-tape, nondeterministic) have the same power.
• Universal TM = stored-program computer; Church–Turing thesis: TM = "algorithm".
• Decidable (always halts) vs recognisable (may loop on "no" instances).