Rice's theorem

The Rice's Theorem is a result of theoretical computer science . The phrase was named after Henry Gordon Rice , who published it in 1953. It says that it is impossible to algorithmically decide any non-trivial property of the generated function of a Turing machine (or an algorithm in another computability model ) .

For special classes of algorithms it is possible - also automatically - to prove individual properties. However, there is no general method that can determine for every algorithm whether the function described by it shows a desired behavior given in a common formal language .

sentence

Let it be the set of all partial Turing-computable functions and a non-empty, real subset of them. In addition, an effective numbering is assumed, which assigns the Turing machine coded thereby to a natural number . ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {S}}\subsetneq {\mathcal {P}}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle M_{n}}$

Then the amount cannot be decided . ${\displaystyle {\mathcal {C}}({\mathcal {S}})=\left\{n\mid {\text{die von }}M_{n}{\text{ berechnete Funktion liegt in }}{\mathcal {S}}\right\}}$

By construction, indices of equivalent Turing machines are either all in or all in complement . It is also said that describes a semantic property of Turing machines, a semantic set is called accordingly . ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$

Applications

For example, it follows from Rice's theorem that there is no algorithm that decides for every Turing machine whether or not it holds for every input. is the set of all totally calculable functions. ${\displaystyle {\mathcal {S}}={\mathcal {R}}}$

It is also impossible to decide whether a Turing machine calculates a given function . then only contains this one function. From this it follows that the problem of program equivalence cannot be decided. ${\displaystyle f\in {\mathcal {P}}}$ ${\displaystyle {\mathcal {S}}=\{f\}}$

Also, it cannot be decided whether the calculated function is injective , surjective , monotonic or constant .

Proof idea

The proof is a many-one reduction of the special holding problem to for anything non-trivial . It is sketched here by pseudocode . ${\displaystyle K}$ ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ ${\displaystyle {\mathcal {S}}}$

It is not trivial. We can assume without restriction that the function, which is undefined everywhere, is not in , otherwise we go to the complement. Let further be an arbitrary, firmly chosen function (here that is not trivial) that is calculated by the Turing machine . ${\displaystyle \emptyset \neq {\mathcal {S}}\subsetneq {\mathcal {P}}}$ ${\displaystyle \bot }$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle f\in {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle M_{f}}$

For any Turing machine, consider the following algorithm: ${\displaystyle M_{n}}$

Function : ${\displaystyle N_{n}(x)}$

simulate with input ${\displaystyle M_{n}}$ ${\displaystyle n}$

then simulate with input ${\displaystyle M_{f}}$ ${\displaystyle x}$

output

It has the following properties:

• The Gödel number of is calculable from . This is done through the function , i. H. ${\displaystyle N_{n}}$ ${\displaystyle n}$ ${\displaystyle g\in {\mathcal {P}}}$ ${\displaystyle \forall x:n\in \mathbb {N} \colon M_{g(n)}(x)=N_{n}(x)}$
• If terminated on the input , it calculates the same function as , i.e. straight and therefore a function . ${\displaystyle M_{n}}$ ${\displaystyle n}$ ${\displaystyle N_{n}}$ ${\displaystyle M_{f}}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {S}}}$
• Otherwise the function , which is undefined everywhere, calculates a function from the complement of . ${\displaystyle N_{n}}$ ${\displaystyle \bot }$ ${\displaystyle {\mathcal {S}}}$
• According to the assumption, the function calculated by is in if and only if the calculation of terminates. ${\displaystyle N_{n}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle M_{n}(n)}$

Now if by a Turing machine decidable, one would by Davor switching an algorithm finally arrive to an algorithm for solving the specific halting problem, more could have been for any natural number that keeps on if and when to have the output 1, ie finds that in lies. Since this is not possible, it can not be decidable. ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ ${\displaystyle M}$ ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle M_{n}}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle g(n)}$ ${\displaystyle g(n)}$ ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$

Analog for recursively enumerable properties

The recursively enumerable (r. A.) Semantic properties of Turing machines can be characterized in an analogous way . Let be a system of r. a. Amounts. Then is the index set ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {P}}(\mathbb {N} )}$

${\displaystyle {\mathcal {C}}({\mathcal {S}})=\left\{n\mid {\text{die von }}M_{n}{\text{ erkannte Menge liegt in }}{\mathcal {S}}\right\}}$

then even r. a. if there is a r. a. Set of god numbers of finite sets with the following property: ${\displaystyle {\mathcal {D}}}$

${\displaystyle \forall A\subseteq \mathbb {N} \colon A\in S\Leftrightarrow (A{\text{ rekursiv aufzählbar}}\ \land \ \exists D\subseteq _{\text{fin}}\mathbb {N} \colon (\#D\in {\mathcal {D}}\wedge D\subseteq A))}$

That is, contains exactly those recursively enumerable sets that have a finite subset whose Godel number is in . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle D}$ ${\displaystyle \#D}$ ${\displaystyle {\mathcal {D}}}$

It is easy to see that such a set can be enumerated recursively. You start the calculations of all Turing machines one after the other and at the same time an enumeration of . Whenever there is a Turing machine that has already output all elements of a finite set that has already been enumerated , one outputs . The fact that all other sets cannot be recursively enumerable can be shown, similar to Rice's theorem, by the unsolvability of the holding problem. ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle M_{n}}$ ${\displaystyle D}$ ${\displaystyle n}$

literature

• Hartley Rogers: Theory of recursive functions and effective computability . McGraw-Hill, 1967.

Individual evidence

1. ^ Henry Gordon Rice: Classes of recursively enumerable sets and their decision problems . In: Transactions of the American Mathematical Society . tape 74 , 1953, pp. 358-366 , doi : 10.2307 / 1990888 .
2. ↑ Rogers 1967, 324