Lektion 3.4

Reduktionen und der Satz von Rice

50 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • die Richtung einer berechenbaren many-one-Reduktion begründen,

  • semantische Spracheigenschaften von syntaktischen Codeeigenschaften unterscheiden,

  • Nichttrivialität anhand zweier erkennbarer Sprachen nachweisen,

  • beide Fälle im Beweis des Satzes von Rice führen und seine Grenzen benennen.

Vorausgesetzt: Turingmaschinen, Berechenbarkeit und die Church-Turing-These, Das Halteproblem und Unentscheidbarkeit

Das Halteproblem verbietet einen allgemeinen Algorithmus, der für jedes Programm und jede Eingabe zuverlässig über dessen Terminierung entscheidet. Aber vielleicht sind einfachere Fragen über das Ergebnisverhalten möglich: Nimmt ein Programm überhaupt irgendein Wort an? Erkennt es nur endlich viele Wörter? Ist seine erkannte Sprache regulär?

Der Satz von Rice zeigt, was diesen Fragen gemeinsam ist. Es geht um die erkannte Sprache, nicht um die Schreibweise des Programms. Sobald eine solche Eigenschaft bei manchen erkennbaren Sprachen gilt und bei anderen nicht, gibt es keinen allgemeinen Entscheider dafür. Den Zusammenhang stellen wir durch eine konkrete Übersetzung des Halteproblems her.

Definition

Berechenbare many-one-Reduktion

Seien A und B Entscheidungsprobleme, jeweils als Sprache über einem endlichen Alphabet codiert. Eine berechenbare many-one-Reduktion von A auf B ist eine totale berechenbare Funktion f, die jede Eingabe x in eine Eingabe f(x) übersetzt und Ja und Nein genau erhält. Total bedeutet: Die Übersetzung hält für jede Eingabe. Man schreibt A≤mBA\le_m B.

Die Funktion darf keine Antwort auf A voraussetzen. Sie darf lediglich ein neues Problemexemplar konstruieren. „Many-one“ bedeutet hier, dass eine Anfrage an B genügt; mehrere verschiedene Eingaben dürfen dabei dieselbe Ausgabe haben.

x∈A  ⟺  f(x)∈Bx\in A\iff f(x)\in B
Satz

Die Richtung des Widerspruchs

Gilt A≤mBA\le_m B und ist B entscheidbar, dann ist A entscheidbar. Ist A bereits als unentscheidbar bekannt, folgt also die Unentscheidbarkeit von B.

Definition

Semantische und nichttriviale Spracheigenschaft

Für eine Turingmaschine M bezeichnet L(M)L(M) die Menge ihrer akzeptierten Eingabewörter. Verwerfen und Endloslaufen tragen beide kein Wort zu L(M)L(M) bei. Eine semantische Spracheigenschaft hängt nur von dieser Menge ab: Haben zwei Maschinen dieselbe erkannte Sprache, müssen sie für die Eigenschaft dieselbe Antwort erhalten.

Eine Eigenschaft P nennen wir nichttrivial auf den erkennbaren Sprachen, wenn es eine Turingmaschine mit L(M)∈PL(M)\in P und eine andere mit L(M)∉PL(M)\notin P gibt. P wird dabei als Menge von Sprachen aufgefasst. Entscheidend ist nicht, ob man sich irgendeine Sprache außerhalb von P vorstellen kann: Beide Gegenbeispiele müssen durch Turingmaschinen erkennbar sein. Wir betrachten ein festes gemeinsames Eingabealphabet Σ={0,1}\Sigma=\{0,1\}.

Beispiel

Zwei Voraussetzungen einzeln prüfen

„Die erkannte Sprache ist leer“ ist semantisch. Eine Maschine, die jedes Wort verwirft, hat die Eigenschaft; eine Maschine, die nur 0 annimmt, hat sie nicht. Damit ist sie nichttrivial. Ebenso ist „Die erkannte Sprache ist endlich“ nichttrivial: ∅\varnothing ist endlich, Σ∗\Sigma^* ist unendlich; beide sind sogar entscheidbar.

„Die Maschine hat höchstens zehn Zustände“ ist dagegen eine Eigenschaft ihres endlichen Codes. Unbenutzte Zustände können ergänzt werden, ohne die erkannte Sprache zu ändern. Die Eigenschaft ist also nicht semantisch und lässt sich durch Zählen entscheiden. „Die erkannte Sprache ist erkennbar“ ist zwar semantisch, aber auf Turingmaschinen trivial: Jede dort auftretende Sprache ist schon per Definition erkennbar.

