Satz von Rice

Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik. Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte.[1] Er besagt, dass es unmöglich ist, eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus in einem anderen Berechenbarkeitsmodell) algorithmisch zu entscheiden.

Für spezielle Klassen von Algorithmen ist es zwar möglich – auch automatisiert – einzelne Eigenschaften nachzuweisen. Es gibt jedoch kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion ein gewünschtes, in einer üblichen formalen Sprache gegebenes Verhalten zeigt.

Satz

Es sei ${\displaystyle {\mathcal {P}}}$ die Menge aller partiellen Turing-berechenbaren Funktionen und ${\displaystyle {\mathcal {S}}\subsetneq {\mathcal {P}}}$ eine nicht-leere, echte Teilmenge davon. Außerdem sei eine effektive Nummerierung vorausgesetzt, die einer natürlichen Zahl ${\displaystyle n\in \mathbb {N} }$ die dadurch codierte Turing-Maschine ${\displaystyle M_{n}}$ zuordnet.

Dann ist die Menge ${\displaystyle {\mathcal {C}}({\mathcal {S}})=\left\{n\mid {\text{die von }}M_{n}{\text{ berechnete Funktion liegt in }}{\mathcal {S}}\right\}}$ nicht entscheidbar.

Nach Konstruktion liegen Indizes äquivalenter Turing-Maschinen entweder alle in ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ oder alle im Komplement. Man sagt auch, dass ${\displaystyle {\mathcal {S}}}$ eine semantische Eigenschaft von Turing-Maschinen beschreibt, entsprechend heißt ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ eine semantische Menge.

Anwendungen

Aus dem Satz von Rice folgt beispielsweise, dass es keinen Algorithmus gibt, der für jede Turing-Maschine entscheidet, ob sie für jede Eingabe hält oder nicht. ${\displaystyle {\mathcal {S}}={\mathcal {R}}}$ ist hierbei die Menge aller total berechenbaren Funktionen.

Ebenso ist es nicht entscheidbar, ob eine Turing-Maschine eine vorgegebene Funktion ${\displaystyle f\in {\mathcal {P}}}$ berechnet. ${\displaystyle {\mathcal {S}}=\{f\}}$ enthält dann nur diese eine Funktion. Daraus folgt, dass erst recht das Problem der Programmäquivalenz nicht entscheidbar ist.

Auch lässt s​ich nicht entscheiden, o​b die berechnete Funktion e​twa injektiv, surjektiv, monoton o​der konstant ist.

Beweisidee

Der Beweis ist eine Many-One-Reduktion des speziellen Halteproblems ${\displaystyle K}$ auf ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ für beliebiges nicht-triviales ${\displaystyle {\mathcal {S}}}$. Er wird hier durch Pseudocode skizziert.

Es sei ${\displaystyle \emptyset \neq {\mathcal {S}}\subsetneq {\mathcal {P}}}$ nicht-trivial. Wir können ohne Einschränkung annehmen, dass die überall undefinierte Funktion ${\displaystyle \bot }$ nicht in ${\displaystyle {\mathcal {S}}}$ liegt, sonst gehe man zum Komplement über. Sei weiter ${\displaystyle f\in {\mathcal {S}}}$ eine beliebige, fest gewählte Funktion (hier geht ein, dass ${\displaystyle {\mathcal {S}}}$ nicht-trivial ist), die durch die Turing-Maschine ${\displaystyle M_{f}}$ berechnet werde.

Man betrachte für eine beliebige Turing-Maschine ${\displaystyle M_{n}}$ den folgenden Algorithmus:

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

simuliere ${\displaystyle M_{n}}$ mit Eingabe ${\displaystyle n}$

simuliere anschließend ${\displaystyle M_{f}}$ mit Eingabe ${\displaystyle x}$

Ausgabe

Er h​at folgende Eigenschaften:

• Die Gödelnummer von ${\displaystyle N_{n}}$ ist aus ${\displaystyle n}$ berechenbar. Dies geschehe durch die Funktion ${\displaystyle g\in {\mathcal {P}}}$, d. h. ${\displaystyle \forall x:n\in \mathbb {N} \colon M_{g(n)}(x)=N_{n}(x)}$
• Falls ${\displaystyle M_{n}}$ auf der Eingabe ${\displaystyle n}$ terminiert, berechnet ${\displaystyle N_{n}}$ dieselbe Funktion wie ${\displaystyle M_{f}}$, also gerade ${\displaystyle f}$ und damit eine Funktion aus ${\displaystyle {\mathcal {S}}}$.
• Andernfalls berechnet ${\displaystyle N_{n}}$ die überall undefinierte Funktion ${\displaystyle \bot }$, also gemäß obiger Annahme eine Funktion aus dem Komplement von ${\displaystyle {\mathcal {S}}}$.
• Nach Voraussetzung liegt also die von ${\displaystyle N_{n}}$ berechnete Funktion genau dann in ${\displaystyle {\mathcal {S}}}$, wenn die Berechnung von ${\displaystyle M_{n}(n)}$ terminiert.

Wäre nun ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ durch eine Turing-Maschine ${\displaystyle M}$ entscheidbar, so würde man durch Davorschalten eines Algorithmus für ${\displaystyle g}$ schließlich zu einem Algorithmus zur Lösung des speziellen Halteproblems gelangen, genauer hätte man für jede natürliche Zahl ${\displaystyle n}$, dass ${\displaystyle M_{n}}$ hält auf ${\displaystyle n}$ genau dann wenn ${\displaystyle M}$ auf ${\displaystyle g(n)}$ die Ausgabe 1 hat, das heißt feststellt, dass ${\displaystyle g(n)}$ in ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ liegt. Da dies nicht möglich ist, kann ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ nicht entscheidbar sein.

Analogon für rekursiv aufzählbare Eigenschaften

Auf eine analoge Weise lassen sich die rekursiv aufzählbaren (r. a.) semantischen Eigenschaften von Turing-Maschinen charakterisieren.[2] Sei ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {P}}(\mathbb {N} )}$ ein System von r. a. Mengen. Dann ist die Indexmenge

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

genau dann selbst r. a., wenn es eine r. a. Menge ${\displaystyle {\mathcal {D}}}$ von Gödelnummern endlicher Mengen mit folgender Eigenschaft gibt:

${\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))}$

Das heißt, ${\displaystyle {\mathcal {S}}}$ enthält genau die rekursiv aufzählbaren Mengen, die eine endliche Teilmenge ${\displaystyle D}$ haben, deren Gödelnummer ${\displaystyle \#D}$ in ${\displaystyle {\mathcal {D}}}$ liegt.

Dass eine solche Menge ${\displaystyle {\mathcal {C}}({\mathcal {S}})}$ rekursiv aufzählbar ist, ist leicht einzusehen. Man startet dazu nacheinander die Berechnungen aller Turingmaschinen und gleichzeitig eine Aufzählung von ${\displaystyle {\mathcal {D}}}$. Immer wenn es eine Turing-Maschine ${\displaystyle M_{n}}$ gibt, die bereits alle Elemente einer schon aufgezählten endlichen Menge ${\displaystyle D}$ ausgegeben hat, gibt man ${\displaystyle n}$ aus. Dass alle anderen Mengen nicht rekursiv aufzählbar sein können, lässt sich ähnlich dem Satz von Rice durch die Unlösbarkeit des Halteproblems zeigen.

Literatur

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

Einzelnachweise

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