7.3Rice's theorem
The idea
Rice's theorem: any non-trivial property of the language of a Turing machine is undecidable.
Think of it like this: You can never inspect a program and decide anything interesting about what it computes.
Why it exists
It settles dozens of questions at once: emptiness, regularity, finiteness of L(M) ...
How it works
- The property must be about L(M) (semantic), not about the machine's code.
- It must be non-trivial: some machines have it, some do not.
- Then it is undecidable.
- Properties of behaviour (running time) or syntax (number of states) are NOT covered.
Worked example: "Takes more than 2021 steps on some input"
Not a property of L(M) and only bounded inputs matter, so it is decidable by simulation. Rice does not apply.
Now play with it
- →Take the quiz and notice how many "obvious" ones are actually decidable.
Is this TM property decidable? · question 1 of 7
L(M) = ∅
Check yourself
By Rice's theorem, which is undecidable?
Exam notes (the dense version)
Every non-trivial semantic property of L(M) is undecidable (e.g. L(M) = ∅, L(M) is regular, L(M) is finite, L(M) contains ε). It does not apply to trivial properties, to syntactic properties of M (number of states) or to properties of M's behaviour that are not about L(M) (e.g. "M halts within k steps").
Previous year questions: Decidability & Undecidability (7)
PYQs are grouped by topic, so this is the full set for Decidability & Undecidability; try the ones that match this subtopic. Open all 7 on the topic page.