Kurz geprüft

Zwei Maschinen erkennen dieselbe Sprache. Eine hält auf jeder Eingabe, die andere läuft auf manchen nicht akzeptierten Eingaben endlos. Ist „hält auf jeder Eingabe“ eine Eigenschaft nur von L(M)?

Satz

Satz von Rice für erkannte Sprachen

Ist P eine semantische Eigenschaft, die auf den Turing-erkennbaren Sprachen nichttrivial ist, dann ist das folgende Indexproblem unentscheidbar. „Indexproblem“ heißt hier, dass die Eingabe ein Maschinencode ist und die Antwort von dessen erkannter Sprache abhängt. Wir verwenden eine feste effektive Codierung; nicht wohlgeformte Codes können erkannt und verworfen werden.

IP={⟨M⟩∣L(M)∈P}I_P=\{\langle M\rangle\mid L(M)\in P\}
Schritt für Schritt

Fall 1: Die leere Sprache liegt nicht in P

Wegen der Nichttrivialität gibt es eine feste Maschine T mit L(T)∈PL(T)\in P. T wird einmal für diese Eigenschaft gewählt und ist dann Teil der festen Übersetzung. Eingabe der Übersetzung ist ein beliebiges Halteproblemexemplar ⟨M,w⟩\langle M,w\rangle. Eine ungültige Paarkodierung wird auf den Code einer festen Maschine abgebildet, die nichts akzeptiert. Sie ist damit wie die ungültige Eingabe eine Nein-Instanz. Für gültige Paare wird N wie folgt gebaut:

  1. Schreibe den Code einer neuen Maschine N. Er enthält die Beschreibungen von M und T sowie das feste Wort w. Das ist eine endliche Textkonstruktion, die auf jeder Eingabe endet.

Schritt 1 von 4

Code erzeugen ist nicht Code ausführen

Die Übersetzung f

Code M und Wort w → fertiger Code N

Endliches Kopieren in ein festes Schema; M wird hier nicht simuliert.

Erst ein späterer Start von N auf Eingabe x führt Folgendes aus:

  1. Simuliere M auf dem gespeicherten Wort w.
  2. Falls M hält: Simuliere T auf x und übernimm dessen Akzeptanz.

M hält nichtDer zweite Teil wird nie erreicht.L(N) = ∅

M hältDer zweite Teil wird erreicht.L(N) = L(T)

Oben steht der immer endende Bau des Maschinencodes. Darunter steht das möglicherweise unendliche Verhalten der gebauten Maschine. Der hypothetische Entscheider erhält den fertigen Code, nicht das Ergebnis einer vorab ausgeführten Simulation.

Schritt für Schritt

Fall 2: Die leere Sprache liegt in P

Im zweiten Fall lässt sich die vorherige Konstruktion nicht unverändert als H≤mIPH\le_m I_P verwenden: Die leere Sprache wäre bereits eine Ja-Antwort. Betrachte stattdessen die Gegeneigenschaft Q auf den erkennbaren Sprachen.

  1. Q gilt genau dann, wenn P nicht gilt. Q ist wieder semantisch und nichttrivial. Die leere Sprache liegt nun nicht in Q.

Schritt 1 von 3
Beispiel

Enthält die erkannte Sprache das Wort 0?

Die Eigenschaft 0∈L(M)0\in L(M) ist semantisch und nichttrivial: Ein Verwerfer erkennt ∅\varnothing, ein geeigneter Entscheider erkennt {0}. Nach Rice ist die Frage für beliebige Maschinencodes unentscheidbar. Trotzdem lässt sie sich semi-entscheiden: Simuliere M auf 0 und bestätige die Eigenschaft, falls M akzeptiert. Bei fehlender Zugehörigkeit kann die Simulation endlos laufen.

Für den Beweis in Fall 1 könnte T hier genau das Wort 0 annehmen. Die gebaute Maschine N erkennt dann entweder {0} oder die leere Sprache. Schon zwischen diesen beiden sehr einfachen Sprachen zu unterscheiden wird unentscheidbar, wenn sie durch beliebige Turingmaschinen beschrieben werden.

