Skills101

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:

StateReadsWritesMovesNext stateMeaning
q011Rq0skip the first number
q0+1Rq1turn the + into a 1 (now one 1 too many)
q111Rq1skip the second number
q1__Lq2reached the end; step back
q21_Laccerase the last 1 and halt

Tape snapshots of the unary adder on 111+11, computed by the simulator: the head walks right over the first number, the plus becomes a 1, it walks to the blank at the end, steps back and erases the last 1, leaving 11111, which is 5

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:

  1. In q0, read the first symbol. If it is blank, everything matched: accept. Otherwise remember it in the state (q1a for a, q1b for b) and erase it.
  2. Move right to the end of the remaining string.
  3. 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.
  4. Move left back to the start and repeat.

Transition table of the palindrome Turing machine: q0 erases the first symbol and moves to q1a or q1b; q1a and q1b run right to the blank; q2a and q2b check the last symbol, erase it on a match, accept on blank and reject on a mismatch; q3 runs left back to the start

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 over bba, step back onto the last a.
  • 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

  1. Write the transition table first, with one row per (state, symbol) pair you use.
  2. Write the starting ID: the start state before the first symbol, like [q0] abba.
  3. 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.
  4. Stop at an accept or reject state, or when no rule applies (the machine halts and rejects).
  5. Check one property at the end: for the adder, count the ones; for the palindrome machine, check the tape is blank.
Common slipCorrect version
moving the head but not changing the symbolapply write, then move in the same step
state written after the symbol it readsthe state goes before the scanned symbol
forgetting blanks at the endsthe tape is infinite; off the input the head reads _
inventing a rule mid-traceif 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.

Practice what you learned

📝 Quiz: Turing Machine Traces5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →