Rice's Theorem for GATE: The Mechanical Test for Undecidability Questions

Undecidability questions feel as if each one demands a fresh reduction from the halting problem. A large family of them does not. Rice's theorem turns properties of a Turing machine's accepted language into a two-part check.

The method is quick, but only when you separate a language property from a property of the machine's description or execution. That distinction is where the exam sets its traps.

Rice's theorem in exam-ready language

Rice's theorem says that every non-trivial semantic property of the language recognised by a Turing machine is undecidable.

In practical terms, ask:

1. Is the yes or no question about L(M), the set of strings accepted by M?

2. Is the property true for at least one recursively enumerable language and false for at least one other?

If both answers are yes, the property is undecidable. The theorem's proof already carries the reduction burden, so an application question does not require you to rebuild a reduction.

Rice gives a decidability verdict. It does not by itself say whether the set of yes-instances is recursively enumerable (RE), co-RE, or neither. That is a separate classification.

The semantic and non-trivial checklist

A property is semantic when it depends only on the language accepted. If two different machines accept exactly the same language, they must receive the same answer. Regularity, finiteness and emptiness are semantic because they describe L(M).

A property is syntactic when it depends on the machine representation. Number of states, presence of a particular transition, or whether a state is named q5 can differ between two machines accepting the same language.

A semantic property is non-trivial when some TM language has it and another TM language does not. For example, regularity is true for Sigma* and false for {a^n b^n : n >= 0}. A property true for every TM language, such as "is RE", is trivial. Its answer is the same for every valid encoding.

The full rule is:

semantic AND non-trivial implies undecidable.

If either check fails, Rice is silent. Silence does not mean decidable. It means you need direct inspection, simulation or a different undecidability reduction.

Six properties routed through the checklist

Keep four witnesses available:

• M0 accepts no strings, so L(M0) = empty set.

• M1 accepts every string, so L(M1) = Sigma*, which is regular, infinite and non-empty.

• M2 accepts {a^n b^n : n >= 0}, which is non-regular, infinite and non-empty.

• M3 accepts only epsilon, so its language is finite.

Now classify six statements.

1. L(M) = empty set. This is semantic. It is non-trivial because M0 has the property and M1 does not. Rice says undecidable.

2. L(M) is regular. This is semantic. M1 supplies a regular language and M2 supplies a non-regular language. Rice says undecidable.

3. L(M) is finite. This is semantic. M3 has a finite language, while M1 has an infinite one. Rice says undecidable.

4. L(M) is recursively enumerable. This is semantic but trivial. Every language accepted by a TM is RE by definition. The answer is always yes, so this property of valid TM descriptions is decidable by a constant answer.

5. M has exactly five states. This is not semantic. Equivalent machines may have different state counts. Rice does not apply, but the question is decidable because an algorithm can count the states in the encoding.

6. M halts on input epsilon. This concerns a particular run, not merely the accepted language. Two machines can accept the same language while one loops on epsilon and the other halts and rejects it. Rice is silent. The property is still undecidable, established through a halting-problem reduction.

This is mechanical only if you name the witnesses. Saying "non-trivial" without exhibiting one true case and one false case leaves room for a silent mistake.

When Rice's theorem does not apply

The syntactic trap asks about the machine rather than its language: number of states, whether it ever writes a blank, or whether a given transition exists. Some such questions are decidable by reading the encoding. Others involving unbounded execution may be undecidable by a different argument.

The run-behaviour trap asks whether M halts on a particular input or enters a state during a computation. These are not determined by the accepted language, so Rice is not the named theorem to use.

Be careful with one related distinction: "M accepts epsilon" is semantic, because it is exactly the property epsilon belongs to L(M). It is non-trivial, so Rice does apply and makes it undecidable. "M halts on epsilon" is not semantic, because halting and rejecting differs from looping even though neither run accepts epsilon. This one-word change is a strong exam trap.

Finally, test "always" and "never" claims. Every TM language is RE, so "L(M) is RE" is always true and "L(M) is not RE" is always false. Both are trivial constant properties, not Rice-undecidable properties.

RE versus non-RE after the Rice verdict

Rice says that a non-trivial semantic property is undecidable. GATE may ask the finer question: can yes-instances at least be recognised?

For non-emptiness, the answer is yes. Dovetail simulations of M over all strings. If any computation accepts, accept the encoded machine. A finite accepting computation is a witness, so {<M> | L(M) is non-empty} is RE.

For emptiness, there is no finite simulation point that confirms M will never accept any string. The language {<M> | L(M) is empty} is not RE. This pairs one RE property with its non-RE complement and shows why "undecidable" alone is not the final classification.

Rice-Shapiro generalises the finite-witness idea: a semantic property has RE yes-instances only when some finite set of accepted strings already forces the yes. Non-emptiness passes that test and emptiness fails it. Finiteness fails it in both directions, because no finite subset can certify that the whole language is infinite, and the empty subset would certify every language as finite. So {<M> | L(M) is finite} is neither RE nor co-RE. Fall back on Turing Machines and Decidability for the recursive versus recursively enumerable groundwork when the options distinguish RE, co-RE and neither.

How GATE tests Rice's theorem

One format lists several properties and asks which are undecidable. Run the two checks separately for every option. Another asks for decidable, RE or non-RE, where you must combine Rice with a recognisability argument. A third mixes one structural property among language properties to catch automatic use of the theorem.

Syllabus wording and topic weightage change with the organising IIT, so confirm both on the official GATE portal for your cycle rather than trusting a fixed marks figure quoted elsewhere.

KnowledgeGate's Theory of Computation bank runs past a thousand questions, with the Turing machine and complexity sections holding the decidability and reduction problems. Pair the checklist with Regular Expressions and the Pumping Lemma to keep language-class questions separate from machine-property questions.

The short version and next step

Semantic plus non-trivial means undecidable. A machine-description or run property makes Rice silent. A property true for every TM language or false for every TM language is trivial and has a constant answer.

Build the reduction proofs behind the shortcut in GATE Guidance by Sanchit Sir, then use the GATE category to continue the Theory of Computation track. On each practice statement, write S for semantic and N for non-trivial before choosing an option.