Beispiel

Leerheit und Nichtleerheit brauchen verschiedene Erkennungsverfahren

Nichtleerheit lässt sich semi-entscheiden: Liste alle Binärwörter nach Länge auf. In Runde n simuliere die ersten n Wörter jeweils n Schritte und bestätige die Eigenschaft, sobald ein akzeptierender Lauf gefunden wird. Jedes angenommene Wort mit endlicher Laufzeit wird so irgendwann erreicht. Nur eine Eingabe nach der anderen unbegrenzt auszuführen wäre falsch, weil bereits die erste Simulation endlos laufen könnte.

Leerheit ist dagegen nicht semi-entscheidbar. Wären Leerheit und Nichtleerheit beide semi-entscheidbar, könnte man beide Erkennungsverfahren verzahnt laufen lassen. Genau eines würde schließlich bestätigen; das würde Leerheit entscheiden und Rice widersprechen. Das zeigt: Der Satz allein sagt „unentscheidbar“. Aussagen über Semi-Entscheidbarkeit brauchen zusätzliche Argumente.

Häufige Fehler

Unentscheidbar beweisen, indem die Übersetzung selbst endlos wartet

Eine angebliche Reduktion lautet: „Simuliere zunächst M auf w und gib nach dessen Halt den passenden neuen Maschinencode aus.“ Für manche Eingaben würde dann nie ein Zielcode entstehen.

Richtig ist

Eine many-one-Reduktion muss total sein. Sie schreibt sofort einen Code, dessen spätere Ausführung die Simulation enthält. Die mögliche Endlosschleife gehört zum Verhalten der konstruierten Maschine. Ebenso reicht es nicht, nur eine Richtung der Äquivalenz oder nur die Nichttrivialität zu prüfen. Erst Semantik, zwei erkennbare Gegenbeispiele und eine korrekte Übersetzung tragen den Schluss.

Zusammenfassung

  • A≤mBA\le_m B übersetzt jedes A-Exemplar in endlicher Zeit und erhält Ja und Nein. Ein B-Entscheider ergäbe einen A-Entscheider.

  • Eine semantische Spracheigenschaft hängt nur von L(M) ab; gleiche erkannte Sprache bedeutet gleiche Antwort.

  • Nichttrivialität verlangt eine erkennbare Sprache mit und eine erkennbare Sprache ohne die Eigenschaft.

  • Rice: Jede solche nichttriviale Spracheigenschaft ist für beliebige Turingmaschinencodes unentscheidbar.

  • Der Beweis trennt die leere Sprache von einer festen Zeugen-Sprache. Falls nötig wird die Eigenschaft umgekehrt.

  • Codeerzeugung hält immer; die erzeugte Maschine darf später endlos laufen.

  • Unentscheidbarkeit ist weder eine Aussage über alle Codeeigenschaften noch automatisch über Semi-Entscheidbarkeit oder eingeschränkte Maschinenmodelle.

Übungen

Aufgabe 1Multiple Choice

A ist unentscheidbar. Welche zusätzliche Aussage beweist, dass B unentscheidbar ist?

Aufgabe 2Multiple Choice

Welche Frage erfüllt die Voraussetzungen des Satzes von Rice für erkannte Sprachen?

Aufgabe 3Freitext

Wende Rice auf „L(M) ist regulär“ an. Welche zwei Zeugen-Sprachen passen über dem Alphabet {0,1}?

Aufgabe 4Multiple Choice

Im ersten Beweisfall hält M auf w und verwirft. Welche Sprache erkennt die gebaute Maschine N?

Aufgabe 5Freitext

Warum ist die Funktion, die den Code N erzeugt, total, obwohl N selbst auf manchen Eingaben nie hält?

Aufgabe 6Freitext

Erkläre, weshalb eine semantische Eigenschaft „erkennt eine entscheidbare Sprache“ nicht dasselbe ist wie „hält auf allen Eingaben“.

Aufgabe 7Freitext

Beschreibe einen Semi-Entscheider für Nichtleerheit und begründe, warum eine unbegrenzte Simulation der Wörter nacheinander nicht genügt.

Aufgabe 8Multiple Choice

Ein Werkzeug analysiert beliebige Programme, meldet bei manchen „bewiesen sicher“ und bei anderen „unbekannt“. Widerlegt seine Existenz Rice?