Introduction

Let’s explore a powerful, sweeping result: Rice’s Theorem. Instead of tackling one weird undecidable problem at a time, Rice’s Theorem tells us that any nontrivial question about the language recognized by a Turing machine is undecidable. It’s like a Swiss army knife for proving undecidability.

Rice’s Theorem Statement

Informally:

Any nontrivial semantic property of the language recognized by Turing machines is undecidable.

More formally, let $P$ be a property of recursively enumerable languages, and suppose:

  1. Nontriviality: There exists at least one TM $M_1$ such that $L(M_1)$ has property $P$, and at least one TM $M_2$ such that $L(M_2)$ does not have $P$.
  2. Semantic: $P$ depends only on the language recognized, not on the machine’s syntax.

Then the decision problem:

$$ {\langle M \rangle \mid L(M) \text{ has property } P} $$

is undecidable.

Example Properties

Rice’s Theorem covers any property like:

  • “The language is empty.”
  • “The language is finite.”
  • “The language is regular/context-free.”
  • “The language contains at least one palindrome.”

All these are undecidable for TM languages (with trivial exceptions like the always-true/always-false properties).

Proof Sketch

  1. Reduction from the Halting Problem: Given $\langle M, w \rangle$, build a new machine $M’$ that:

    • On any input, simulates $M(w)$.
    • If $M(w)$ halts, simulates a fixed machine $M_1$ whose language has $P$.
    • If $M(w)$ doesn’t halt, simulates a fixed machine $M_2$ whose language does not have $P$.

  2. If you could decide whether $L(M’)$ has $P$, you’d decide if $M(w)$ halts.

  3. Contradiction, since the Halting Problem is undecidable.

Applications

  • Emptiness, Finiteness, Equivalence: We’ve seen these specific cases, but Rice’s Theorem gives a single stroke proof.
  • Properties like “Contains a prime number encoding”: You can encode any semantic question about the set of accepted strings.
  • Meta-theory: Explains why program analyzers that try to infer behaviors of programs run into undecidable roadblocks.

Wrap-Up

Rice’s Theorem is the grand finale of undecidability for TM languages: it shows that nearly every interesting question you ask about what a program computes is hopelessly unsolvable. Next, we’ll journey into the land of NP-completeness with the Boolean Satisfiability Problem (SAT)!