Rices theorem

Rice's theorem states that any non-trivial property of the function that is defined by an algorithm is undecidable, i.e., there is no algorithm that decides this property given a description of the algorithm. Here a trivial property is defined as a property that holds for all algorithms or for none.

Sketch of Proof

Algorithms are presumed here to define functions over strings. The function represented by a string a is denoted as F[a]. This proof proceeds by reductio ad absurdum; we assume that there is a non-trivial property that is decided by an algorithm, and then show that it follows that we can decide the Halting problem, which is not possible, and therefore a contradiction.

Let us now assume that P(a) is an algorithm that decides some non-trivial property of F[a]. Without loss of generality we may assume that P(no-halt) = "no" with no-halt the representation of an algorithm that never halts. If this is not the case then this will hold for the negation of the property. Since P decides a non-trivial property it follows that there is a string b that represents an algorithm and it holds that P(b) = "yes". We can then define an algorithm H(a, i) as follows:

• (1) construct a string t that defines an algorithm T(d) such that
  • T first simulates the computation of F[a](i)
  • then T simulates the computation of F[b](d) and returns its result.
• (2) return P(t)

We can now show that H decides the Halting problem:

• Assume that the algorithm represented by a halts on input i. In that case F[t] = F[b] and because P(b) = "yes" and P(a) decides a property of F[a], it follows that P(t) = "yes" and, therefore H(a, i) = "yes".
• Assume that the algorithm represented by a does not halt on input i. In that case F[t] = F[no-halt], i.e., the function that is never defined. Since P(empty) = "no" and P(a) decides a property of F[a], it follows that P(t) = "no" and, therefore, H(a, i) = "no".

Since the Halting problem is known to be undecidable this is a contradiction and the assumption that there is an algorithm P(a) that decides a non-trivial property for the algorithm represented by a, must be false.