Turing machines — formal definition, computation, configurations: Worked examples

The scenario matrix

Every worked example below is tagged with the cell it covers. Read this table first, then watch each cell get filled.

Cell	The scenario class	Covered by
C1	Normal accept — head walks right, halts on a blank	Example A
C2	Normal reject — machine reaches $q_{reject}$	Example B
C3	Empty input $w = ε$ (head reads a blank immediately)	Example C
C4	Left-edge move ( $L$ at cell 0) — head must stay put, not crash	Example D
C5	Overwrite under the head, then move (tape actually changes)	Example D
C6	Looping forever (never halts) — no accept, no reject	Example E
C7	$δ$ undefined / partial transition (implicit reject)	Example F
C8	Word problem — a decidable language, checked end-to-end	Example G
C9	Exam twist — recognizer that loops on a non-member	Example H

Example A — Cell C1 (normal accept)

Figure — Turing machines — formal definition, computation, configurations

Figure s02 — alt-text: four stacked tape rows, each [0][0][0][⊔]. A red arrow (the head) points down at cell 0 in the top row, cell 1 in the next, cell 2 in the third, and cell 3 (the blank) in the bottom row where the state label reads q_acc. The red head marches one cell right per row — this is exactly steps 1→2→3→4 below.

Start configuration is $q_{0} 000$ ( $u = ε$ , state $q_{0}$ , $v = 000$ , head on the first 0).

Why this step? Every computation begins at $q_{0}$ with the head on the first input symbol — that's the definition of the start configuration. This is the top row of figure s02 (red head over cell 0).

Read 0, apply $δ (q_{0}, 0) = (q_{0}, 0, R)$ : write 0 back, move right ( $R$ ). $q_{0} 000 ⊢ 0 q_{0} 00$

Why? Move-right rule: the symbol we just wrote (0) joins the left part $u$ , and the state slides onto the next cell. This is the second row of s02: the red head has stepped to cell 1.

Same rule twice more: $0 q_{0} 00 ⊢ 00 q_{0} 0 ⊢ 000 q_{0}$

Why? Each 0 triggers the identical transition (rows 3 and 4 of s02, red head at cells 2 then 3). When the right part $v$ becomes empty, the head is now reading a blank $⊔$ — recall $⊔$ fills the tape past the input.

Read $⊔$ , apply $δ (q_{0}, ⊔) = (q_{accept}, ⊔, R)$ : $000 q_{0} ⊢ 000 q_{accept}$

Why? This is a halting configuration — the state is $q_{accept}$ (bottom row of s02, labelled q_acc), so the machine stops and says yes. ✓

Verify: input length $= 3$ , so $3$ right-moves over 0s plus $1$ blank step $= 4$ yields total. Final state $q_{accept}$ . Accepts. ✓

Example B — Cell C2 (normal reject)

Figure s03 — alt-text: one tape row [1][0][0] with a red head arrow pointing down at cell 0 (the 1), state label q0. A red annotation arrow points from the 1 to the words "first symbol is 1 → q_reject, HALT", and black text notes "the 00 is never read". This is step 2 below.

Start: $q_{0} 100$ ( $u = ε$ , state $q_{0}$ , $v = 100$ , head on the 1).

Why? Head on the first symbol 1 — the red head in figure s03.

Read 1, apply $δ (q_{0}, 1) = (q_{reject}, 1, R)$ : $q_{0} 100 ⊢ 1 q_{reject} 00$

Why? We reached $q_{reject}$ — a halting state (the red "→ q_reject, HALT" annotation in s03). The machine stops immediately and says no, even though 00 is still unread.

Verify: the string starts with 1, so it should be rejected — matches. Notice a TM, unlike a DFA, does not need to read the whole string to reject. Rejects. ✓

Example C — Cell C3 (empty input)

Figure s04 — alt-text: one tape row of four blank cells [⊔][⊔][⊔][⊔], red head arrow pointing down at cell 0, state label q0. A red annotation arrow points from cell 0 to "empty input: whole tape is blanks, head on cell 0"; black text reads "blank rule fires → q_accept". This is step 1 below.

