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
For every x, φp(x)↓ ⇔ φq(x)↓.
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.
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.
p ∈ S | ⇔ | φp(x)↓ for all x and (φp(x) = "yes" ⇔ x is prime) |
⇔ | φq(x)↓ for all x and (φq(x) = "yes" ⇔ x is prime) |
|
⇔ | q ∈ S |