Turing machines — formal definition, computation, configurations: Visual walkthrough

Step 1 — Draw the machine as a picture, not a formula

WHAT. A Turing machine has three physical parts we can literally draw:

an infinite tape — a long strip of cells, each holding one symbol;
a head — a little pointer sitting under exactly one cell, which can read that cell and write over it;
a finite control — a small box holding the current state, a label like $q_{0}$ that means "which line of the instruction book am I on".

WHY. The formal 7-tuple $M = (Q, Σ, Γ, δ, q_{0}, q_{accept}, q_{reject})$ lists these parts, but a list hides the geometry. Computation is movement of a head over a tape — so we must picture the tape to reason about it.

PICTURE. Below, the blue strip is the tape. Each box is one cell. The yellow triangle is the head, pointing at one cell. The green box on top is the finite control showing the state $q_{0}$ . Cells to the far right hold the blank symbol $⊔$ — that is how the machine knows the input has ended and the empty tape begins.

Step 2 — Freeze one frame: a configuration $u q v$

WHAT. A configuration is a single snapshot of the machine: everything you'd need to press "pause" and later press "play" and get exactly the same future. We write it as three things glued together: $tape left of head u current state q tape from head rightward v$

$u$ — the string of symbols strictly to the left of the head.
$q$ — the state, written between the two tape pieces so its position marks the head.
$v$ — the string starting at the head cell and going right (up to the last non-blank).

WHY. The future of the machine depends on nothing else: not on how it got here, not on the clock. State + tape + head position is a complete description. Bundling them into one word $u q v$ lets us treat a whole computation as a list of words — easy to write, easy to check.

PICTURE. We label each region on the tape. Notice the state symbol $q$ sits immediately left of the cell the head reads — the head always points at the first symbol of $v$ .

Step 3 — The instruction book $δ$ : one lookup = one move

WHAT. The transition function $δ$ is the rulebook. You feed it two things — the current state and the symbol under the head — and it hands back three things: $δ (state now q, symbol read a) = (next state r, symbol to write b, move L or R D)$

Input $q$ : which state we're in.
Input $a$ : what the head currently reads.
Output $r$ : the state we jump to.
Output $b$ : what we overwrite the current cell with (possibly the same symbol).
Output $D \in {L, R}$ : step the head one cell Left or Right.

WHY. Everything a TM can ever do is this one operation, repeated. There is no separate "read" and "write" and "move" — one lookup does all three atomically. That is the whole reason the model is so simple to analyse.

PICTURE. The rule below is a machine-part: two dials in (state, symbol), three dials out (state, symbol, direction).

Step 4 — The yield $⊢$ when moving RIGHT

WHAT. Now we make a configuration become the next one. We say $C_{1}$ yields $C_{2}$ , written $C_{1} ⊢ C_{2}$ , if applying $δ$ once to $C_{1}$ produces $C_{2}$ . Take the rule $δ (q, b) = (r, c, R)$ with tape neighbour $a$ just left of the head: $u a q b v ⊢ u a written over b c new state r v$

Term by term:

$b$ (the read symbol) gets replaced by $c$ .
Because we moved right, the head leaves the cell holding $c$ behind — so $c$ joins the left part $u a c$ .
The state marker $r$ slides right and now sits before $v$ , meaning the head reads the first symbol of $v$ .

WHY $⊢$ and not " $=$ "? These two configurations are not equal — one is the "before", one is the "after". The turnstile $⊢$ is a one-way arrow: "this frame is legally followed by that frame." It answers the question what happens next?, which $=$ cannot express.

PICTURE. Watch the yellow head slide right and the freshly written $c$ (red) drop into the left region.

Step 5 — The yield $⊢$ when moving LEFT

WHAT. Same idea, opposite direction. Rule $δ (q, b) = (r, c, L)$ , with $a$ the symbol just left of the head: $u a q b v ⊢ u new state r new head symbol a written over b c v$

Term by term:

$b$ still gets overwritten by $c$ .
But now the head steps left, landing on $a$ . So the state marker $r$ moves to sit before $a$ — the head now reads $a$ .
$c$ is left to the right of the head, so it sits between $a$ and the old $v$ : the right part becomes $a c v$ .

WHY it looks different from RIGHT. Moving left means the previously-left symbol $a$ becomes the new thing under the head, whereas moving right means the newly-written symbol was passed over. That asymmetry is exactly why the two yield rules look different — the direction decides which symbol the head ends up on.

PICTURE. The head jumps left onto $a$ ; $c$ stays put where $b$ used to be.

Step 6 — Edge case: falling off the LEFT end