Start configuration. On empty input the tape is all blanks, so cell 0 already holds $⊔$ . Writing the head-symbol explicitly, the start configuration is $q_{0} ⊔$ — that is, $u = ε$ , state $q_{0}$ , and $v = ⊔$ (head reading the blank at cell 0, exactly the red head in figure s04).

Why? By our convention, when the input part $v$ would be empty we make the leading blank explicit and write $q_{0} ⊔$ rather than a bare $q_{0}$ ; the two mean the same thing, but $q_{0} ⊔$ shows precisely which symbol the head reads.

Read $⊔$ , apply $δ (q_{0}, ⊔) = (q_{accept}, ⊔, R)$ : $q_{0} ⊔ ⊢ q_{accept} ⊔$

Why? The blank transition fires on step one (the "blank rule fires" note in s04). Halting state reached.

Verify: length- $0$ input $\Rightarrow 0$ right-moves over 0s $+ 1$ blank step $= 1$ yield total. Accepts $ε$ . ✓ (This machine recognizes $0^{*}$ , and $ε \in 0^{*}$ , so accepting is correct.)

Example D — Cell C4 + C5 (left-edge move and overwrite)

Figure s01 — alt-text: two tape rows. Top row [1][#][0] with a red head over cell 1 (#), state q3. A black ⊢ arrow points down to the bottom row [1][Y][0] with the red head over cell 0 (1), state q5. Two red annotations: "overwrite # → Y" pointing at the middle cell, and "move LEFT: head lands on cell 0 (left edge)" pointing at cell 0. This is step 1 below.

Apply $δ (q_{3}, #) = (q_{5}, Y, L)$ : $1 q_{3} #0 ⊢ q_{5} 1 Y 0$

Why? Overwrite (C5): the # under the head becomes Y (the red "overwrite # → Y" note in s01). Move left ( $L$ ) rule: the head steps onto the symbol immediately to its left, which is 1, so the new configuration is $u = ε$ , state $q_{5}$ , $v = 1 Y 0$ (head on the 1). Look at figure s01: the red head jumps from the middle cell down to cell 0.

Now suppose $δ (q_{5}, 1) = (q_{6}, 1, L)$ — another left ( $L$ ) move, but the head is already at cell 0. $q_{5} 1 Y 0 ⊢ q_{6} 1 Y 0$

Why? (C4) The tape does not extend left of cell 0. By convention the head stays put — it does not crash, does not throw an error. Only the state changes (here $q_{5} \to q_{6}$ ; the cell is rewritten 1→1, so the tape is unchanged). This is the left-edge special case from the parent note, and the red "head lands on cell 0" marker in s01 is exactly where the clamp bites.

Verify: after step 1 the tape reads 1Y0 and the head is at index 0. After step 2 the tape still reads 1Y0 and the head is still at index 0, because the clamp gives $max (0, index - 1) = max (0, - 1) = 0$ . ✓

Example E — Cell C6 (looping forever)

Figure s05 — alt-text: two tape rows, both [0][⊔], each labelled q0. In the top row the red head is on cell 0 (the 0); in the bottom row the red head is on cell 1 (the ⊔). A red curved arrow labelled "move R" goes top→bottom, and a red curved arrow labelled "move L" goes bottom→top, forming a closed loop. Black text notes "never reaches a halting state". This matches steps 1–3 below.

$q_{0} 0 ⊔ ⊢ 0 q_{0} ⊔$ (read 0, $δ (q_{0}, 0) = (q_{0}, 0, R)$ , move right).

Why? Standard move-right ( $R$ ); the right part becomes just the blank, so the head now reads $⊔$ (top→bottom, the "move R" arrow in figure s05).

$0 q_{0} ⊔ ⊢ q_{0} 0 ⊔$ (read $⊔$ , $δ (q_{0}, ⊔) = (q_{0}, ⊔, L)$ , move left).

Why? Move-left ( $L$ ): the head steps back left onto the 0. The tape is unchanged and the state is still $q_{0}$ (bottom→top, the "move L" arrow in s05).

We are back at $q_{0} 0 ⊔$ — the exact start configuration. $q_{0} 0 ⊔ ⊢ 0 q_{0} ⊔ ⊢ q_{0} 0 ⊔ ⊢ 0 q_{0} ⊔ ⊢ \dots$

Why this matters? The machine cycles between two configurations forever (the closed red loop in s05). It never halts — neither accepts nor rejects. This is exactly the "gap" that makes recognizable weaker than decidable, and the seed of the Halting Problem.

Verify: the configuration at even step counts is always $q_{0} 0 ⊔$ ; a period- $2$ cycle. Halting states encountered $= 0$ . Loops. ✓

Example F — Cell C7 (undefined / partial $δ$ )

Worked example When

$δ$ has no arrow for the current symbol Tape alphabet: $Γ = {a, b, ⊔}$ (with input alphabet $Σ = {a, b}$ ). Machine has only $δ (q_{0}, a) = (q_{accept}, a, R)$ . The symbol b is in $Γ$ but $δ (q_{0}, b)$ is not defined. Input b.

Forecast: the transition function is silent here. What is the standard convention?

Start: $q_{0} b$ ( $u = ε$ , state $q_{0}$ , $v = b$ , head reads b).
Look up $δ (q_{0}, b)$ — it does not exist.
- Why is this legal? $δ$ is allowed to be a partial function. By the undefined-transition convention stated at the top of this page, a missing arrow means: go to $q_{reject}$ and halt. $q_{0} b ⊢ q_{reject} b$

Verify: no matching rule $\Rightarrow$ implicit reject $\Rightarrow$ machine halts in $q_{reject}$ . So b is not in the recognized language. Any machine can be made total by adding all missing arrows into $q_{reject}$ ; behaviour is identical. ✓

Example G — Cell C8 (word problem, decided end-to-end)

Worked example "Is this binary string a palindrome?" — a decider, fully traced

Language $P = {w \in {0, 1}^{*} : w = w^{R}}$ (reads the same forwards and backwards). This is decidable. Tape alphabet: $Γ = {0, 1, X, ⊔}$ with input alphabet $Σ = {0, 1}$ . The working symbol $X$ is a cross-off marker: writing X over a cell records "this cell has already been checked and matched". ( $X \in / Σ$ — again $Σ ⊊ Γ$ .)

Transition function (all directions $L$ / $R$ as per the legend):

$δ (q_{0}, 0) = (q_{1}, X, R)$ — remember we saw a 0, cross it out, sweep right.
$δ (q_{0}, 1) = (q_{2}, X, R)$ — remember we saw a 1, cross it out, sweep right.
$δ (q_{0}, X) = (q_{accept}, X, R)$ and $δ (q_{0}, ⊔) = (q_{accept}, ⊔, R)$ — nothing left in the middle → accept.
$δ (q_{1}, 0) = (q_{1}, 0, R)$ , $δ (q_{1}, 1) = (q_{1}, 1, R)$ — in "seek right end, expecting a matching 0".
$δ (q_{1}, X) = (q_{3}, X, L)$ , $δ (q_{1}, ⊔) = (q_{3}, ⊔, L)$ — hit the far end, step back to the last real symbol.
$δ (q_{3}, 0) = (q_{5}, X, L)$ — the right end is a 0: match! cross it out, sweep back left.
$δ (q_{3}, 1) = (q_{reject}, 1, L)$ — right end is 1 but we needed 0: mismatch → reject.
Symmetrically for state $q_{2}$ (we remembered a 1): $δ (q_{2}, 0) = (q_{2}, 0, R)$ , $δ (q_{2}, 1) = (q_{2}, 1, R)$ , $δ (q_{2}, X) = (q_{4}, X, L)$ , $δ (q_{2}, ⊔) = (q_{4}, ⊔, L)$ , $δ (q_{4}, 1) = (q_{5}, X, L)$ (match), $δ (q_{4}, 0) = (q_{reject}, 0, L)$ (mismatch).
$δ (q_{5}, 0) = (q_{5}, 0, L)$ , $δ (q_{5}, 1) = (q_{5}, 1, L)$ — rewind to the left end.
$δ (q_{5}, X) = (q_{0}, X, R)$ — hit the left marker, step right to the next unchecked cell, back to $q_{0}$ for the next pass.

Forecast: input 0110. How many "peel a pair" passes before it decides, and what's the verdict?

Pass 1 (outer pair):

$q_{0} 0110 ⊢ X q_{1} 110$
- Why? $δ (q_{0}, 0) = (q_{1}, X, R)$ : cross the leftmost 0 to X, remember "expecting a 0" via state $q_{1}$ , move right ( $R$ ).
$X q_{1} 110 ⊢ X 1 q_{1} 10 ⊢ X 11 q_{1} 0 ⊢ X 110 q_{1} ⊔$
- Why? $δ (q_{1}, 1)$ and $δ (q_{1}, 0)$ keep the symbol and sweep right ( $R$ ); we're seeking the right end.
$X 110 q_{1} ⊔ ⊢ X 11 q_{3} 0$
- Why? $δ (q_{1}, ⊔) = (q_{3}, ⊔, L)$ : hit the blank past the string, step left ( $L$ ) onto the last real symbol 0.
$X 11 q_{3} 0 ⊢ X 1 q_{5} 1 X$
- Why? $δ (q_{3}, 0) = (q_{5}, X, L)$ : the right end is a 0 — match! Cross it to X, sweep left.
$X 1 q_{5} 1 X ⊢ X q_{5} 11 X ⊢ q_{5} X 11 X$
- Why? $δ (q_{5}, 1)$ rewinds left ( $L$ ) over the middle until we reach the left marker X.
$q_{5} X 11 X ⊢ X q_{0} 11 X$
- Why? $δ (q_{5}, X) = (q_{0}, X, R)$ : step right past the left marker, restart at $q_{0}$ on the shrunk string 11.

Pass 2 (inner pair): 7. $X q_{0} 11 X ⊢ X X q_{2} 1 X$

Why? $δ (q_{0}, 1) = (q_{2}, X, R)$ : cross the leftmost 1, remember "expecting a 1" via $q_{2}$ .

$X X q_{2} 1 X ⊢ X X 1 q_{2} X$
- Why? $δ (q_{2}, 1)$ sweeps right ( $R$ ) to the far end.
$X X 1 q_{2} X ⊢ X X q_{4} 1 X$
- Why? $δ (q_{2}, X) = (q_{4}, X, L)$ : hit the right marker, step left ( $L$ ) onto the last real symbol 1.
$X X q_{4} 1 X ⊢ X q_{5} X X X$

Why? $δ (q_{4}, 1) = (q_{5}, X, L)$ : the right end is a 1 — match! Cross it to X and sweep left ( $L$ ). Now every real symbol of the original 0110 has been crossed out; only Xs and the rewind remain.

$X q_{5} X X X ⊢ q_{5} X X X X ⊢ X q_{0} X X X$

Why? Rewind ( $q_{5}$ , moving $L$ ) to the left marker, then $δ (q_{5}, X) = (q_{0}, X, R)$ restarts at $q_{0}$ .

Termination: 12. $X q_{0} X X X ⊢ X q_{accept} X X X$

Why? $δ (q_{0}, X) = (q_{accept}, X, R)$ : the head reads an X, meaning the middle is empty (all crossed out). Accept — halt in $q_{accept}$ . ✓

Verify: $w = 0110$ , reverse $w^{R} = 0110$ . Equal $\Rightarrow$ palindrome $\Rightarrow$ accept. Number of matching passes $=$ length $/2 = 4/2 = 2$ , and the trace above shows exactly $12$ yield steps to halt. ✓ Contrast: on 0111, pass 1 crosses the leftmost 0 ( $q_{1}$ ), sweeps right, and $δ (q_{3}, 1)$ fires at the far 1 — mismatch → reject in a single pass. Because this TM always halts (each pass strictly shrinks the unmarked middle), it is a decider, not just a recognizer.

Example H — Cell C9 (exam twist: recognizer that loops)

Worked example The recognize-vs-decide trap

Tape alphabet: $Γ = {0, 1, ⊔}$ with input alphabet $Σ = {0, 1}$ . Consider a machine $M$ built to recognize $L = {0^{k} : k \geq 1}$ but whose designer forgot a reject arrow. Its transitions are: $δ (q_{0}, 0) = (q_{0}, 0, R)$ , $δ (q_{0}, ⊔) = (q_{accept}, ⊔, R)$ , and on symbol 1 it goes $δ (q_{0}, 1) = (q_{1}, 1, R)$ , $δ (q_{1}, 1) = (q_{1}, 1, R)$ , $δ (q_{1}, ⊔) = (q_{1}, ⊔, L)$ , $δ (q_{1}, 1)$ already given — the $q_{1}$ subroutine has no halting state anywhere.

Forecast: on input 01, does $M$ say yes, say no, or neither?

$q_{0} 01 ⊢ 0 q_{0} 1$ — read 0, $δ (q_{0}, 0) = (q_{0}, 0, R)$ , move right ( $R$ ).
- Why? Normal 0 transition; the 0 joins $u$ , head steps onto the 1.
$0 q_{0} 1 ⊢ 01 q_{1} ⊔$ — read 1, $δ (q_{0}, 1) = (q_{1}, 1, R)$ , go to $q_{1}$ , move right ( $R$ ) onto the blank past the input.
- Why? The first 1 sends us into the $q_{1}$ subroutine; the head now reads $⊔$ (written explicitly).
$01 q_{1} ⊔ ⊢ 0 q_{1} 1 ⊔$ — read $⊔$ , $δ (q_{1}, ⊔) = (q_{1}, ⊔, L)$ , move left ( $L$ ) onto the 1.
- Why? The blank rule in $q_{1}$ bounces the head back left onto the 1.
$0 q_{1} 1 ⊔ ⊢ 01 q_{1} ⊔$ — read 1, $δ (q_{1}, 1) = (q_{1}, 1, R)$ , move right ( $R$ ) onto the blank again.
- Why? We are back at the configuration of step 2's result. Steps 3–4 repeat forever: $01 q_{1} ⊔ ⊢ 0 q_{1} 1 ⊔ ⊢ 01 q_{1} ⊔ ⊢ \dots$ No halting state is ever entered.

Verify: 01 $\in / L$ (it contains a 1). $M$ never reaches $q_{accept}$ (correct — it should not accept) but also never reaches $q_{reject}$ — it loops. So $M$ is only a recognizer: it says "yes" for members but may loop forever on non-members instead of saying "no". This is exactly the Turing-recognizable $\neq =$ Turing-decidable distinction, and it's why the Halting Problem bites. ✓

Recall

Recall On empty input

$ε$ , how do we write the start configuration and what does the head read? $q_{0} ⊔$ — the head is at cell 0 reading a blank $⊔$ (the whole tape is blank). ::: $q_{0} ⊔$ , head reading a blank at cell 0 In the notation $u q v$ , where does the state $q$ sit? ::: Between $u$ and $v$ — immediately before the head-symbol (the first symbol of $v$ ). Never $q u v$ . A left ( $L$ ) move at cell 0 does what? ::: The head stays at cell 0 (left-edge convention) — it never crashes. A missing (undefined) transition means the machine does what? ::: Halts in $q_{reject}$ by convention — implicit reject. Entering $q_{accept}$ or $q_{reject}$ causes what to happen? ::: The machine halts immediately — no further $⊢$ steps. A machine that reaches $q_{accept}$ on members but loops on non-members is a ...? ::: recognizer (Turing-recognizable), not a decider. What makes the palindrome TM a decider rather than only a recognizer? ::: Every pass strictly shrinks the unmarked middle, so it always halts.