Coursify

Rice’s Theorem: Short Note with an Application

Rice’s Theorem: Short Note with an Application

Verified Sources
Nov 1, 2026

Rice’s theorem is a foundational result in computability theory stating that there is no general algorithm to decide interesting properties of the language recognized by an arbitrary Turing machine. In particular, if a property depends only on the recognized language (not on the machine’s syntactic description), and the property is neither always true nor always false, then the problem of deciding that property is undecidable. 2

Key idea: if we could decide such a property, we could decide the halting problem (or an equivalent undecidable problem) by reducing it to the property, contradicting known undecidability. 2

Footnotes

  1. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩ ↩2

  2. Lecture 16: Post’s Correspondence Problem and Rice's Theorem (Georgia Tech) - Statement of Rice’s theorem; semantic vs syntactic; proof outline. ↩ ↩2

Rice's Theorem (Undecidability): 5 Proofs and Examples

What Rice’s theorem is actually about (semantic properties)

Rice’s theorem applies to language properties (semantic properties), i.e., properties PP of the form: “L(M)L(M) has property PP,” where L(M)L(M) is the language recognized by machine MM. The property must satisfy:

  1. Non-triviality: some Turing-recognizable languages have the property and some do not. 2
  2. Semantic dependence: if L(M1)=L(M2)L(M_1)=L(M_2) then M1M_1 and M2M_2 either both satisfy the property or both fail it. 2

Syntactic properties (about the code/structure of the machine, like “MM has exactly 17 states”) are a different class and are not covered by Rice’s theorem.

Footnotes

  1. Lecture 16: Post’s Correspondence Problem and Rice's Theorem (Georgia Tech) - Statement of Rice’s theorem; semantic vs syntactic; proof outline. ↩ ↩2

  2. Rice's Theorem (Grinnell CSC 341 PDF) - Non-trivial vs trivial properties; alternative application framing. ↩

  3. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩ ↩2

Formal statement (index set form)

Let PP be a non-trivial semantic property of recursively enumerable languages. Define the associated decision problem:

LP=⟨Mrangle,mid,L(M)inP.L_P = \\{\langle M\\rangle \\,\\mid\\, L(M) \\in P\\}.

Rice’s theorem says that LPL_P is undecidable whenever PP is non-trivial. 2

Footnotes

  1. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩

  2. Lecture 16: Post’s Correspondence Problem and Rice's Theorem (Georgia Tech) - Statement of Rice’s theorem; semantic vs syntactic; proof outline. ↩

type="tip" title="Pro Tip: How to use Rice’s theorem" content="To apply Rice’s theorem, you usually (i) define the property PP on languages, then (ii) prove it’s non-trivial by exhibiting two machines whose languages differ on the property, and (iii) argue the property depends only on L(M)L(M) (semantic dependence). 2"

Footnotes

  1. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩

  2. Lecture 16: Post’s Correspondence Problem and Rice's Theorem (Georgia Tech) - Statement of Rice’s theorem; semantic vs syntactic; proof outline. ↩

Template proof when applying Rice’s theorem

  1. 1
    Step 1

    Specify the property in terms of the recognized language L(M)L(M) (e.g., empty, infinite, finite, contains a specific string).

  2. 2
    Step 2

    Prove that if L(M1)=L(M2)L(M_1)=L(M_2) then either both satisfy the property or both do not.

  3. 3
    Step 3

    Find one machine MyesM_{yes} such that L(Myes)∈PL(M_{yes})\in P and another MnoM_{no} such that L(Mno) otinPL(M_{no})\ otin P.

  4. 4
    Step 4

    Since PP is non-trivial and semantic, Rice’s theorem implies {⟨M⟩∣L(M)∈P}\{\langle M\rangle\mid L(M)\in P\} is undecidable. 2

    Footnotes

    1. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩

    2. Lecture 16: Post’s Correspondence Problem and Rice's Theorem (Georgia Tech) - Statement of Rice’s theorem; semantic vs syntactic; proof outline. ↩

