Satz von Rice

aus Wikipedia, der freien Enzyklopädie

Beim Satz von Rice handelt es sich um ein Ergebnis der Theoretischen Informatik. Benannt wurde der Satz nach Henry Gordon Rice. Er besagt, dass es unmöglich ist, irgendeinen nichttrivialen Aspekt des funktionalen Verhaltens einer Turingmaschine (oder eines Algorithmus in einem anderen Algorithmenmodell) algorithmisch zu überprüfen.

Es ist zwar möglich, eine Eigenschaft eines speziellen Algorithmus zu beweisen, und dies lässt sich auch automatisieren, doch es gibt kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion eine gewünschte Eigenschaft hat.

[Bearbeiten] Formale Fassung

Es sei R die Klasse aller Turing-berechenbaren Funktionen und S eine beliebige nichttriviale (das bedeutet S ≠ ø und S ≠ R) Teilmenge davon. Außerdem ist eine Codierung, die einem Codewort w die dadurch codierte Turingmaschine M_w zuordnet, vorausgesetzt. Dann ist die Sprache

C(S) = { w | die von M_w berechnete Funktion liegt in S }

unentscheidbar.

[Bearbeiten] 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.

[Bearbeiten] Beweisidee

Der Beweis arbeitet mit einer Reduktion des speziellen Halteproblems auf C(S) für 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 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:

function 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 . 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 Halteproblem gelangen. Da dies nicht möglich ist, kann C(S) nicht entscheidbar sein.