Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Decidability and the halting problem

Decidability studies which problems (languages) a Turing machine can always answer correctly; the halting problem is the classic undecidable example showing limits of algorithmic computation.

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

Decidability tells an engineer which questions about programs and systems can be answered automatically and which cannot. Knowing that the halting problem is undecidable prevents wasted effort trying to build a perfect program analyzer and guides practical work toward sound-but-incomplete tools (static analyzers, model checkers, heuristics).

Key ideas

Start with a clear model of computation: a Turing machine is an abstract machine with a finite control, a tape divided into cells storing symbols, a head that reads/writes and moves, and a transition function; it models general algorithms. A language is a set of finite strings over an alphabet Σ. A language is decidable (also called recursive) if there exists a Turing machine that, on every input string, halts and correctly answers YES (accept) if the string is in the language, and NO (reject) otherwise. A language is Turing-recognizable (also called recursively enumerable) if there exists a Turing machine that accepts every string in the language and either rejects or loops forever on strings not in the language.

Define the halting set precisely: HALT = { <M, w> | M is a Turing machine and M halts on input w }. Here <M,w> is an encoding (finite string) that describes the pair. The central result is:

Theorem (Undecidability of HALT). There is no Turing machine that decides HALT.

Proof (standard diagonal/self-reference by contradiction):

  1. Assume for contradiction there exists a decider H for HALT. So H(<M,w>) halts and returns YES iff M halts on w, and NO otherwise.
  2. Using H as a subroutine (it is assumed available and always halts), construct a new Turing machine D that takes one input x and does: (a) Let Mx be the machine encoded by x (treat x as a description of a machine). (b) Run H on pair <Mx, x>. (c) If H says Mx halts on input x, then D loops forever. If H says Mx does not halt on x, then D halts (and accepts).
  3. Ask: what happens when D is run on its own encoding <D>? Consider D(<D>): By construction, H(<D, <D>>) predicts whether D halts on <D>. If H says D halts on <D>, D will loop forever — contradiction. If H says D does not halt on <D>, D halts — contradiction. Both cases contradict the correctness of H.
  4. Therefore no such decider H exists; HALT is undecidable.

Important corollary and distinctions:

  • HALT is Turing-recognizable: there is a machine that simulates M on w step by step and accepts if simulation halts; this machine may loop forever if M never halts. Thus HALT is in RE (recursively enumerable) but not in R (recursive).
  • The complement of HALT, ¬HALT = {<M,w> | M does not halt on w}, is not Turing-recognizable. If both HALT and ¬HALT were Turing-recognizable, then HALT would be decidable (simulate both recognizers in dovetailing; if the HALT recognizer accepts first, accept; if the ¬HALT recognizer accepts first, reject), contradicting undecidability.

Define reduction: A language A is reducible to language B (mapping reduction) if there is a computable function f such that x ∈ A ⇔ f(x) ∈ B. If A is undecidable and A ≤m B then B is undecidable. Reductions are the central proof tool for showing undecidability.

What to draw (diagram description for exam answers): draw three boxes left-to-right labeled "input x", "transformer f (computable)", "oracle for B (decider/recognizer)". Arrow from x to f to f(x) to oracle. For the halting proof draw a loop: an assumed decider H is boxed and used by machine D; then draw D receiving its own encoding to show the self-reference contradiction.

Formulas

HALT = { <M, w> | M is a Turing machine and M halts on input w }

  • <M,w>: encoding of Turing machine M and input w. No SI unit. Applies when defining the halting language.

¬HALT = { <M, w> | M does not halt on input w }

  • Complement of HALT.

A ≤m B means there exists a computable function f such that for all x: x ∈ A ⇔ f(x) ∈ B.

  • f is a total computable function (Turing-computable). No SI unit. Used in reductions to transfer undecidability.

R = set of decidable (recursive) languages; RE = set of Turing-recognizable (recursively enumerable) languages. co-RE = set of languages whose complements are Turing-recognizable (co-Turing-recognizable). A language is decidable iff it is both in RE and in co-RE (equivalently, both it and its complement are Turing-recognizable).

Worked examples

Example 1 — Model answer: Prove HALT is not decidable.

  • State HALT as above. Assume H decides HALT. Construct D as in Key ideas step-by-step: on input x, run H on <x,x>; if H says YES (x halts on x) then loop, else halt and accept. Ask what D does on <D>. Both outcomes contradict H's correctness. Conclude H cannot exist. This is the classic self-reference proof. (This is the standard full-marks answer expected.)

Example 2 — Show HALT is Turing-recognizable but ¬HALT is not Turing-recognizable.

  • Recognizability of HALT: Construct machine R that on input <M,w> simulates M on w step-by-step. If the simulation halts at some step, R accepts; if M never halts, R never accepts (may loop). Hence HALT ∈ RE.
  • Nonrecognizability of ¬HALT: Suppose ¬HALT were recognisable by S. Then simulate R and S in parallel (dovetailing) on input <M,w>: whichever accepts first determines membership. This would decide HALT, contradicting undecidability. Therefore ¬HALT ∉ RE.

Example 3 — Reduction example (show language L = { <M> | M halts on input <M> } is undecidable):

  • Observe L is essentially HALT restricted to pairs where input equals machine encoding; reduce HALT to L by mapping <M,w> to a machine M' that on input y ignores y and simulates M on w, then halts iff M halts on w. Then <M,w> ∈ HALT ⇔ <M'> ∈ L. Since HALT is undecidable, L is undecidable. Show M' construction precisely in steps (write pseudo-code of M').

Common mistakes

  • Confusing "halts and accepts" with "halts". Always be precise: HALT concerns halting, not acceptance.
  • Informal or missing self-reference in the diagonal proof: you must explicitly describe machine D using H and then evaluate D on its own encoding to get the contradiction.
  • Using non-computable reductions: when claiming a mapping reduction exists, show f is computable (give construction or machine that computes f).
  • Thinking that undecidability implies impossible to say anything useful: forget to mention semi-decision procedures, reductions, or restricted decidable subclasses.

For your exam

Typical question types:

  • Define terms (decidable, Turing-recognizable). A full answer defines and contrasts both with simple examples.
  • Prove HALT is undecidable (write full diagonal proof): include formal statement of HALT, construction of D, and the contradiction when running D on <D>.
  • Show a language is (un)decidable using reduction: give computable mapping and argue correctness.
  • Show recognizability or nonrecognizability: give simulation algorithm or use complement-arguments.
  • Draw and explain diagrams: show the flow of an assumed decider used to construct a paradox machine.

A full-marks answer includes precise definitions, clear construction of helper machines, argument that helper machine is computable, and the contradiction or correctness proof. Always state assumptions (e.g., allowed to encode machines as strings) and be explicit about halting vs acceptance.

Quick check

  1. Define "decidable language" in one sentence.
  2. Is HALT Turing-recognizable, co-Turing-recognizable, both, or neither? Give one-line justification.
  3. What is a mapping reduction (A ≤m B)?

Answers: 1) A language is decidable if some Turing machine halts on every input and accepts exactly the strings in the language. 2) HALT is Turing-recognizable but not co-Turing-recognizable; simulate M on w to recognize HALT, but complement would make HALT decidable. 3) A mapping reduction is a computable function f such that x ∈ A ⇔ f(x) ∈ B; it transforms membership questions for A into membership questions for B.

Notes for the reviewer: I have tried to be precise with formal statements and the standard diagonal proof. Where I am unsure I list checks below.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?