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. Er besagt, dass es unmöglich ist, irgendeinen nichttrivialen Aspekt des funktionalen Verhaltens einer Turingmaschine (oder eines Algorithmus in einem anderen Algorithmenmodell) algorithmisch zu entscheiden.

Es ist zwar teilweise möglich, eine Eigenschaft eines speziellen Algorithmus zu beweisen, und dies lässt sich auch automatisieren, doch lässt sich aufgrund des gödelschen Unvollständigkeitssatzes nicht jede Aussage über einen gegebenen Algorithmus beweisen oder widerlegen. Daher gibt es kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion eine gewünschte, in einer üblichen formalen Sprache gegebene Eigenschaft hat. Der Satz von Rice zeigt, dass es kein solches Entscheidungsverfahren auch für andere nichttriviale Eigenschaften gibt.

Formale Fassung

Es sei R die Menge aller Turing-berechenbaren Funktionen und S eine nichtleere, echte Teilmenge davon. Außerdem sei eine Kodierung vorausgesetzt, die einem Codewort w die dadurch codierte Turingmaschine $M_w$ zuordnet. Dann ist die Sprache

$C(S) = \left\{ w \mid \text{die von }M_w\text{ berechnete Funktion liegt in }S \right\}$

nicht entscheidbar.

Aus die von $M_w$ berechnete Funktion liegt in $S$ folgt, dass äquivalente Turingmaschinen entweder beide in $C(S)$ liegen oder keine von beiden. Man sagt auch, dass $S$ eine semantische Eigenschaft von Turingmaschinen ist.

Beispiele

Aus dem Satz von Rice folgt beispielsweise, dass es keinen Algorithmus gibt, der für jede Turingmaschine entscheidet, ob sie für jede Eingabe hält. S ist hierbei die Menge aller totalen (überall definierten) Funktionen.

Ebenso ist es nicht entscheidbar, ob eine Turingmaschine eine vorgegebene Funktion berechnet. S enthält dann nur diese eine Funktion. Daraus folgt, dass erst recht das Problem der Programmäquivalenz nicht entscheidbar ist.

Auch lässt es sich nicht entscheiden, ob die berechnete Funktion etwa injektiv, surjektiv oder monoton ist.

Beweisidee

Der Beweis arbeitet mit einer Reduktion des speziellen Halteproblems auf C(S) für ein beliebiges nicht triviales S. Er wird hier durch Pseudocode skizziert.

Es sei S eine nichttriviale Teilmenge von R. Da der Übergang zum Komplement keinen Unterschied für die Entscheidbarkeit macht, kann man ohne Beschränkung der Allgemeinheit annehmen, dass die überall undefinierte Funktion $\bot$ nicht in S enthalten ist. Sei f eine beliebige Funktion aus S. (An dieser Stelle geht ein, dass S nicht trivial ist.) Ferner werde f durch die Turingmaschine $M_f$ berechnet.

Nun betrachtet man für einen beliebigen Algorithmus $M_w$ den folgenden Algorithmus:

Funktion $N_w$(x):

simuliere $M_w$ mit Eingabe w

simuliere $M_f$ mit Eingabe x und gib das Ergebnis aus

Er hat folgende Eigenschaften:

• Der Übergang von $M_w$ zu $N_w$ ist berechenbar. Es gibt also eine berechenbare Funktion g, so dass $M_{g(w)}=N_w$ für alle w gilt.
• Falls $M_w$ bei Eingabe von w terminiert, berechnet $N_w$ dieselbe Funktion wie $M_f$, also f. Andernfalls berechnet $N_w$ die überall undefinierte Funktion $\bot$. Aufgrund der getroffenen Annahmen bedeutet das, dass die von $N_w$ berechnete Funktion genau dann in S liegt, wenn $M_w$ bei Eingabe von w terminiert.

Wenn es nun einen Algorithmus für die Sprache C(S) gäbe, so würde man durch Davorschalten eines Algorithmus für g zu einem Algorithmus zur Lösung des speziellen Halteproblems gelangen. Da dies nicht möglich ist, kann C(S) nicht entscheidbar sein.

Analogon für rekursiv aufzählbare Eigenschaften

Auf eine analoge Weise lassen sich die rekursiv aufzählbaren semantischen Eigenschaften von Turing-Maschinen charakterisieren. Sei $S$ eine Menge rekursiv aufzählbarer Mengen. Dann ist die Sprache

$C(S) = \left\{ w \mid \text{die von }M_w\text{ erkannte Menge liegt in }S \right\}$

genau dann rekursiv aufzählbar, wenn es eine rekursiv aufzählbare Menge $\mathcal{D}$ von Gödelnummern endlicher Mengen mit folgender Eigenschaft gibt: $S$ enthält genau die rekursiv aufzählbaren Mengen, die eine endliche Teilmenge $D$ haben, deren Gödelnummer $\#D$ in $\mathcal{D}$ liegt:

$A \in S \leftrightarrow (A \text{ rekursiv aufzählbar} \wedge \exists D (\#D \in \mathcal{D} \wedge D \subseteq A))$

Dass eine solche Menge $S$ rekursiv aufzählbar ist, ist leicht einzusehen. Man startet dazu nacheinander die Berechnungen aller Turingmaschinen und gleichzeitig eine Aufzählung von $\mathcal{D}$. Immer wenn es eine Turingmaschine $M_w$ gibt, die bereits alle Elemente einer schon aufgezählten endlichen Menge $D$ ausgegeben hat, gibt man $w$ 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.

Siehe auch

• Gödelscher Unvollständigkeitssatz

Literatur

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