Redirected from Rices theorem
As an example, consider the following variant of the halting problem: Take the property a partial function F has if F is defined for argument 1. It is obviously nontrivial, since there are partial functions which are defined for 1 and others which are undefined at 1. The 1halting problem is the problem of deciding of any algorithm whether it defines a function with this property, i.e., whether the algorithm halts on input 1. By Rice's theorem, the 1halting problem is undecidable.
Algorithms are presumed here to define partial functions over strings, and are themselves represented by strings. The partial function computed by the algorithm represented by a string a is denoted as F_{a}. This proof proceeds by reductio ad absurdum; we assume that there is a nontrivial 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 nontrivial property of F_{a}. Without loss of generality we may assume that P(nohalt) = "no" with nohalt 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 nontrivial property it follows that there is a string b that represents an algorithm and P(b) = "yes". We can then define an algorithm H(a, i) as follows:
We can now show that H decides the Halting problem:
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 nontrivial property for the function represented by a must be false.
Search Encyclopedia

Featured Article
