# 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}$$)