Universal Turing machine and the Church–Turing thesis
Universal Turing machine (UTM) is a single Turing machine that can simulate any other Turing machine given its description; the Church–Turing thesis states that the intuitive notion of 'effectively calculable' equals 'computable by a Turing machine'.
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
Engineers use the concept of a Universal Turing machine when reasoning about what any programmable computer can or cannot compute in principle — it formalises the idea of a stored-program computer. The Church–Turing thesis guides whether a problem is algorithmically solvable at all, so it helps decide when to stop looking for an algorithm and instead use approximation or heuristics.
Key ideas
Start from first principles used in this course (you already saw Turing machines in the syllabus list). Define again the terms we will use.
Turing machine (TM): A TM is a formal model of computation defined as a 7-tuple M = (Q, Σ, Γ, δ, q0, qaccept, qreject) where
- Q is a finite set of states,
- Σ is the input alphabet not containing the blank symbol,
- Γ is the tape alphabet with blank
␣and Σ ⊆ Γ, - δ : Q × Γ → Q × Γ × {L, R} is the (partial) transition function; it is undefined on qaccept and qreject (the machine halts when it enters either state),
- q0 ∈ Q is the start state,
- qaccept ∈ Q is the accept state,
- qreject ∈ Q is the reject state, qreject ≠ qaccept.
(Bolded terms are defined. This is the standard deterministic single-tape TM used for most proofs.)
Configuration: A configuration of TM M is a snapshot (state, tape contents, head position). Universities often write configuration as ...a q b... meaning the head scans the symbol after the state symbol.
Computable function: A (partial) function f : Σ* → Σ* is computable if there exists a TM M such that for every x ∈ Σ*, if f(x) is defined then M halts with f(x) on its tape, and if f(x) is undefined then M does not halt (so f is partial computable; if f is defined for all x, it is total computable).
Universal Turing machine (UTM): A TM U is universal if there is a standard encoding scheme ⟨M⟩ that maps any TM M to a string such that for every M and input w, U on input ⟨M⟩#w (where
#is a separator) simulates M on w and produces the same output and halts exactly when M halts. Formally:U(⟨M⟩, w) = M(w)
(This equality is an informal notation meaning "the computation of U on ⟨M⟩ and w yields the same result as M on w".)
Encoding / description: To build a UTM you choose an encoding that lists M's states, tape alphabet and transition table as a string. A common university encoding uses numbers or binary for states and symbols, with a delimiter alphabet (for example
#,,) to separate items. The encoding must be effective (computable), injective, and uniquely decodable so that U can parse it.Church–Turing thesis: Exact, exam-style statement:
"Any function which would naturally be regarded as computable by an effective method (an algorithm) is computable by a Turing machine."
Notes: this is not a mathematical theorem but a thesis (a claim about the informal notion of algorithm). It is supported by the equivalence of many formal models (lambda-calculus, μ-recursive functions, Post machines) which all define the same class of computable functions.
Existence of a UTM: Standard constructive proof (sketch universities expect):
- Fix a concrete encoding scheme ⟨·⟩ for any TM as a finite string over a fixed alphabet.
- Design U so its tape initially contains ⟨M⟩#w.
- U interprets ⟨M⟩ as a finite table of rules. U maintains a simulated tape (part of its tape) and a marker for the simulated head and current simulated state.
- For each simulated step: U scans ⟨M⟩ to find the rule for (simulated-state, scanned-symbol), writes the new symbol on the simulated tape, moves the simulated head marker left/right and updates the simulated state; then repeat.
- Because ⟨M⟩ is finite, U can always find the applicable rule or detect it is undefined. This constructs a single TM that simulates any M.
(When writing this in an exam, describe a tape layout and the subroutines U needs: parse description, find matching rule, update simulated tape, update pointer.)
Relationship to other topics in the syllabus: UTM formalises the idea behind "stored-program" computers (links to Turing machines and variants, decidability, halting problem). Using a UTM, one proves the undecidability of the halting problem by self-reference / diagonalisation.
Diagram to draw (describe exactly): To show how a UTM tape looks, draw a single horizontal tape with cells. On the left place the encoding ⟨M⟩ written as blocks separated by
|(for states, symbols, rules). Then a#cell, then the simulated tape contents (the input w) with a distinct marker (draw an arrow or box) marking the simulated head position. Label: "encoded machine ⟨M⟩", "separator #", "simulated tape contents", "simulated head marker", and indicate the real head of U which moves to scan different parts of the tape when simulating.
Formulas
M = (Q, Σ, Γ, δ, q0, qaccept, qreject) — M is a Turing machine; Q: set of states, Σ: input alphabet, Γ: tape alphabet, δ: transition function, q0, qaccept, qreject: states. unit: not applicable. Applies to deterministic single-tape TMs.
δ : Q × Γ → Q × Γ × {L,R} — transition function mapping current state and read symbol to next state, symbol to write, and head move. unit: not applicable. Applies to deterministic TMs.
U(⟨M⟩, w) = M(w) — U simulates M on w; both sides denote the resulting output or halting behaviour. unit: not applicable. Applies when ⟨M⟩ is the standard encoding and U implements the simulation correctly.
HT = {⟨M, w⟩ | M is a TM and M halts on input w} — Halting problem language (set of encoded pairs where M halts on w). unit: not applicable. Used when discussing decidability. Fact: HT is recognisable (recursively enumerable) but undecidable; its complement is not recognisable.
(These are formal notations students must remember; they are not physical units.)
Worked examples
Example 1 — Encoding and one-step simulation
Problem: Let M be a TM that on alphabet {1} replaces the first 1 by 0 and moves right, then halts. Encode M in a simple scheme and show U simulating M on input 11 step-by-step.
Solution (model exam answer):
- Describe M informally: states Q = {q0, q1, qaccept}, tape alphabet Γ = {1,0,␣}, start q0. Rules:
- (q0, 1) → (q1, 0, R)
- (q1, 1) → (qaccept, 1, R) — this is a dummy to move to accept after first replacement.
- Choose an encoding: encode states as numbers: q0->0, q1->1, qaccept->2; symbols 1->1, 0->0, blank->b. Encode a rule (p,a)→(q,b,D) as
p,a->q,b,D;For our M:0,1->1,0,R; 1,1->2,1,R;So ⟨M⟩ =0,1->1,0,R;1,1->2,1,R;. - Input string w =
11. The UTM tape initially (conceptually) is:[0,1->1,0,R;1,1->2,1,R;] # [1 1]with the simulated head marker at the first1of the input. - Simulation steps by U (high-level):
- U reads simulated state q0 and symbol 1. It scans ⟨M⟩, finds
0,1->1,0,R;and applies it: write0at head, set simulated state q1, move simulated head right. - Simulated tape becomes
0 1, simulated head at second cell, simulated state q1. - Next, U finds rule
1,1->2,1,R;and applies it: writes1(no change), sets state qaccept and moves right. - Since simulated state is qaccept, simulation halts and U halts with tape content
01.
- U reads simulated state q0 and symbol 1. It scans ⟨M⟩, finds
- Final answer (bold in exam): U halts with tape
01, matching M(11).
(When writing this on exams, include the exact strings, the simulated tape after each step, and which rule was chosen.)
Example 2 — Using UTM to prove halting problem undecidable (short model answer)
Question: Sketch a proof that HT is undecidable using a UTM.
Answer (model steps):
- Assume, for contradiction, there is a decider H for HT. H(⟨M, w⟩) returns "yes" if M halts on w, "no" otherwise.
- Construct a TM D that on input x does: run H on ⟨x, x⟩. If H says "no" (x does not halt on x), then D halts; if H says "yes", then D loops forever.
- By the assumption that H decides HT, D is a valid TM; obtain its encoding ⟨D⟩ and consider D run on ⟨D⟩.
- Analyze: If D(⟨D⟩) halts, then H(⟨D, D⟩) would have said "yes", so by D's definition D would loop — contradiction. If D(⟨D⟩) loops, H would have said "no" and D would halt — contradiction. Thus H cannot exist.
- Therefore HT is undecidable.
(UTM is implicit: we can build D because we can encode machines and simulate them; UTM justifies that encoding and simulation are effective.)
Common mistakes
- Poorly defined encoding: in answers, students sometimes forget to fix a concrete encoding when asked to sketch a UTM; exam answers must state a clear encoding convention.
- Assuming a UTM must be efficient; UTM is about possibility, not time complexity. Do not claim polynomial-time simulation unless you prove it for a specific variant (not required here).
- Mixing up the simulated head (position in the simulated tape) and the real head (position of U on its own tape) in diagrams and traces.
For your exam
Kinds of questions you will see:
- Definitions: give precise definitions of Turing machine, Universal Turing machine, encoding, Church–Turing thesis.
- Short notes: explain existence of UTM; compare models (lambda calculus, μ-recursive) to support Church–Turing.
- Derivations/proofs: construct (sketch) a UTM or prove undecidability of the halting problem using encoding and self-reference.
- Trace/algorithms: trace U simulating a small M on a short input (give tape after each simulated step).
- Diagrams: draw the UTM tape layout and label parts (see diagram instructions above).
What a full-marks answer includes:
- Precise definitions with bolded or clearly labelled terms.
- A stated encoding convention when constructing or describing a UTM.
- A step-by-step simulation routine (parse description, find rule, update simulated tape, update simulated head/state).
- For Church–Turing thesis questions, state it exactly and explain that it is a thesis (not provable) and cite equivalence with other models as evidence.
- For undecidability proofs, clearly state the assumed decider and the constructed machine, then show the contradiction by self-application.
Quick check
- What is a Universal Turing machine (one line)?
- State the Church–Turing thesis (one line).
- Give the 7 components of a deterministic Turing machine.
Answers: 1) A TM U that, given an encoding ⟨M⟩ and input w, simulates M on w and reproduces M's behaviour. 2) Any function that can be calculated by an effective procedure can be computed by a Turing machine (this is a thesis, not a proved theorem). 3) (Q, Σ, Γ, δ, q0, qaccept, qreject).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?