Turing Machines, Decidability and Undecidability
A Turing machine is a finite automaton with a tape it can move over in both directions and write on, and that is enough to compute anything computable — the Church–Turing thesis is the claim that no reasonable model does better, and nothing in ninety years has contradicted it. What makes this the most conceptual part of the paper is that the interesting results are all negative, and the vocabulary for them has to be exact. A language is decidable if some machine always halts and answers correctly. It is recognisable (or recursively enumerable) if some machine accepts every string in the language but is allowed to run forever on strings outside it. Those are different, and the gap between them is where undecidability lives: the halting problem is recognisable and not decidable, which means you can confirm a halt by waiting but can never confirm a non-halt. There are two ways to see that undecidable languages must exist, and the counting argument is the more honest one to start from: there are countably many Turing machines and uncountably many languages, so almost every language has no machine at all — undecidability is the normal case and decidability the rare one. From there, Rice's theorem is the tool that makes most exam questions immediate: any non-trivial property of the language a machine recognises is undecidable. Not the hard ones — any of them. And the last thing worth having exactly right is the decidability grid, because it is not uniform: equivalence is decidable for DFAs and undecidable for context-free grammars, even though emptiness and membership are decidable for both.
Rice's Theorem, the Shortcut That Answers Most Questions
Rice's theorem: every non-trivial property of the language a Turing machine recognises is undecidable. Non-trivial means only that some machine has the property and some machine does not. So all of these are undecidable, and none of them needs a separate reduction: is L(M) empty, is L(M) finite, is L(M) regular, does L(M) contain the string 01, is L(M) = Σ*, do two machines recognise the same language.
⚠️ Rice applies to the language, not to the machine
The theorem is about properties of L(M) — the set of strings accepted — and says nothing about properties of the machine as a piece of syntax. "Does M have more than seven states?" is a property of the machine and is perfectly decidable: count them. "Does M ever write a blank?" is likewise a syntactic question about the transition table. But "is L(M) empty?" is a property of the language and is undecidable. The test to apply is whether two machines recognising the same language must always get the same answer: if yes, it is a language property and Rice bites; if two such machines can differ, the property is about the machine and Rice is silent. That single test resolves the entire class of question, and it is the one candidates skip.The Decidability Grid, Which Is Not Uniform
| Question | DFA | CFG | Turing machine |
|---|---|---|---|
| Is w in the language? (membership) | Decidable | Decidable (CYK) | Undecidable, but recognisable |
| Is the language empty? | Decidable | Decidable | Undecidable |
| Do two descriptions give the same language? | Decidable | UNDECIDABLE | Undecidable |
| Is the language infinite? | Decidable | Decidable | Undecidable |
⚠️ The one cell that breaks the pattern
Read down the CFG column and it looks reassuring — membership, emptiness and infiniteness are all decidable — and then equivalence is not. That single cell is the most-asked fact in this table, precisely because the rest of the column invites the generalisation "context-free things are decidable". The reason equivalence falls is that deciding it would let you decide much harder questions about grammars; the reason it survives for DFAs is Myhill–Nerode, which gives each regular language a unique minimal DFA, so equivalence reduces to minimise-and-compare. There is no canonical form for a context-free grammar, and that absence is the whole difference. Related and also undecidable for CFGs: is a grammar ambiguous, and is the intersection of two CFLs empty.Key takeaways
- Decidable means halts on every input; recognisable allows running forever on non-members.
- Turing machines are countable and languages are uncountable, so almost every language has no machine.
- L is decidable exactly when L and its complement are both recognisable — run the two in parallel.
- The halting problem is recognisable and undecidable, so its complement is not even recognisable.
- Rice: every non-trivial property of L(M) is undecidable — empty, finite, regular, contains 01, all of them.
- Rice does not apply to properties of the machine: "more than seven states" is decidable by counting.
- The test: if two machines with the same language must get the same answer, it is a language property.
- Equivalence is decidable for DFAs and UNDECIDABLE for CFGs — no canonical form for a grammar.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
Which of these problems is decidable?
Show answer
Answer: B — Given two DFAs, do they accept the same language?
DFA equivalence is decidable, and the reason is Myhill–Nerode: each regular language has a unique minimal DFA, so minimise both machines and check whether they are identical up to renaming. Option A is the cell of the grid that breaks the pattern — membership, emptiness and infiniteness are all decidable for CFGs, and equivalence is not, because a context-free grammar has no canonical form to compare. Option C is undecidable by Rice, being a non-trivial property of L(M). Option D, grammar ambiguity, is also undecidable. So three of four are undecidable, and the one that is not is the one with a canonical form behind it.By Rice’s theorem, which of the following about a Turing machine M is DECIDABLE?
Show answer
Answer: C — Whether M has more than seven states
Rice applies to properties of L(M), the language recognised, and A, B and D are all non-trivial properties of it — so all three are undecidable. Option C is a property of the machine as a syntactic object: read the transition table and count. The test that settles this whole family of questions is whether two machines recognising the same language must always get the same answer. For "is L(M) empty" they must, so it is a language property and Rice bites. For "more than seven states" they need not — the same language has machines of many sizes — so it is not a language property and Rice says nothing about it.A language L is recognisable and its complement is also recognisable. It follows that L is:
Show answer
Answer: A — Decidable
Decidable. Run the two recognisers in parallel on the input, alternating steps. The input lies in L or in its complement, so exactly one of the two must eventually accept — and the combination therefore always halts with the right answer. That is the definition of a decider. The theorem is the most useful one in the topic because of its contrapositive, which is the standard exam fact: the halting problem is recognisable and is not decidable, so its complement cannot be recognisable at all. Options C and D overreach badly — decidability says nothing about being regular or context free, and {aⁿbⁿcⁿ} is decidable while being neither.The strongest reason undecidable languages must exist is that:
Show answer
Answer: B — There are countably many Turing machines and uncountably many languages
Each Turing machine is a finite object and can be written as a finite string, so the machines are countable. Languages are arbitrary subsets of Σ*, and the power set of a countably infinite set is uncountable by Cantor's argument. So there are strictly more languages than machines, and undecidability follows by counting — no construction needed. Option A is true and is a weaker answer to this question: it names one undecidable language, whereas the counting argument shows almost all languages are undecidable, which is the stronger and more surprising statement. Option D is false: a Turing machine has finite control and an unbounded tape, and that unboundedness is exactly what separates it from a finite automaton.Which of the following are undecidable for context-free grammars? (More than one may be correct.)
Show answer
Answer: A — Whether two grammars generate the same language; B — Whether a grammar is ambiguous; D — Whether the intersection of two context-free languages is empty
A, B and D. Equivalence is undecidable because a context-free grammar has no canonical form to compare — the contrast with DFAs, where Myhill–Nerode supplies a unique minimal machine, is the whole reason the two differ. Ambiguity is undecidable, and so is emptiness of an intersection, which is unsurprising once you recall that the intersection need not even be context free. C is decidable: mark the non-terminals that can derive a terminal string, propagate upward, and check whether the start symbol gets marked. So the CFG column of the decidability grid is mostly decidable with equivalence as the exception, and that exception is what this question is for.The complement of the halting problem is:
Show answer
Answer: C — Not even recognisable
Not even recognisable. The halting problem itself is recognisable — simulate the machine and accept if it halts — and it is not decidable. Now apply the theorem: a language is decidable exactly when both it and its complement are recognisable. If the complement were recognisable, halting would be decidable, which it is not. So the complement has no recogniser at all. Option B is the answer for the halting problem itself rather than its complement, and it is the natural slip. The pair is the standard illustration that the recognisable languages are not closed under complement, unlike the decidable ones.Membership — is w in L? — is undecidable for which kind of description?
Show answer
Answer: C — A Turing machine
For a Turing machine, membership is recognisable but not decidable: simulate M on w and accept if it accepts, but if M loops there is no point at which you may conclude it never will. For a DFA you run the string through in |w| steps. For a context-free grammar the CYK algorithm decides membership in O(n³) after conversion to Chomsky normal form. A regular expression converts to a DFA. So the tape is what breaks decidability, and the reason is precisely the unboundedness that gives the Turing machine its power — the same feature appears as strength in the Church–Turing thesis and as a limit here.Which of these classes are NOT closed under complement? (More than one may be correct.)
Show answer
Answer: C — Recognisable languages; D — Finite languages
Recognisable and finite languages, for completely different reasons. Recognisable is the deep case: the halting problem is recognisable and its complement is not, which settles it with one example — the class is defined by the promise "accepts every member, may run forever otherwise", and there is no way to invert a promise like that. Finite is the shallow case, and worth spotting rather than dismissing: over a non-empty alphabet Σ* is infinite, so the complement of any finite language is infinite and therefore not finite. Decidable languages are closed, because a decider always halts and you can simply flip its answer; regular languages are closed by swapping a DFA's accepting states. The test to carry is whether the class is defined by a promise you can invert.