# Turing Machines Step by Step — Instantaneous Descriptions, Full Traces, Palindromes and Unary Addition

Source: https://skills101.in/learn/theory-of-computation/toc-turing-machine-step-by-step-traces — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-21.

The [Turing machines lesson](https://skills101.in/learn/theory-of-computation/turing-machines) 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

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

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

![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](https://skills101.in/learn-img/theory-of-computation/tm-trace-add.svg)

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](https://skills101.in/learn-img/theory-of-computation/tm-palindrome-table.svg)

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

```text
  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 `b`s.
- 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:

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

```text
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 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.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-turing-machine-step-by-step-traces