AdvancedTheory of Computation (TOC) · Lesson 11 of 14 · Updated ·
Turing Machines Step by Step — Instantaneous Descriptions, Full Traces, Palindromes and Unary Addition
The Turing machines lesson introduced the model and showed two machines working. Exam questions usually go one step further: "Design a TM for … and show the moves on the input …". To answer them you need a precise way to write down where the machine is after every move. That is the instantaneous description. In this lesson we trace two machines move by move, and a Python simulator prints the same traces so you can check your hand work.
1. Instantaneous descriptions (IDs)
At any moment a Turing machine is fully described by three things: the tape contents, the state, and the head position. An instantaneous description writes them as one string:
left part, state, right part — the head is on the first symbol of the right part.
For example, 1 1 q₀ + 1 1 means: the tape holds 11+11, the machine is in state q₀, and the head is on the +.
One move is written with ⊢ ("yields"):
1 1 q₀ + 1 1 ⊢ 1 1 1 q₁ 1 1
Here the rule δ(q₀, +) = (q₁, 1, R) replaced + with 1, moved right and changed state. A whole run is a chain of IDs joined by ⊢, ending in an accepting or rejecting state (or going on forever).
2. A simulator that prints IDs
def run(delta, tape, start, accept, reject="rej", blank="_", max_steps=500, trace=True):
cells = dict(enumerate(tape))
head, state, steps = 0, start, 0
def show():
lo = min(min(cells, default=0), head)
hi = max(max(cells, default=0), head)
left = "".join(cells.get(i, blank) for i in range(lo, head)).lstrip(blank)
right = "".join(cells.get(i, blank) for i in range(head, hi + 1)).rstrip(blank) or blank
return f"{left} [{state}] {right}".strip()
if trace:
print(f"{steps:3} {show()}")
while state not in (accept, reject) and steps < max_steps:
sym = cells.get(head, blank)
if (state, sym) not in delta:
state = reject # no rule: the machine halts and rejects
break
state, write, move = delta[(state, sym)]
cells[head] = write
head += 1 if move == "R" else -1
steps += 1
if trace:
print(f"{steps:3} {show()}")
return state == accept, steps
# unary addition: 111+11 means 3 + 2
add = {("q0", "1"): ("q0", "1", "R"), ("q0", "+"): ("q1", "1", "R"),
("q1", "1"): ("q1", "1", "R"), ("q1", "_"): ("q2", "_", "L"),
("q2", "1"): ("acc", "_", "L")}
print("accepted, steps:", run(add, "111+11", "q0", "acc"))
0 [q0] 111+11
1 1 [q0] 11+11
2 11 [q0] 1+11
3 111 [q0] +11
4 1111 [q1] 11
5 11111 [q1] 1
6 111111 [q1] _
7 11111 [q2] 1
8 1111 [acc] 1
accepted, steps: (True, 8)
The state is shown in square brackets just before the symbol under the head, which is the usual exam notation.
3. Reading the unary adder
In unary, a number n is written as n ones: 3 is 111. To add, the machine joins the two blocks of ones and removes one extra 1:
| State | Reads | Writes | Moves | Next state | Meaning |
|---|---|---|---|---|---|
| q0 | 1 | 1 | R | q0 | skip the first number |
| q0 | + | 1 | R | q1 | turn the + into a 1 (now one 1 too many) |
| q1 | 1 | 1 | R | q1 | skip the second number |
| q1 | _ | _ | L | q2 | reached the end; step back |
| q2 | 1 | _ | L | acc | erase the last 1 and halt |
The trace has 8 moves for 3 + 2. In general it takes (m + n + 1) moves right plus 2 more: the work grows linearly with the input.
4. A palindrome checker
Language: palindromes over {a, b} — strings that read the same backwards (ε, a, abba, aba, …). No DFA can recognise this language, because it would have to remember the whole first half. A Turing machine can, by crossing off matching ends:
- In q0, read the first symbol. If it is blank, everything matched: accept. Otherwise remember it in the state (q1a for
a, q1b forb) and erase it. - Move right to the end of the remaining string.
- Step back onto the last symbol. If it matches the remembered one, erase it. If it is blank, the remembered symbol was the middle of an odd-length string: accept. If it is the other letter: reject.
- Move left back to the start and repeat.
def run(delta, tape, start, accept, reject="rej", blank="_", max_steps=500, trace=True):
cells = dict(enumerate(tape))
head, state, steps = 0, start, 0
def show():
lo = min(min(cells, default=0), head)
hi = max(max(cells, default=0), head)
left = "".join(cells.get(i, blank) for i in range(lo, head)).lstrip(blank)
right = "".join(cells.get(i, blank) for i in range(head, hi + 1)).rstrip(blank) or blank
return f"{left} [{state}] {right}".strip()
if trace:
print(f"{steps:3} {show()}")
while state not in (accept, reject) and steps < max_steps:
sym = cells.get(head, blank)
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 trace:
print(f"{steps:3} {show()}")
return state == accept, steps
pal = {("q0", "a"): ("q1a", "_", "R"), ("q0", "b"): ("q1b", "_", "R"), ("q0", "_"): ("acc", "_", "R"),
("q1a", "a"): ("q1a", "a", "R"), ("q1a", "b"): ("q1a", "b", "R"), ("q1a", "_"): ("q2a", "_", "L"),
("q1b", "a"): ("q1b", "a", "R"), ("q1b", "b"): ("q1b", "b", "R"), ("q1b", "_"): ("q2b", "_", "L"),
("q2a", "a"): ("q3", "_", "L"), ("q2a", "_"): ("acc", "_", "R"), ("q2a", "b"): ("rej", "b", "L"),
("q2b", "b"): ("q3", "_", "L"), ("q2b", "_"): ("acc", "_", "R"), ("q2b", "a"): ("rej", "a", "L"),
("q3", "a"): ("q3", "a", "L"), ("q3", "b"): ("q3", "b", "L"), ("q3", "_"): ("q0", "_", "R")}
print("abba ->", run(pal, "abba", "q0", "acc"))
print()
print("abb ->", run(pal, "abb", "q0", "acc"))
0 [q0] abba
1 [q1a] bba
2 b [q1a] ba
3 bb [q1a] a
4 bba [q1a] _
5 bb [q2a] a
6 b [q3] b
7 [q3] bb
8 [q3] _bb
9 [q0] bb
10 [q1b] b
11 b [q1b] _
12 [q2b] b
13 [q3] _
14 [q0] _
15 [acc] _
abba -> (True, 15)
0 [q0] abb
1 [q1a] bb
2 b [q1a] b
3 bb [q1a] _
4 b [q2a] b
5 [rej] bb
abb -> (False, 5)
Follow the abba trace line by line:
- Moves 1–5: erase the first
a, run right overbba, step back onto the lasta. - Move 6: it matches, so erase it. Moves 7–9: run left back to the blank, then step right.
- Moves 10–14: the same for the two
bs. - Move 15: q0 reads a blank — every symbol was matched — so the machine accepts.
For abb, the first symbol a is compared with the last symbol b, and the machine rejects at move 5.
5. Is it correct, and how fast is it?
A trace shows one run. To trust the machine, compare it with a plain Python definition on every short string, and record the number of moves:
from itertools import product
def run(delta, tape, start, accept, reject="rej", blank="_", 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, blank)
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
pal = {("q0", "a"): ("q1a", "_", "R"), ("q0", "b"): ("q1b", "_", "R"), ("q0", "_"): ("acc", "_", "R"),
("q1a", "a"): ("q1a", "a", "R"), ("q1a", "b"): ("q1a", "b", "R"), ("q1a", "_"): ("q2a", "_", "L"),
("q1b", "a"): ("q1b", "a", "R"), ("q1b", "b"): ("q1b", "b", "R"), ("q1b", "_"): ("q2b", "_", "L"),
("q2a", "a"): ("q3", "_", "L"), ("q2a", "_"): ("acc", "_", "R"), ("q2a", "b"): ("rej", "b", "L"),
("q2b", "b"): ("q3", "_", "L"), ("q2b", "_"): ("acc", "_", "R"), ("q2b", "a"): ("rej", "a", "L"),
("q3", "a"): ("q3", "a", "L"), ("q3", "b"): ("q3", "b", "L"), ("q3", "_"): ("q0", "_", "R")}
words = ["".join(t) for n in range(11) for t in product("ab", repeat=n)]
print("agrees with w == reversed(w) on", len(words), "strings:",
all(run(pal, w, "q0", "acc")[0] == (w == w[::-1]) for w in words))
for n in [2, 4, 8, 16, 32]:
print(f"length {n:2}: {run(pal, 'a' * n, 'q0', 'acc')[1]:4} moves")
agrees with w == reversed(w) on 2047 strings: True
length 2: 6 moves
length 4: 15 moves
length 8: 45 moves
length 16: 153 moves
length 32: 561 moves
Doubling the length roughly quadruples the moves: the machine walks across the whole remaining string for each pair of symbols, so it takes about n²/2 moves — O(n²). A two-tape Turing machine could copy the input and compare it in O(n) moves. That is the "multi-tape machines can be faster but not more powerful" fact from the earlier lesson, seen in real numbers.
6. How to answer a "show the moves" exam question
- Write the transition table first, with one row per (state, symbol) pair you use.
- Write the starting ID: the start state before the first symbol, like
[q0] abba. - For each move, look up the rule for (current state, symbol under the head), then write the new ID: replace the symbol, move the state marker one place left or right.
- Stop at an accept or reject state, or when no rule applies (the machine halts and rejects).
- Check one property at the end: for the adder, count the ones; for the palindrome machine, check the tape is blank.
| Common slip | Correct version |
|---|---|
| moving the head but not changing the symbol | apply write, then move in the same step |
| state written after the symbol it reads | the state goes before the scanned symbol |
| forgetting blanks at the ends | the tape is infinite; off the input the head reads _ |
| inventing a rule mid-trace | if no rule exists, the machine halts and rejects |
Common mistakes
- Mixing up notation: in an ID the head is on the symbol right after the state.
- Moving before writing. Each move writes first, then moves one cell, then changes state.
- Treating a missing transition as "stay still". With no rule the machine halts (and in our convention rejects).
- Forgetting the odd-length case in the palindrome machine (q2a or q2b reading a blank must accept).
- Assuming a TM is efficient. These machines define what is computable; their step counts are often quadratic or worse.
Quick recap
- An ID is left part, state, right part; the head reads the first symbol after the state. One move is written ⊢.
- Each move: read the symbol, write a symbol, move L or R, change state.
- Unary adder: turn + into 1, walk to the end, erase one 1 — 8 moves for 3 + 2.
- Palindrome TM: erase matching first and last symbols until nothing is left; it needs about n²/2 moves.
- Check a TM against a plain definition on all short strings, just as with DFAs.