Difficulty: Intermediate to Advanced | Prerequisites: Algorithms study notes (Big O, proof techniques), basic set theory, familiarity with DFAs and regular expressions.
This is the computability half of a theory-of-computation course. It asks a more fundamental question than "how fast can we solve this?": it asks "can we solve this at all?" If you are arriving fresh, make sure you understand what a Turing machine is before tackling reductions and Rice's theorem. The ideas here underpin why certain problems (the halting problem, virus detection, program equivalence) have no general algorithmic solution.
Some problems have no algorithm that always halts with the correct answer. Turing machines formalise what "algorithm" means, and the decidable/recognisable/unrecognisable hierarchy classifies problems by whether a machine can solve them at all. Reductions and Rice's theorem are the main tools for proving a problem sits in one of these classes.
Turing machine (TM)
A theoretical model of computation with an infinite tape, a read/write head, and a finite set of states with transition rules (state, symbol → new state, new symbol, move left/right). Every TM defines exactly one language.
Think of it as the most powerful computer imaginable, with unlimited memory but still following a fixed set of rules.
DFA / regex
Finite automata and regular expressions. They recognise a strictly smaller class of languages than Turing machines. Multiple accept states are allowed, and every arrow from every state should have a valid destination.
Decider
A Turing machine that always halts: it accepts every string in the language and rejects every string not in the language. It never loops.
In simple terms, a decider always gives you a yes or no answer in finite time.
Recogniser (also: semi-decider)
A Turing machine where: if x is in the language A, the machine accepts x; if x is not in A, the machine either rejects or loops forever. A = L(M).
Think of it as a machine that can confirm membership but might run forever on non-members.
Decidable language
A language L is decidable if there exists a decider for it. Equivalently, both L and its complement are recognisable.
Recognisable language (also: recursively enumerable, r.e.)
A language is recognisable if there exists a Turing machine that accepts exactly the strings in the language (but may loop on strings outside it).
Unrecognisable language
A language for which no Turing machine exists that accepts exactly its strings.
Countability
A set is countable if it can be mapped to the natural numbers (ℕ). The set Σ* (all strings over a finite alphabet) is countable: you can list all strings of length 0, 1, 2, ... The set of all languages over Σ is uncountable.
Diagonalisation
A proof technique showing that the set of all languages is uncountable (and hence some languages have no TM). List all strings as rows, all TMs as columns, and flip the diagonal to construct a language not in the list.
Turing reduction (A ≤_T B)
A is Turing-reducible to B if a decider for A can be built using a "black box" (oracle) decider for B. If B is decidable, so is A. Equivalently, if A is undecidable, then B is undecidable.
In simple terms, you show that if you could solve B, you could solve A, so A is no harder than B.
Mapping reduction (A ≤_m B)
A function f such that x ∈ A if and only if f(x) ∈ B. Stronger than Turing reduction. Used for recognisability arguments as well as decidability.
Rice's theorem
For any non-trivial semantic property P of recognisable languages, the language L_P = {⟨M⟩ : L(M) ∈ P} is undecidable. A property is trivial if it contains all recognisable languages or none of them.
Think of it as: you cannot build a general algorithm that looks at a program's code and decides anything interesting about what that program computes.
Semantic property
A set of languages related to program behaviour (what the TM computes), not its syntax (how the code looks). P is a set {L ⊆ Σ* : L satisfies some condition}. L_P is the set of TM descriptions whose language is in P.
A Turing machine has a tape (infinite in one direction), a head that reads and writes one character at a time, a finite set of states, and a transition function δ: (state, symbol) → (new state, new symbol, direction). The tape includes one blank symbol. The input is a subset of the tape, and the tape contents can serve as the finite description of a TM.
Key conventions:
Transition notation: δ(q, a) = (q', b, R) means "in state q reading a, write b, move right, go to state q'."
A TM halts when it enters an accept or reject state.
Every Turing machine defines exactly one language: L(M) = the set of strings M accepts.
The hierarchy from most to least "solvable":
Decidable: A decider exists (always halts, always correct). All finite languages are decidable.
Recognisable (but not decidable): A recogniser exists (accepts members, may loop on non-members). The halting problem L_HALT sits here.
Unrecognisable: No TM accepts exactly the strings in this language. The complement of the halting problem sits here.
A language L is decidable if and only if both L and its complement L-bar are recognisable. If L is undecidable, then L or L-bar (or both) is unrecognisable.
Decidable languages are closed under union, intersection, and complement. Recognisable languages are closed under union and intersection but not complement.
Construct an explicit decider: a TM (or algorithm) that accepts every string in L and rejects every string not in L, and always halts. Alternatively, show L = L_P where P is a trivial property (Rice's theorem gives decidability for trivial properties).
The standard approach:
Assume for contradiction that a decider B exists for the language L you want to show is undecidable.
Use B as a subroutine to build a decider A for a language already known to be undecidable (typically L_HALT).
Since L_HALT is undecidable, A cannot exist, so B cannot exist either.
The reduction is written A ≤_T B (A reduces to B). The direction matters: you reduce FROM the known-undecidable problem TO the new one.
Worked example from the cheat sheet: proving L = {⟨M⟩ : M loops on 42 and 376 and rejects 281} is undecidable.
Assume B decides L.
Define a new machine M' from any machine M and input x: run M on x. If M halts, check whether the result triggers looping on 42/376 or rejecting 281.
Construct M' so that: if M halts on x, then M' loops on 376 and 42 and rejects 281 (putting ⟨M'⟩ in L). If M does not halt on x, then M' loops on everything (putting ⟨M'⟩ outside L, since it does not reject 281).
Run B on M'. If B accepts, M halts on x. If B rejects, M does not halt on x.
This decides HALT, which is a contradiction.
Two main approaches:
Show that its complement is undecidable and the language itself is recognisable. Since L is decidable iff both L and L-bar are recognisable, if L is recognisable and undecidable, then L-bar must be unrecognisable.
Alternatively, show both that the language is undecidable and that its complement is recognisable.
L_FINITE = {⟨M⟩ : M is a TM and L(M) is finite}.
The cheat sheet proves L_FINITE is undecidable by reducing from E_HALT = {⟨M, x⟩ : M halts on x}. The construction:
Given ⟨M, x⟩, build M' that ignores its own input w, runs M on x, and accepts if M accepts.
If M halts on x, then M' accepts everything: L(M') = Σ*, which is infinite, so ⟨M'⟩ is not in L_FINITE.
If M does not halt on x (loops), M' loops on everything: L(M') = ∅, which is finite, so ⟨M'⟩ ∈ L_FINITE.
A decider for L_FINITE would therefore decide E_HALT (with the accept/reject flipped), contradicting the undecidability of E_HALT.
Rice's theorem is a shortcut for undecidability proofs. It says: if P is a non-trivial semantic property of recognisable languages, then L_P is undecidable.
A property P is trivial if P contains all recognisable languages or P contains none of them.
A property P is non-trivial if there exists at least one recognisable language in P and at least one recognisable language not in P.
To prove undecidability using Rice's theorem:
Find a property P such that L = L_P.
Show P is non-trivial: find one TM whose language is in P (⟨M⟩ ∈ L_P) and one whose language is not (Σ* ∈ P and ∅ ∉ P, or similar).
Conclude L_P is undecidable.
To prove decidability:
Show L = L_P.
Show P is trivial.
Conclude L_P is decidable.
If L and L-bar are both recognisable, build a decider by running recognisers R and R' for L and L-bar in parallel (one step of each, alternating). One must accept; whichever does first tells you the answer.
If L is undecidable, then at least one of L or L-bar is unrecognisable.
Σ* and ∅ are both recognisable (and decidable). The set of all Turing machines is countable. The set of all languages is uncountable. Therefore most languages have no TM at all.
Students often confuse "undecidable" with "unrecognisable." They are different levels. Undecidable means no decider exists, but a recogniser might. Unrecognisable means no recogniser exists either.
The direction of a reduction trips people up. A ≤_T B means "A reduces to B," meaning B is at least as hard as A. To show B is undecidable, you reduce a known-undecidable A to B, not the other way round.
Rice's theorem applies only to semantic properties of programs (what the TM computes), not syntactic properties (how the code looks). "Does M have fewer than 100 states?" is syntactic and decidable. "Does M accept the empty string?" is semantic and undecidable by Rice's theorem.
Thinking that recognisable and co-recognisable are the same thing. A language can be recognisable without its complement being recognisable. Only when both are recognisable do you get decidability.
Assuming every subset of a decidable language is decidable. Subsets of decidable languages (or even of Σ*) can be anything, including undecidable or unrecognisable.
⚠️ Turing reduction proofs are a near-certainty on the exam. You will be given a language and asked to show it is undecidable by reducing from L_HALT or E_HALT. Practise the "assume B decides L, build a decider for HALT" template until it is automatic.
⚠️ Rice's theorem questions often ask you to identify whether a property is trivial or non-trivial, then state the conclusion. Make sure you can produce the two witness languages (one in P, one not in P).
⚠️ The interplay between L and L-bar is commonly tested: "If L is recognisable but not decidable, what can you say about L-bar?" Answer: L-bar is unrecognisable.
⚠️ Diagonalisation is sometimes tested directly: be able to explain why the set of all languages is uncountable while the set of all TMs is countable, and what that implies (most languages have no TM).
⚠️ Closure properties are a favourite for short-answer questions: decidable languages closed under ∪, ∩, complement; recognisable languages closed under ∪, ∩ but not complement.
True or false: If a language is undecidable, it is also unrecognisable.
Answer: False. The halting problem is undecidable but recognisable.
Fill in the blank: A language is decidable if and only if both it and its ______ are recognisable.
Answer: Complement.
True or false: Rice's theorem can be used to show that "Does M have exactly 5 states?" is undecidable.
Answer: False. The number of states is a syntactic property, not a semantic one. Rice's theorem does not apply.
Fill in the blank: In a Turing reduction A ≤_T B, if A is undecidable, then B is ______.
Answer: Undecidable.
True or false: The set of all Turing machines is uncountable.
Answer: False. The set of all TMs is countable (each TM has a finite description). The set of all languages is uncountable.
Q: Prove that L = {⟨M⟩ : M accepts at least one string} is undecidable.
A: Use Rice's theorem. Define P = {languages that are non-empty}. P is non-trivial: the language Σ* is non-empty (in P), and the language ∅ is empty (not in P). Both are recognisable. Therefore L_P is undecidable by Rice's theorem.
Q: If L is recognisable and L-bar is also recognisable, what can you conclude?
A: L is decidable. Run recognisers for L and L-bar in parallel. One must halt and accept on any input, giving a decider for L.
Q: Explain the difference between a Turing reduction and a mapping reduction.
A: A Turing reduction (A ≤_T B) uses a black-box decider for B as a subroutine, possibly calling it multiple times with different inputs. A mapping reduction (A ≤_m B) is a computable function f where x ∈ A iff f(x) ∈ B, with no subroutine calls. Mapping reductions are strictly stronger: A ≤_m B implies A ≤_T B, but not vice versa. Mapping reductions also transfer recognisability, not just decidability.
Q: Is the property "L(M) contains the string 0110" trivial or non-trivial? What does Rice's theorem tell you?
A: Non-trivial. The language {0110} is recognisable and satisfies the property. The language ∅ is recognisable and does not. Therefore L_P = {⟨M⟩ : 0110 ∈ L(M)} is undecidable.
Q: Give an example of a language that is unrecognisable.
A: The complement of the halting problem: L-bar_HALT = {⟨M, x⟩ : M does not halt on x}. L_HALT is recognisable (simulate M on x; if it halts, accept). Since L_HALT is undecidable, L-bar_HALT cannot be recognisable (otherwise L_HALT would be decidable).
Turing machines connect back to DFAs and regular languages: DFAs are a restricted form of TM (no writing, finite memory), and every regular language is decidable. The hierarchy runs regular ⊂ context-free ⊂ decidable ⊂ recognisable ⊂ all languages.
Reductions connect forward to NP-completeness. The same logical structure ("if you could solve B, you could solve A") appears in polynomial-time reductions used to prove NP-hardness. The difference is that Turing reductions deal with computability (possible vs impossible) while polynomial reductions deal with tractability (efficient vs inefficient).
Rice's theorem connects to software verification and the halting problem in practice: it is the formal reason you cannot write a program that checks arbitrary programs for correctness, termination, or security properties.
Turing machine, TM, decider, recogniser, semi-decider, decidable, undecidable, recognisable, recursively enumerable, r.e., unrecognisable, Turing reduction, mapping reduction, many-one reduction, halting problem, L_HALT, E_HALT, L_FINITE, Rice's theorem, semantic property, trivial property, non-trivial property, diagonalisation, countability, uncountable, complement, co-recognisable, closure properties, DFA, regular language, context-free language, computability theory, theory of computation, EECS 376, Foundations of Computer Science, University of Michigan