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

Source: https://skills101.in/learn/theory-of-computation/turing-machines — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

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).

![Turing machine: an infinite tape of cells holding symbols, a read-write head positioned over one cell, and a finite control that, based on the current state and the symbol under the head, writes a symbol, moves left or right and changes state](https://skills101.in/learn-img/theory-of-computation/turing-machine.svg)

Compared with earlier machines:

| Machine | Memory | Can move back? | Can write? |
|---|---|---|---|
| DFA | none | no | no |
| PDA | stack (top only) | — | push/pop |
| **TM** | unbounded tape | **yes** | **yes** |

## 2. A Turing machine simulator

```python
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")
```

```text
  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 `Y`s and `Z`s remain.

```python
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)
```

```text
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):

| Variant | Note |
|---|---|
| multi-tape TM | can be faster (e.g. quadratic speed-up) but not more powerful |
| two-way infinite tape | same |
| nondeterministic TM | same languages (simulate by trying all branches — possibly exponentially slower) |
| TM with "stay" moves | same |
| RAM machines, real CPUs | same (given unlimited memory) |

## 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).


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/turing-machines