Difficulty: Intermediate to Advanced | Prerequisites: basic set theory, proof techniques, familiarity with Turing machine definitions.
This topic sits at the heart of EECS 376. Computability theory asks the deepest question in CS: what can a computer solve at all, regardless of time or resources? It connects to complexity theory (P vs NP), algorithm design (knowing when a problem is solvable before optimising), and cryptography (hardness assumptions). You should already be comfortable with formal definitions of languages, sets and basic proof by contradiction.
TL;DR: Some problems have no algorithm that solves them, full stop. Decidable languages are the ones a Turing machine always answers correctly (accept or reject). Recognisable languages are weaker: the machine may loop forever on "no" instances. Diagonalisation and reductions are the main tools for proving these impossibility results.
Decidable language
A language L for which there exists a Turing machine (a "decider") that halts on every input, accepting strings in L and rejecting strings not in L.
In simple terms, a decidable language is one where an algorithm can always give you a definite yes or no.
Turing-recognisable language (recursively enumerable)
A language L for which there exists a TM that accepts every string in L. For strings not in L, the machine may reject or loop forever.
Think of it as: the machine will eventually say yes to anything that belongs, but might never get back to you on things that do not.
Unrecognisable language
A language for which no Turing machine exists that accepts exactly its strings. Most languages over any alphabet are unrecognisable.
Countable set
A set whose elements can be placed in a one-to-one correspondence with the natural numbers (or a subset of them). All finite sets and the integers are countable.
Uncountable set
A set that is strictly larger than the natural numbers. The set of all real numbers is the classic example, proved uncountable by Cantor's diagonalisation argument.
Diagonalisation argument
A proof technique (due to Cantor) that shows no enumeration of a set can list every element. Applied in CS to prove the reals are uncountable and that certain languages are undecidable.
Mapping reduction (≤m)
A computable function f that transforms instances of one language into instances of another, such that x ∈ A if and only if f(x) ∈ B. Used to transfer undecidability from a known-undecidable problem to a new one.
Think of it as: "if I could solve B, I could solve A by converting every A-question into a B-question."
Complement of a language
Given a language L over alphabet Σ, its complement L̄ is the set of all strings in Σ* that are not in L.
Regular language
A language recognisable by a finite automaton (equivalently, described by a regular expression). The smallest class in the Chomsky hierarchy.
Every multi-tape TM has an equivalent single-tape TM. They recognise and decide exactly the same class of languages. The single-tape simulation is slower (quadratic overhead), but computational power is identical.
A TM may accept, reject or loop on a given input. "Must either accept or reject" describes a decider, not a TM in general.
The Church-Turing thesis asserts that any "effectively computable" function can be computed by a Turing machine.
Decidable = a TM (decider) exists that halts on every input, accepting members of L and rejecting non-members.
Recognisable = a TM exists that accepts every string in L. On strings not in L it may reject or loop forever.
Every decidable language is recognisable. The converse is false: L_ACC = {⟨M, x⟩ : M accepts x} is recognisable but not decidable.
If both L and its complement L̄ are recognisable, then L is decidable (run both recognisers in parallel; one must halt).
The class of decidable languages is closed under union, intersection, complement and symmetric difference.
Complement closure proof: given a decider M for L, build M' that swaps M's accept and reject states. M' decides L̄.
Symmetric difference closure proof: given deciders M_A for A and M_B for B, build M_L that runs both, accepts when exactly one accepts (XOR logic). Since both always halt, M_L always halts.
Any finite language is always decidable, even if it is a subset of an undecidable language. A TM can hard-code a finite list of strings and check membership directly.
The set of all Turing machines is countable (each TM has a finite description encodable as a string).
The set of all languages over an alphabet Σ is uncountable (it is the power set of Σ*, and the power set of a countably infinite set is uncountable by Cantor's theorem).
The set of all recognisable languages is countable (at most one per TM).
The set of all unrecognisable languages is uncountable: total languages minus recognisable languages. The countable set of recognisable languages cannot account for the uncountable set of all languages.
The set of all decidable languages is countable (a subset of the recognisable languages).
Cantor's diagonal argument proves the real numbers are uncountable. Assume a listing of all reals; construct a new real differing from the n-th entry in its n-th digit. This real is not in the listing, contradicting the assumption.
The same technique proves the existence of undecidable languages: there are uncountably many languages but only countably many TMs.
L₂₈₁ = {⟨M, x⟩ : M accepts x in fewer than 282 steps} is decidable. Simulate M on x for exactly 281 steps; if it has not accepted, reject. The simulation always halts because the step count is bounded.
L_ACC and L_HALT are not decidable. L₂₈₀ = {⟨M⟩ : M rejects at least 280 inputs} is not decidable (requires checking infinitely many inputs).
The class of regular languages is closed under union, concatenation and Kleene star. Also closed under complement and intersection.
To show A ≤m B, construct a computable function f so that x ∈ A ⟺ f(x) ∈ B.
If A ≤m B and B is decidable, then A is decidable.
If A ≤m B and A is undecidable, then B is undecidable.
L_REJ = {⟨M, x⟩ : M rejects x}.
Construction: given ⟨M, x⟩, build M' that on any input w runs M on x. If M halts (accept or reject), M' rejects w.
If ⟨M, x⟩ ∈ L_HALT, M halts on x, so M' reaches the reject step and rejects w. Thus ⟨M', w⟩ ∈ L_REJ.
If ⟨M, x⟩ ∉ L_HALT, M loops on x, so M' loops on w and never rejects. Thus ⟨M', w⟩ ∉ L_REJ.
This is a valid mapping reduction.
L_TSD = {⟨M⟩ : L(M) is the set of all socially distant strings} (a string in {0,1}* where every '1' is at least six positions from any other '1').
Assume decider H for L_TSD. Build a decider D for L_ACC on input ⟨M, x⟩: construct M' that on input w checks if w is socially distant (always decidable), rejects if not, and if w is socially distant, runs M on x, accepting w if M accepts.
If ⟨M, x⟩ ∈ L_ACC, M' accepts exactly the socially distant strings, so H accepts ⟨M'⟩.
If ⟨M, x⟩ ∉ L_ACC, M' accepts nothing (the empty set, which is not the set of all socially distant strings), so H rejects ⟨M'⟩.
Since L_ACC is undecidable, H cannot exist. Therefore L_TSD is undecidable.
Complement of a decidable language: If M decides L, then M' (with swapped accept/reject) decides L̄. Decidable languages are closed under complement.
Symmetric difference: L = A ⊕ B = (A \ B) ∪ (B \ A). If A and B are decidable, L is decidable (XOR the outputs of both deciders).
Socially distant string recurrence: S(n) = S(n − 1) + S(n − 6) for n > 6, with base cases S(n) = n + 1 for n ≤ 6. The first term covers strings ending in '0'; the second covers strings ending in '1' (forcing five preceding '0's).
Countability hierarchy: finite ⊂ countably infinite ⊂ uncountable. The set of TMs is countable; the set of all languages is uncountable; the gap is filled by unrecognisable languages.
The undecidability of the halting problem is why no tool can perfectly detect all infinite loops or verify all software properties. Static analysis tools use conservative approximations instead.
Mapping reductions underpin the entire theory of NP-completeness: showing that one problem is "at least as hard" as another is how we classify thousands of practical problems (scheduling, routing, circuit design) as likely intractable.
Students often think a Turing machine must always halt. It does not. Only a decider must halt on every input. A general TM (a recogniser) is allowed to loop forever on inputs not in its language.
Students often confuse "undecidable" with "unrecognisable." L_HALT is undecidable but recognisable (a TM can simulate and accept if it halts; it just cannot detect non-halting). A language is unrecognisable only when no TM accepts exactly its members.
A finite subset of an undecidable language is always decidable. Students sometimes assume undecidability "infects" subsets. It does not: finiteness guarantees decidability.
The complement of an undecidable language is not necessarily unrecognisable. For example, L_HALT is recognisable, and its complement is unrecognisable, but other undecidable languages may have recognisable complements.
⚠️ Know the precise definitions of decidable vs recognisable. Exam questions test whether you can distinguish the two by their behaviour on strings not in the language.
⚠️ Bounded-step simulation is a common exam pattern: if you can cap the number of steps a TM runs, the resulting language is decidable.
⚠️ Mapping reductions appear in both short-answer and long-answer form. Be ready to construct a machine M' and argue both directions (membership and non-membership).
⚠️ Countability questions frequently pair with "which of these sets is uncountable?" Know: TMs countable, all languages uncountable, unrecognisable languages uncountable.
⚠️ Closure of decidable languages under complement is a one-line proof (swap accept/reject). Expect it as a building block in longer proofs (e.g. symmetric difference).
True or false: every recognisable language is decidable. (False: L_ACC is recognisable but not decidable.)
True or false: a finite language is always decidable. (True.)
Fill in the blank: the set of all Turing machines is ______ (countable/uncountable). (Countable.)
True or false: if L is decidable, then L̄ is also decidable. (True: swap accept and reject states.)
Fill in the blank: to show L_HALT ≤m L_REJ, construct a machine M' that ______ w whenever M halts on x. (Rejects.)
Q: Which of the following languages is decidable: L_ACC, L_HALT, or L₂₈₁ = {⟨M, x⟩ : M accepts x in fewer than 282 steps}?
A: L₂₈₁. Simulate M on x for 281 steps. If it accepts within that bound, accept; otherwise reject. The bounded step count guarantees the decider halts.
Q: Which of the following sets is uncountable: the set of all decidable languages, the set of all Turing machines, or the set of all unrecognisable languages?
A: The set of all unrecognisable languages. The set of all languages is uncountable (power set of Σ*), and the recognisable languages are countable (one per TM). The remaining unrecognisable languages must be uncountable.
Q: If a language L is decidable, is its complement always decidable, sometimes decidable, or always undecidable?
A: Always decidable. Build a new TM that runs the decider for L and swaps accept/reject.
Q: A language L is recognisable if there exists a TM that does what?
A: Accepts for all x ∈ L, and either rejects or loops for all x ∉ L.
Q: What does a diagonalisation argument prove about the set of real numbers?
A: That it is uncountable. No listing of reals can be complete, because a new real can always be constructed that differs from every listed entry.
Q: Prove that L_HALT ≤m L_REJ, where L_REJ = {⟨M, x⟩ : M rejects x}.
A: Construct computable f(⟨M, x⟩) = ⟨M', w⟩ where M' on input w simulates M on x. If M halts (accept or reject), M' rejects w. If ⟨M, x⟩ ∈ L_HALT, then M halts, so M' rejects w, meaning ⟨M', w⟩ ∈ L_REJ. If ⟨M, x⟩ ∉ L_HALT, then M loops, so M' loops and never rejects, meaning ⟨M', w⟩ ∉ L_REJ. The mapping is valid.
Q: Let A and B be decidable. Prove that A ⊕ B (the symmetric difference) is decidable.
A: Since A and B are decidable, deciders M_A and M_B exist that halt on all inputs. Build M_L: on input x, run M_A and M_B. Accept if exactly one accepts; reject otherwise. M_L always halts (both sub-machines halt), and it accepts x if and only if x ∈ (A \ B) ∪ (B \ A).
Computability connects directly to complexity theory (P, NP, NP-completeness): once you know a problem is decidable, the next question is how efficiently it can be solved. The reduction technique used here (mapping reductions) reappears in NP-completeness proofs, where polynomial-time reductions replace general computable reductions. Regular languages and their closure properties are the simplest tier of the Chomsky hierarchy and provide a contrast: everything decidable about regular languages (emptiness, equivalence, membership) becomes undecidable for Turing-recognisable languages.
Related Terms / Search Tags
Computability, decidability, Turing-decidable, Turing-recognisable, recursively enumerable, undecidable, unrecognisable, countable, uncountable, Cantor diagonalisation, halting problem, L_HALT, L_ACC, L_REJ, mapping reduction, many-one reduction, complement closure, symmetric difference, regular languages, closure properties, Kleene star, Church-Turing thesis, bounded computation, socially distant strings, EECS 376, foundations of computer science, University of Michigan