Visualizing the logic

Rice’s theorem is essentially an “all-or-nothing” statement for non-trivial semantic questions about recognized languages.

Application: Undecidability of emptiness of a recognized language

Consider the classical emptiness problem for Turing machines:

[ETM]{def="Set of TM descriptions such that L(M)=∅"}

ETM=langleMranglemidL(M)=emptyset.ETM = \\{\\langle M\\rangle \\mid L(M)=\\emptyset\\}.

Why Rice’s theorem applies

Define a property PP on languages by:

  • P(L)P(L) holds iff L=emptysetL=\\emptyset.

This property is:

  1. Semantic: if L(M1)=L(M2)L(M_1)=L(M_2), then either both are empty or both are not empty.
  2. Non-trivial:
    • There exists a Turing machine M_\\emptyset with L(M_\\emptyset)=\\emptyset (e.g., a machine that never accepts).
    • There exists a Turing machine M_\\epsilon with L(M_\\epsilon)=\\{\\epsilon\\} (accepting exactly the empty string), so L(M_\\epsilon)\\neq\\emptyset.

By Rice’s theorem, ETMETM is undecidable. 2

Footnotes

  1. Rice's Theorem (Grinnell CSC 341 PDF) - Application example proving emptiness problem undecidable via Rice. ↩ ↩2 ↩3 ↩4 ↩5

  2. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩

type="warning" title="Common mistake" content="Rice’s theorem does NOT apply to syntactic properties of the machine (e.g., number of states). It applies to properties that depend only on the recognized language L(M)L(M). 2"

Footnotes

  1. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩

  2. 1 Rice's Theorem (Illinois CS 373 Lecture PDF) - Distinguishes properties of TMs vs properties of languages; lists undecidable language properties. ↩

Another application (quick): “Language is infinite”

Let P(L)P(L) mean “LL is infinite.” This is a semantic property of L(M)L(M). It is also non-trivial because there are recognizable languages that are infinite (e.g., 0n:nge0\\{0^n:n\\ge 0\\}) and recognizable languages that are finite (e.g., emptyset\\emptyset or epsilon\\{\\epsilon\\}). Therefore, by Rice’s theorem, the index set

langleMranglemidL(M)textisinfinite\\{\\langle M\\rangle \\mid L(M) \\text{ is infinite}\\}

is undecidable. 2

Footnotes

  1. Rice's Theorem (Grinnell CSC 341 PDF) - Non-trivial vs trivial properties; alternative application framing. ↩

  2. 6.045J Lecture 9: Mapping reducibility and Rice's theorem (MIT OCW) - Examples and interpretation of Rice’s theorem for language properties. ↩

How Rice’s theorem fits into undecidability proofs

Choose a semantic question

1) Define property

Turn the informal requirement into a property PP of languages."

Verify language-only dependence

2) Check semantics

Show the property depends only on L(M)L(M)."

Exhibit yes/no witnesses

3) Check non-triviality

Produce machines whose languages differ on the property."

Conclude undecidability

4) Apply theorem

Rice’s theorem yields undecidability of the associated index set."

Rice’s theorem quick-check flashcards

1 / 5
Question · Term

What kind of properties does Rice’s theorem handle?

Click to reveal
Answer · Definition

Non-trivial semantic (language) properties of Turing-recognizable languages; i.e., depends only on L(M)L(M). 2

Footnotes

  1. Rice's theorem - Wikipedia - Formal statement and discussion of semantic/non-trivial properties. ↩

  2. Lecture 16: Post’s Correspondence Problem and Rice's Theorem (Georgia Tech) - Statement of Rice’s theorem; semantic vs syntactic; proof outline. ↩

Knowledge Check

Question 1 of 4
Q1Single choice

Rice’s theorem applies to which type of property?

Explore Related Topics

1

Knowledge: Short Notes with a Clear Conceptual Framework

2

Minimization of Automata

3

Topological Sorting (Write Short Notes)

Browse all research articles