Quick and – somewhat – informal: Rice’s Theorem

Rice’s Theorem is a very powerful and yet easy to use tool in every Computer Scientists arsenal. It states Every non-trivial, semantic property of an algorithm is undecidable.

Reading this theorem begs the question: What exactly is a non-trivial property? This question is best answered by thinking of trivial properties because there are only two of them: (1) The algorithm halts for every input or (2) the algorithm halts for no input.

Have a look at the formal definition:
Let \(R\) be the set of semi-recursive (computable) functions and \(S\) be a non-empty, real subset of \(R\) such that \(S \subset R\), \(S \neq R\) and \(S \neq \emptyset\). Then, Rice’s Theorem states that
$$ L(S) = \{\langle M \rangle | M \text{ calculates } S \}$$
is not decidable. Here, \(M\) is a Turing Machine and \(L(S)\) the language of \(S\).

Now to the more useful part: If there is any question regarding a non-trivial property of \(M\), which calculates algorithm \(A\) it is sufficient to show that the calculated function \(S\) is indeed a true subset of \(R\) and that there is another function in \(R\) that does not calculate \(S\). The latter part is trivial to show by finding a counter example. For instance: Let \(U \subset R\) but \(u \in U\) calculates for some input \(x\) a result for which \(u(x) \neq s(x) \in S\). This already shows that \(R – S \neq \emptyset\).

After finding such a trivial counter example, Rice’s Theorem follows immediately and it is shown that \(L(S)\) is not decidable.

Common Examples for non-trivial properties:
(1) Given a TM \(M\), does \(M\) visit each of it’s states during the computation for an arbitrary input?
(2) Does TM \(M\) calculate function \(f\)?
(3) Will TM \(M\) halt on every input? (Halting Problem \(H\))
(4) Will TM \(M\) halt on the empty input \(\epsilon\)? (Special Halting Problem \(H_{\epsilon}\))

Further reading:
Rice’s Theorem on Wikipedia