Motivation
Many questions about a program ask what inputs it accepts, rather than how its code is written. Does it accept any string? Is its language finite? Is its language regular? Such questions may look different, but a single reduction proves that every nontrivial property of the recognized language is undecidable.
The key is to build a machine that either recognizes a chosen reference language or recognizes nothing, depending on whether a particular computation halts. The new machine need not know which case holds. It merely simulates the computation whenever it receives an input. A hypothetical property decider would distinguish the cases and thereby decide halting.
Definitions
Definition 5.3.1
(Recognizable language)
Fix a finite alphabet with at least two symbols, designate two distinct symbols as and , and fix an effective encoding of deterministic Turing machines whose inputs are words over . For a machine , let be the set of words on which eventually accepts. A machine may reject or run forever on other words. A language is recognizable if it equals for some such machine.
Definition 5.3.2
(Property of languages and nontriviality)
A property is a collection of recognizable languages over . It is nontrivial if some recognizable language belongs to it and some recognizable language does not. The associated decision problem takes an encoded machine and asks whether . We assume a standard encoding in which a syntactic validity check is decidable; malformed encodings can be rejected. The particular choice of ordinary effective machine encoding does not change the reduction argument.
Theorem 5.3.3
(Rice's theorem)
Every nontrivial property of recognizable languages is undecidable: no decider correctly determines for every machine whether has the property.
Theorem 5.3.4
(The halting problem used in the reduction)
There is no decider that, given an encoded deterministic Turing machine and an input , determines whether halts on .
The second theorem is the standard halting undecidability result established in the computability companion chapter. “Halts” includes either acceptance or rejection. The property in Rice's theorem concerns the accepted language alone; two machines accepting the same set must receive the same answer even if their running times and rejection behavior differ.
The reduction when the empty language is outside the property
Proof
(Halting reduces to a nontrivial property)
Assume first that . Nontriviality supplies a recognizable language and a fixed machine recognizing . Given a halting instance , effectively construct a machine that behaves as follows on any input :
- Simulate on the fixed word .
- If that simulation halts, run on and accept exactly when accepts.
If never halts on , the first step runs forever for every , so . If does halt, the finite first step is followed by the simulation of , so . This remains true whether accepts or rejects ; only halting controls the branch.
The map is computable: a machine description can contain the finite encodings of and and instructions for the two simulations. The construction does not attempt to decide whether the first simulation will halt. A hypothetical decider for would answer yes on exactly when halts on , contradicting halting undecidability.
Proof X-ray
Where the hypotheses of Rice's theorem enter
Nontriviality is used twice. It supplies the fixed recognizable language whose machine is wired into , and in the remaining case it keeps the complementary property nontrivial. The assumption makes the dichotomy work: the construction can only produce or , exactly one of which lies in , so the decider's answer on reports whether halts. Semantic invariance is used when the decider is applied to : its answer depends only on , not on how the code was written. The non-obvious move is that waits on instead of testing whether halts, so is computable even though identifying the language it produces is not. The argument closes by contradiction: a decider for composed with this computable map would decide halting.
The remaining case
Proof
(The remaining case by complementing the property)
If , consider the complementary property within the class of recognizable languages: it contains precisely those recognizable languages outside . It is still nontrivial, and it does not contain . By the preceding argument its decision problem is undecidable. If were decidable, swapping yes and no answers would decide , a contradiction. This completes the proof.
Common mistake
(Complementing the property is not complementing the languages)
The complement here is a complement of a property of languages, not the complement of each language. We are not claiming that every recognizable language has a recognizable complement. A hypothetical decider returns a Boolean answer on each machine encoding, so exchanging that answer decides the complementary property even though language complementation itself can be difficult.
Worked examples
Worked example 5.3.5
(The construction for the property of containing 0)
Let be the recognizable languages that contain the word . Then , the language belongs to , and can be a machine that accepts exactly the input . For an instance , the machine first simulates on and then runs on its own input. If halts on , even by rejecting, the simulation ends, so . If runs forever on , then never reaches and . A decider for “contains ” would therefore decide halting. The rejecting case is the edge case: halting, not acceptance, controls the branch.
Worked example 5.3.6
(The remaining case for finiteness)
Let be the finite recognizable languages, so and the construction above does not apply directly. The complementary property consists of the infinite recognizable languages: and . Take and let accept every word. Then if halts on , and otherwise. So is infinite exactly when halts on . A decider for finiteness, with its answers swapped, would decide halting.
Worked example 5.3.7
(Emptiness)
The property is nontrivial: the empty language is recognizable, and is a different recognizable language. Rice's theorem says that deciding whether is impossible. Its complementary property, nonemptiness, is also undecidable, although nonemptiness is recognizable by dovetailing simulations over all inputs and accepting when some run accepts.
Worked example 5.3.8
(Finiteness)
“ is finite” is a nontrivial semantic property. The empty language is finite and recognizable, whereas is infinite and recognizable because the alphabet is nonempty. Therefore no decider can determine finiteness from an arbitrary recognizer's code. A machine with finitely many states as part of its description can still accept an infinite language; code size and language size are different notions.
Worked example 5.3.9
(Regularity of the recognized language)
The empty language is regular and recognizable. The language is recognizable but not regular by the pumping-lemma argument in the regular-languages chapter. Thus regularity is a nontrivial property of recognizable languages and is undecidable for arbitrary Turing-machine descriptions. This does not contradict efficient regularity-related algorithms for inputs already promised to be DFAs.
Worked example 5.3.10
(A syntactic question is different)
“Does the encoded machine have exactly three states?” can be answered by parsing a valid finite description and counting states. It is not a semantic language property: two machines with the same accepted language can have different numbers of unreachable or redundant states. Rice's theorem does not apply to this syntactic question.
What the theorem does and does not say
The input class matters. Rice's theorem ranges over arbitrary encoded recognizers, including machines that may run forever. If inputs are restricted to a representation with stronger promises, a particular property can be decidable. For example, DFA emptiness is decidable by graph reachability, even though emptiness of an arbitrary Turing-recognizable language is undecidable.
The property must depend only on . Whether a particular machine halts within a fixed number of steps on a fixed input is decidable by bounded simulation, but it can differ between two machines accepting the same language. It is not a counterexample to Rice's theorem because it is not a property of the accepted language alone.
Common mistake
(Undecidable does not mean unrecognizable)
The theorem proves undecidability, not automatically nonrecognizability of both answers. The set of machine encodings with nonempty language is recognizable: enumerate input words, interleave finite prefixes of the machine's computations, and accept as soon as one accepts. It is nevertheless undecidable. To decide whether the yes or no side of another property is recognizable, a separate argument is needed.
Counterexample mode
Not every nontrivial question about machines is undecidable
A tempting overreading of Rice's theorem is that every nontrivial yes/no question about encoded machines is undecidable. Consider “does the machine have exactly three states?” It is nontrivial, since some machines have three states and others do not, yet it is decidable: parse the finite description and count. Concretely, let have exactly three states and no transition into its accepting state, so . Let be with one unreachable extra state, so as well. The answer is yes for and no for , although they accept the same language. The question is therefore not a property of the accepted language alone, which is exactly the hypothesis Rice's theorem needs.
Following the reduction direction
Common mistake
(Reducing in the wrong direction)
The reduction begins with an arbitrary instance of the already undecidable halting problem and turns it into one instance of the property problem. If a property decider existed, feeding it the constructed instance would solve the original halting question. This direction is essential: reducing the property problem to halting would only show how a hypothetical halting oracle could help with the property, not that a property decider could solve halting.
The construction also uses a fixed reference recognizer rather than a fixed reference input. When the simulated halting instance stops, the new machine must reproduce the behavior of on whichever input it was given. For each such , the initial simulation takes a finite number of steps independent of whether eventually accepts, rejects or runs forever on . Therefore the set of accepted inputs is exactly , not merely a subset of .
When the halting simulation does not stop, the new machine runs forever on every input. This behavior is allowed for a recognizer. A proof that required the constructed machine to halt on every input would need an additional argument and cannot simply reuse this waiting construction. The theorem as stated concerns unrestricted Turing-machine recognizers, and the distinction explains why the input-class hypothesis is substantive.
For nonemptiness, dovetailing can be made explicit. Enumerate all finite input words as . At stage , simulate the machine on each of for steps, restarting or retaining configurations as convenient. If any run accepts, accept the machine encoding. Every fixed input and every fixed finite number of its simulation steps are eventually reached. If no input is accepted, the procedure runs forever, which is permitted for recognition but not for a decision procedure.
Understanding nontriviality
Nontriviality is relative to recognizable languages over the fixed alphabet. A property true of every recognizable language is decidable by always answering yes; one true of none is decidable by always answering no. Rice's theorem excludes both trivial cases. The witness languages used in a proof need not be hard to recognize; simple languages such as , and often suffice.
For a property like regularity, one witness must be a recognizable language that is not regular. It is not enough to name an arbitrary nonregular set without showing it is recognizable. The language is decidable by checking the block order and comparing the two counts, so it is a valid witness. Its nonregularity is a separate fact proved by the pumping lemma.
In the reduction, the reference machine is fixed once the property is fixed. The construction is allowed to include that finite machine description. It is not given an arbitrary description of the property as input and does not need to compute a witness from such a description. This distinction keeps the effective transformation from to precise.
Summary
A semantic property depends only on the accepted language. If it is nontrivial, a constructed recognizer can switch between the empty language and a fixed witness language depending on a halting computation. A decider for the property would therefore decide halting. Trivial properties, syntactic machine features and restricted representation classes fall outside the theorem's hypotheses.
Exercises
Quick check
(Explain why the property “contains the word ” is nontrivial and undecidable for arbitrary Turing-machine recognizers.)
Find two recognizable languages, one with the word and one without it.
Solution · Answer
The empty language lacks , while contains it; both are recognizable. Membership of depends only on the accepted language, so Rice's theorem makes the property undecidable.
Quick check
(Is the property “the accepted language equals ” covered by Rice's theorem? Give witnesses for nontriviality.)
Check both hypotheses: nontriviality and dependence on the language alone.
Solution · Answer
Yes. is recognizable and satisfies the property, while is recognizable and does not. Equality with depends only on the language, so the property is nontrivial and semantic.
Quick check
(Explain why “the machine accepts within 100 steps” is not a semantic property of the recognized language.)
Look for two machines with the same language but different running times.
Solution · Answer
One machine can accept immediately, while another performs 101 dummy steps before accepting it; they can otherwise recognize the same language. The bounded-time answers differ even though their accepted languages agree. The bounded simulation itself is decidable.
Quick check
(For the nonemptiness property, describe a recognizer for its yes instances and explain why Rice's theorem still applies.)
Which procedure can search all inputs at once?
Solution · Answer
Enumerate all input words and dovetail the encoded machine's simulations on them, running an increasing finite number of steps. Accept if any simulation accepts. If the language is nonempty, some accepting run is eventually found; if it is empty, the procedure may run forever. The property is nontrivial and semantic, so it is undecidable despite having recognizable yes instances.