Designing Turing machines
Designing Turing machines: formal definition, design strategies, standard constructions (multi-tape simulation, nondeterminism), worked designs for a^n b^n and palindrome, common exam pitfalls and quick checks.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Turing machines are the formal model of what an algorithm can compute. Engineers use Turing-machine ideas to reason about what problems are decidable, to prove limits of computation (undecidability), and to model low-level algorithms when proving correctness and complexity (for example in computability and complexity theory papers or advanced compiler design). Knowing to design simple Turing machines trains you to give rigorous algorithm descriptions used in proofs and exams.
Key ideas
Define terms first and use plain language.
- Turing machine: A mathematical model of computation consisting of a finite control (a finite set of states), an infinite tape divided into cells (each holding a symbol), and a read/write head that moves left or right. Formally given below as a 7-tuple.
- Formal definition (exact): A deterministic Turing machine M is a 7-tuple M = (Q, Σ, Γ, δ, q0, q_accept, q_reject) with the assumptions:
- Q is a finite nonempty set of states.
- Σ is the input alphabet (does not contain the blank symbol).
- Γ is the tape alphabet with Σ ⊆ Γ and a distinguished blank symbol ␣ ∈ Γ\Σ (often written as B or _ ).
- q0 ∈ Q is the start state.
- q_accept ∈ Q and q_reject ∈ Q are distinct halting states.
- transition function δ : Q \ {q_accept, q_reject} × Γ → Q × Γ × {L, R}.
- The machine starts with the input written on tape cells from the left, the head at the leftmost input symbol, and blanks elsewhere.
- Deterministic Turing machine (DTM): the machine above — at any point exactly one action is prescribed by δ for each (state, symbol).
- Nondeterministic Turing machine (NTM): similar but with a transition relation or function δ that maps to a set of possible moves: δ : Q × Γ → P(Q × Γ × {L, R}). The machine accepts if any branch accepts.
- Universal Turing machine (UTM): A single machine U that, given an encoding ⟨M, x⟩ of a Turing machine M and input x on its tape, simulates M on x. UTMs formalize programmable computation and are central in undecidability proofs.
- Configuration: A description of the current state, the entire tape contents, and head position. Usually written as u q v meaning tape has u v with head over first symbol of v and machine in state q.
- Recognizes / accepts: A machine recognizes (is said to accept) a language L if it accepts every x ∈ L (halts in q_accept) and may either reject or loop on x ∉ L. Also called recursively enumerable languages.
- Decides: A machine decides a language L (is decidable or recursive) if it halts (in q_accept or q_reject) on every input and accepts exactly the strings in L.
- Halting: A computation halts when it enters q_accept or q_reject. Otherwise it may loop forever.
Principles of designing Turing machines (practical steps):
- Give a high-level description first: what the head does, what symbols mark progress, and when it halts.
- Choose a small set of marker symbols added to Γ to record processed characters (for instance, X, Y).
- Use loops of the form: scan right to find a symbol, mark it, return left to a remembered position, repeat.
- Break the design into clear phases (e.g., mark, match, erase, check blank) and name states for phases: q_scan, q_mark, q_return.
- If necessary, use multiple tracks or simulate multiple tapes conceptually to simplify design; later convert to single-tape if required.
Standard constructions universities expect you to know (statements and assumptions):
- Multi-tape to single-tape simulation: Any k-tape deterministic Turing machine running in time t(n) can be simulated by a single-tape deterministic Turing machine that runs in time O(t(n)^2) (assume t(n) ≥ n). Describe the simulation by laying out k tracks separated by special separators and simulating each step by scanning to update track symbols and head markers.
- Nondeterministic to deterministic simulation: A nondeterministic Turing machine that runs in time t(n) can be simulated by a deterministic Turing machine in time 2^{O(t(n))} (exponential blow-up) by performing a breadth-first search of the computation tree; this ensures accepting branches are found if they exist. Furthermore, NTMs and DTMs have the same computability power: they recognize and decide exactly the same sets of languages; nondeterminism affects efficiency, not what is computable.
Diagrams to draw in exam answers (describe exactly):
- Draw a horizontal row of boxes for tape cells. Put the input symbols in the left boxes, blanks elsewhere. Draw an arrow above one box to indicate the head position and label the arrow with the current state, e.g., → q2. If showing multi-tape, draw parallel rows separated by vertical bars and mark each head position with an upward arrow and state.
- For state diagrams: draw circles for each state, label with state name. Draw directed arrows labeled as read symbol → write symbol,move (e.g., a→X,R). Mark q_accept and q_reject with double circles.
Formulas
M = (Q, Σ, Γ, δ, q0, q_accept, q_reject) — M is the Turing machine; Q: states (no unit); Σ: input alphabet; Γ: tape alphabet; δ: transition function as below. Applies for deterministic TM definition.
δ : (Q \ {q_accept,q_reject}) × Γ → Q × Γ × {L, R} — transition function for DTM. Meaning: on state q and tape symbol s, machine goes to state q', writes s' and moves left or right. No units.
δ_N : Q × Γ → P(Q × Γ × {L, R}) — transition function for NTM (maps to set of possible moves). P(...) is power set.
Configuration = u q v — finite strings u ∈ Γ*, v ∈ Γ+ (nonempty) with head on first symbol of v (write ␣ explicitly if head is on blank); q is current state.
Time_M(n) — the worst-case number of transitions M makes on any input of length n. No units, applies to time complexity analysis.
Space_M(n) — the maximum number of tape cells used on any input of length n. No units, applies to space complexity analysis.
Note: These are not physical formulas with units; they are formal notations. Verify notation of blank symbol and writing convention in your course.
Worked examples
Example 1 — Design and trace a DTM that decides L = {a^n b^n | n ≥ 0}. High-level idea: Repeatedly find leftmost a, mark it as X, then scan right to find rightmost unmarked b, mark it Y. Repeat until no a left; then check there is no unmarked b.
Formal description (state names and key transitions in words):
- Γ = {a, b, X, Y, ␣}. Start in q0.
- q0: If read a, replace with X, move right and go to q1. If read Y or X, move right and stay in q0. If read b or blank when no unmarked a found, go to q_check.
- q1: Move right skipping X and Y and a until you see an unmarked b. If see b, replace it with Y, move left and go to q2. If you reach blank without seeing b, reject (unequal counts).
- q2: Move left until you see a blank ␣ (left end of the nonblank region), then move right one cell and go to q0. This reliably returns the head to the left end to search for the next unmarked a.
- q_check: From current position, scan to see if any unmarked a or b remain. If none, accept; else reject.
Trace on input aaabbb (show key steps):
- Tape initial: [a][a][a][b][b][b][␣]..., head at first a, state q0.
- q0 reads a → write X, move R, go q1. Tape: [X][a][a][b][b][b]...
- q1 moves right to find b, skipping a: passes a,a then at first b writes Y, move L, goto q2. Tape: [X][a][a][Y][b][b]...
- q2 moves left back to leftmost unmarked a, stops, goto q0. Repeat marking next a and corresponding b. After three iterations tape becomes [X][X][X][Y][Y][Y] and q_check verifies nothing unmarked, accepts. Final answer: accept.
Example 2 — DTM to recognize palindromes over {0,1} (decide). High-level: Match first and last symbols, mark them, repeat inward. If mismatch, reject; if all matched (only marked symbols remain or single unmarked), accept.
Design sketch:
- Use markers X and Y (or single marker X for both sides). States: q0 (start), q_mark_left, q_seek_right, q_check, q_accept, q_reject.
- q0: If read X, move right and stay in q0 (skip marked). If read 0 or 1, mark it (replace with X and store the symbol via states q0_0 or q0_1), then move right to q_seek_right. If you see blank ␣, accept.
- q_seek_right: Move right to the end of the nonblank region (scan right until you see ␣), then move left to the first unmarked symbol (skip X). If such a symbol exists, compare it with the stored symbol; if they match, mark it X, then move left until you see ␣ and move right to re-enter q0; else reject. If no unmarked symbol exists on the right (only X before ␣), this was the middle symbol of an odd-length palindrome; return left to ␣ and right to q0 and it will accept next.
Trace for input 101: mark first 1, search rightmost unmarked (1), match, mark, then middle 0 remains -> accept.
(Full state tables are expected in long exam answers; here we give the design and trace — an examiner will accept a clear state-wise table or state diagram.)
Common mistakes
- Writing transition rules that allow no move for some (state,symbol) — in a DTM you must define δ for all non-halting states and tape symbols, or explicitly say machine rejects/halts.
- Not returning the head properly when using two-way scans (forgetting to move back to leftmost position before next phase).
- Forgetting that a TM may loop: to claim a machine decides a language you must show it halts on every input.
- In reductions: mixing recognizability (recursively enumerable) and decidability; be precise with halting behavior.
For your exam
Kinds of questions:
- Definitions: define Turing machine, configuration, decide vs recognize. Full marks require the 7-tuple and explanation of each component.
- Short notes: explain multi-tape simulation, nondeterminism, Universal Turing machine. Full marks require statement of simulation overhead and a sketch of construction.
- Derivations: prove simulation theorems (multi-tape to single-tape). Full marks require clear simulation steps, how head positions are encoded, and time overhead derivation.
- Design problems: give a machine for a language (e.g., a^n b^n, palindromes, {ww^R}). Full marks require a high-level algorithm, state list or state diagram or transition table, and a sample trace.
- Diagrams: draw tape contents and state transitions. Label every arrow and symbol.
A full-marks answer should always: state assumptions, give formal machine description (7-tuple or transition table), provide a clear high-level idea, include at least one short trace showing correctness, and explain halting conditions.
Quick check
- What is the blank symbol and where do you list it?
- Give the formal type signature of the DTM transition function δ.
- Why does simulating a nondeterministic TM on a deterministic TM usually cost exponential time?
Answers: Blank symbol is a distinguished tape symbol in Γ\Σ (often written ␣ or B) listed in Γ; δ : (Q \ {q_accept,q_reject}) × Γ → Q × Γ × {L,R}; because deterministic simulation must explore all nondeterministic branches (e.g., via breadth-first search), and the number of branches can grow exponentially in the number of nondeterministic steps.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?