17.11 Rice's Theorem

Rice's theorem offers an easy way to prove that certain kinds of problems are not computable. It only works for sets of programs or machine descriptions.

A set S of strings over alphabet A is nontrivial if S ≠ ∅ and S ≠ A^*.

Two programs p and q are equivalent if

1. For every x, φ_p(x)↓ ⇔ φ_q(x)↓.

2. For every x, if φ_p(x)↓ then φ_p(x) = φ_q(x).

Let S be a set of programs. Say that S respects equivalence if, for any two equivalent programs p and q, p ∈ S ⇔ q ∈ S.

Rice's theorem says that every nontrivial set of programs that respects equivalence is uncomputable.

Proving that S respects equivalence

---

One thing to remember when proving that a set S respects equivalence is that you are proving a property of S, not of programs. So do not try to prove that two programs are equivalent.

Suppose

S = {p | φ_p(x)↓ for all x and
    φ_p(x) = "yes" if and only if x is a prime number}.

Then S respects equivalence, for the following reason. Suppose that p and q are equivalent programs.