Rice's theorem

The set of Rice is a result of theoretical computer science. It was named after Henry Gordon Set Rice, who published it in 1953. He says that it is impossible any non - trivial property of a Turing machine ( or algorithm predictability in another model) to decide algorithmically.

For special classes of algorithms, it is possible - even automated - detect single properties. However, there is no general method which can determine, for each algorithm, if the function described by it shows a desired, given in a usual formal language behavior.

Set

It is the set of all partial Turing computable functions and a non-empty, proper subset of them. In addition, an effective enumeration Assume that a natural number maps the encoded thereby Turing machine.

Then the amount is not decidable.

By construction indices are equivalent Turing machines either all in or all in the complement. It is also said that a semantic property of Turing machines describes accordingly called a semantic quantity.

Examples

From the set of Rice follows, for example, that there is no algorithm which decides for each Turing machine, if it holds for any input. here is the set of all total computable functions.

Likewise, it is not determinable whether a Turing machine calculates a predetermined function. then contains only this one function. It follows a fortiori that the problem of program equivalence is not decidable.

Also, it can not be decided whether the calculated function is approximately injective, surjective or monotonically.

Idea of ​​proof

The proof is a many -one reduction of the particular problem holding on for any non-trivial. It is outlined here by pseudocode.

It is non- trivial. O.B.d.A. is not everywhere undefined function. Let further arbitrary ( here is that non- trivial ). Furthermore, is calculated by the Turing machine.

Consider an arbitrary Turing machine, the following algorithm:

It has the following properties:

• The Gödel number of can be calculated from. This is being done by the function, that is,
• If terminated at the input, calculates the same function as (that is even).
• Otherwise, the everywhere undefined function computed ( this is required by different).
• By assumption, ie the ones computed function is present precisely in when calculating terminated.

Now if decidable by a Turing machine, we would end by Davor switching an algorithm for finally to an algorithm for solving the special halting problem. Since this is not possible, not be determinable.

Recursively enumerable properties for analogue

In an analogous way, the recursively enumerable (re) semantic properties of Turing machines characterize. Let a system of R. E. Quantities. Then the index set

If and R. E. yourself if there is a R. E. Set of Godel numbers of finite sets with the following property are:

That is exactly contains the recursively enumerable sets which have a finite subset whose Gödel number is in.

That such amount is recursively enumerable, is easy to see. You start sequence the calculations of all Turing machines and at the same time an enumeration of. Whenever there is a Turing machine that has already spent all the elements of a finite set already enumerated, are from you. That all other quantities can not be recursively enumerable, can be similar to the set of Rice by the insolubility of the halting problem show.