Satz von Rice

mathematischer Satz

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.

Es sei   die Menge aller partiellen Turing-berechenbaren Funktionen und   eine nicht-leere, echte Teilmenge davon. Außerdem sei eine effektive Nummerierung vorausgesetzt, die einer natürlichen Zahl   die dadurch codierte Turing-Maschine   zuordnet.

Dann ist die Menge   nicht entscheidbar.

Nach Konstruktion liegen Indizes äquivalenter Turing-Maschinen entweder alle in   oder alle im Komplement. Man sagt auch, dass   eine semantische Eigenschaft von Turing-Maschinen beschreibt, entsprechend heißt   eine semantische Menge.

Anwendungen

Bearbeiten

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.   ist hierbei die Menge aller total berechenbaren Funktionen.

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

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

Beweisidee

Bearbeiten

Der Beweis ist eine Many-One-Reduktion des speziellen Halteproblems   auf   für beliebiges nicht-triviales  . Er wird hier durch Pseudocode skizziert.

Es sei   nicht-trivial. Wir können ohne Einschränkung annehmen, dass die überall undefinierte Funktion   nicht in   liegt, sonst gehe man zum Komplement über. Sei weiter   eine beliebige, fest gewählte Funktion (hier geht ein, dass   nicht-trivial ist), die durch die Turing-Maschine   berechnet werde.

Man betrachte für eine beliebige Turing-Maschine   den folgenden Algorithmus:

Funktion  :
simuliere   mit Eingabe  
simuliere anschließend   mit Eingabe  
Ausgabe

Er hat folgende Eigenschaften:

  • Die Gödelnummer von   ist aus   berechenbar. Dies geschehe durch die Funktion  , d. h.  
  • Falls   auf der Eingabe   terminiert, berechnet   dieselbe Funktion wie  , also gerade   und damit eine Funktion aus  .
  • Andernfalls berechnet   die überall undefinierte Funktion  , also gemäß obiger Annahme eine Funktion aus dem Komplement von  .
  • Nach Voraussetzung liegt also die von   berechnete Funktion genau dann in  , wenn die Berechnung von   terminiert.

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

Analogon für rekursiv aufzählbare Eigenschaften

Bearbeiten

Auf eine analoge Weise lassen sich die rekursiv aufzählbaren (r. a.) semantischen Eigenschaften von Turing-Maschinen charakterisieren.[2] Sei   ein System von r. a. Mengen. Dann ist die Indexmenge

 

genau dann selbst r. a., wenn es eine r. a. Menge   von Gödelnummern endlicher Mengen mit folgender Eigenschaft gibt:

 

Das heißt,   enthält genau die rekursiv aufzählbaren Mengen, die eine endliche Teilmenge   haben, deren Gödelnummer   in   liegt.

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

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

Einzelnachweise

Bearbeiten
  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