Rice’s theorem

Rice’s theorem states that it’s not possible to compute the index set \(A\) that corresponds to a certain class \(\mathcal F\) of partial computable functions if this index set is not trivial (i.e. there are elements in the set but there are also elements that are not in the set).

Proof

Let’s say that \(A\) is the index set of the given class of functions \(\mathcal F\) and that \(a\in A\) and \(b\notin A\). If \(A\) is computable then the characteristic function \(\chi_A\) is computable as well. It follows that the function \[ f(n) = b\chi_A(n) + a(1-\chi_A(n))\] is also computable and total and therefore has a fixed point \(s\) (i.e.: \( \varphi_{f(s)} = \varphi_s\)).

Using this it’s possible to obtain the following contradiction.

\[ \varphi_s \in \mathcal F \iff \varphi_{f(s)} \in \mathcal F \iff f(s) = a \iff s \notin A \iff \varphi_s \notin \mathcal F \]

Remark: \(f(s) = a\) follows from the fact that \(f(x) = a \text{ or } b\) and it can’t be \(b\) if \(\varphi_{f(s)} \in \mathcal F\) as \(b \notin A \iff \varphi_b \notin \mathcal F\).

Applications

Indices of total functions are not computable

There is a function that is total and there’s another function that is not total. Therefore the index set of total functions is not trivial and therefore it’s not decidable whether the function corresponding to a given index is total.

The index set of any partial computable function is uncomputable and infinite

As not all functions are identical there is at least one index that is not in the set. The set can’t be empty either as every partial computability function has (at least) an index. Therefore the index set is uncomputable which implies that the index set of any function is a set of infinite size as every finite set is computable.