WHAT. What if the head is already at cell 0 (the leftmost cell, so $u$ is empty) and the rule says move Left? The tape does not extend left of cell 0. Rule $δ (q, b) = (r, c, L)$ with no $a$ to the left: $q b v ⊢ r c v$

Term by term:

$b$ is still overwritten by $c$ (the write always happens).
The head cannot go left, so by convention it stays on cell 0. The state marker $r$ therefore sits at the very front, and $c$ remains under the head.

WHY this convention. We need some well-defined behaviour so the machine never gets undefined. Two conventions exist; the standard one is "the head stays put at the wall." No crash, no error — the computation simply continues, now reading $c$ .

PICTURE. The head bumps the left wall (red barrier) and stays; only the written symbol and state change.

Step 7 — Edge case: reading past the input into blanks

WHAT. When the head walks right off the end of the written input, it enters the blank region. In our word notation the right part $v$ becomes empty. Convention: an empty $v$ is treated as a single blank $⊔$ . So the configuration $u q$ is the same as $u q ⊔$ , and the machine looks up $δ (q, ⊔)$ .

$u q \equiv u q ⊔ δ (q, ⊔) apply a normal yield$

WHY. The tape is infinite to the right and full of blanks. Without this rule the machine would "run out of tape". Instead it always has something to read — a blank — so $δ$ is always given a symbol.

PICTURE. The head steps onto the first blank; the rulebook is consulted with symbol $⊔$ .

Step 8 — A whole computation, halting on accept

WHAT. Chain the yields together. Start configuration on input $w$ is $q_{0} w$ . Run $C_{0} ⊢ C_{1} ⊢ C_{2} ⊢ \dots$ until a halting configuration appears (state $q_{accept}$ or $q_{reject}$ ) — or forever, if it loops.

Take the tiny machine $δ (q_{0}, 0) = (q_{0}, 0, R)$ and $δ (q_{0}, ⊔) = (q_{accept}, ⊔, R)$ . On input 00: $q_{0} 00 ⊢ 0 q_{0} 0 ⊢ 00 q_{0} ⊢ 00 q_{accept}$

Frame by frame:

$q_{0} 00$ : read 0, write 0, move R → 0 joins left ⇒ $0 q_{0} 0$ .
$0 q_{0} 0$ : read 0 again, same rule, move R ⇒ $00 q_{0}$ .
$00 q_{0}$ : right part empty ⇒ head reads $⊔$ ; rule $δ (q_{0}, ⊔)$ fires ⇒ state becomes $q_{accept}$ . Halt, accept. ✓

WHY this is "acceptance". $M$ accepts $w$ the instant some $C_{i}$ carries state $q_{accept}$ . The language recognised is $L (M) = {w : M accepts w}$ . If instead it can loop forever on some inputs, $M$ merely recognises (Turing-recognizable); if it always halts, it decides (Turing-decidable).

PICTURE. Three tape frames stacked as a film strip, head sliding right until it hits the blank and flips to $q_{accept}$ (green).

The one-picture summary

This single diagram compresses the whole walkthrough: a configuration $u q v$ , the lookup $δ (q, head) = (r, write, D)$ , and the two directions of yield $⊢$ , plus the wall (left edge) and the blank sea (right edge).

Recall Feynman retelling — say it back in plain words

Picture a long paper strip full of boxes, mostly empty (blanks) except for a bit of writing on the left. A little pointer sits under one box. A tiny notebook (the state) tells the pointer which rule to use. To take one step: look up the box's symbol and your notebook page in the rulebook. The rulebook says three things — write this new symbol here, flip to that notebook page, and shuffle one box left or right. That single act is one "yield," and we draw it with a one-way arrow $⊢$ . Chain the steps and you get a movie of the computation. If you're on the far-left box and told to go left, you just stay against the wall. If you walk off the right end of the writing, the box you land on is a blank, and you look that up. Keep going until your notebook reaches the special page "accept" (done, yes) or "reject" (done, no) — or maybe you never stop, and that endless loop is the whole reason some questions can never be answered.

Recall Quick self-test

What are the three pieces of a configuration? ::: The left tape $u$ , the current state $q$ , and the tape from the head rightward $v$ — written $u q v$ . In $u a q b v ⊢ u a c r v$ , why did $c$ join the left part? ::: Because the move was Right, so the head stepped past the freshly written $c$ , leaving it behind on the left. The head is at cell 0 and $δ$ says move Left. What happens? ::: It writes the new symbol, changes state, but stays on cell 0 (the wall convention) — no crash. The right part $v$ is empty and $δ (q, ⊔)$ is undefined-looking — what symbol does the head read? ::: The blank $⊔$ ; an empty $v$ is treated as a single $⊔$ . What is the difference between recognising and deciding a language? ::: Recognise: says yes for members but may loop on non-members. Decide: always halts with yes or no.