|
Contents
Rice's theorem
Rice's theorem is an important result in the theory of recursive functions. A property of partial functions is trivial if it holds for all partial recursive functions, or for none.
Rice's theorem states that for any non-trivial property of partial functions, the question of whether a given algorithm computes a partial function with this property is undecidable.
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 non-trivial, since there are partial functions which are defined for 1 and others which are undefined at 1. The 1-halting 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 1-halting 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 Fa. 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 Fa. 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 P(b) = "yes". We can then define an algorithm H(a, i) as follows:
- (1) construct a string t that represents an algorithm T(d) such that
- T first simulates the computation of Fa(i)
- then T simulates the computation of Fb(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 Ft = Fb and because P(b) = "yes" and the output of P(x) only depends Fx, 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 Ft = Fno-halt, i.e., the partial function that is never defined. Since P(no-halt) = "no" and the output of P(x) only depends Fx, 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 function represented by a must be false.
| Elsewhere |  | |
Search engine
Web directory
|
CONTENTS:
|
