Turing machines · configurations, nondeterminism and the tableau, step by step

A Turing machine is a finite control with a read/write head on an unbounded tape — and a configuration C = α q β is nothing but a word: tape content αβ, current state q, head on the first symbol of β. The page runs a machine step by step and shows, side by side, the tape picture, the configuration string, and the case of the computation relation ⊢ that produced it, while counting time and space. For a nondeterministic machine the computation is a tree: pick branches by clicking, or let the page find an accepting computation — the sequence of choices is the certificate.

Tape and head

What just happened

Choices made so far — the certificate

Finite control δ

Machine descriptionplain text · load to run

One transition per line, q a -> q' b D with D ∈ {L, R, N} (read a in state q: write b, move D, go to q'). The blank □ is written _. Several lines for the same (q, a) make the machine nondeterministic; a missing line makes δ(q,a) = ∅, a dead end.

# the machine of the slides
name: the machine of the slides
start: q0
halt: qhalt
input: abaaabaaa
q0 a -> q0 a R
q0 b -> q1 b R
q0 _ -> qhalt _ N
q1 a -> q1 b R
q1 b -> q0 b R
q1 _ -> qhalt _ N

Directives: start (default: state of the first transition), halt (default qhalt), input (the word to run on), sigma (input alphabet, default: all non-blank symbols read from the input), name, limit (time limit), note (a remark shown at the start of the run). Lines starting with # are comments.

Conventions, as in the lecture. A configuration α q β ∈ Γ*QΓ⁺ is identified with all versions that differ in leading □s of α or trailing □s of β; the page always shows the shortest representative (keeping β ≠ ε). At the boundary (n = 1 moving right, m = 0 moving left) the rule of ⊢ is applied to αqβ□ resp. □αqβ. M(x) = {y : q₀x ⊢* q_halty}: the machine produces output only if it halts with nothing left of the head; then y = β ∈ Γ⁺. M accepts x iff 1 ∈ M(x). time_M(x) = sup{t : q₀x ⊢^t q_halty} ∪ {0}, space_M(x) = sup{|αβ| : q₀x ⊢* αqβ} ∪ {0}. The Corner cases examples in the machine menu exercise each of these rules.