Berechenbarkeit und die Church-Turing-These
Lesen anpassen
Nach dieser Lektion kannst du
entscheidbare und semi-entscheidbare Sprachen unterscheiden und Beispiele nennen,
WHILE-Programme lesen und erklären, warum verschiedene Rechnermodelle dieselben Funktionen berechnen,
sagen, was die Church-Turing-These behauptet und warum sie sich nicht beweisen lässt,
Turingmaschinen als Wörter kodieren und die Idee der universellen Turingmaschine erklären,
mit Cantors Diagonalargument beweisen, dass es Sprachen gibt, die keine Turingmaschine erkennt.
Vorausgesetzt: Turingmaschinen
David Hilbert stellte 1928 eine Frage, die als "Entscheidungsproblem" bekannt wurde: Gibt es ein mechanisches Verfahren, das für jede Formel der Prädikatenlogik entscheidet, ob sie allgemeingültig ist? Wer mit "ja" antworten will, muss nur ein Verfahren vorführen. Wer mit "nein" antworten will, hat ein viel schwereres Problem: Er muss zeigen, dass kein Verfahren funktioniert, und dafür muss er erst genau sagen, was ein Verfahren überhaupt ist.
1936 gaben Alonzo Church (mit dem -Kalkül) und Alan Turing (mit seiner Maschine) zwei solche Präzisierungen an und bewiesen damit, dass die Antwort auf Hilberts Frage "nein" ist. Die beiden Modelle sehen völlig verschieden aus, berechnen aber genau dasselbe. Und es muss Probleme geben, die keines davon löst.
Jede Turingmaschine lässt sich als endlicher Text aufschreiben. Eine Sprache über ist eine beliebige Menge von Wörtern. Gibt es mehr Sprachen als Turingmaschinen?
Berechenbare Funktion
Eine partielle Funktion muss nicht für jedes Argument definiert sein. Sie heißt (Turing-)berechenbar, wenn es eine Turingmaschine gibt mit:
- Ist definiert, hält auf in , und auf dem Band steht , sonst nur Blanks.
- Ist nicht definiert, hält auf nicht.
Funktionen auf natürlichen Zahlen behandelt man über die Binärdarstellung. Beispiel: Die Maschine "Binärzahl plus 1" aus der letzten Lektion berechnet . Die Maschine, die in einem Zustand für immer stehen bleibt, berechnet die nirgends definierte Funktion.
Entscheidbar und semi-entscheidbar
Sei eine Sprache.
- heißt entscheidbar, wenn es eine Turingmaschine gibt, die auf jeder Eingabe hält, jedes akzeptiert und jedes verwirft. Sie heißt Entscheider für .
- heißt semi-entscheidbar oder rekursiv aufzählbar, wenn es eine Turingmaschine mit gibt. Auf darf verwerfen oder nicht halten.
Jede entscheidbare Sprache ist semi-entscheidbar, denn ein Entscheider erfüllt . Ist entscheidbar, so auch das Komplement : Vertausche im Entscheider und .
Der Name "rekursiv aufzählbar" kommt daher, dass sich genau diese Sprachen von einer Maschine Wort für Wort auflisten lassen. Diese Gleichwertigkeit ist ein Satz, den wir hier nicht brauchen.
Entscheidbar, semi-entscheidbar und eine Falle
Entscheidbar, semi-entscheidbar und eine Falle
Entscheidbar: und die Palindrome. Die Maschinen aus der letzten Lektion halten auf jedem Wort.
Semi-entscheidbar: Die Sprache der Polynome mit ganzzahligen Koeffizienten (etwa ), die eine ganzzahlige Nullstelle haben. Eine Maschine probiert für alle Tupel mit Einträgen zwischen und aus und akzeptiert, sobald eines das Polynom zu null macht. Gibt es eine Nullstelle, wird sie nach endlich vielen Runden gefunden. Gibt es keine, sucht die Maschine ewig. Dass es keinen Entscheider gibt, hat Juri Matijassewitsch 1970 bewiesen (Hilberts zehntes Problem).
Die Falle: Die Maschine aus der letzten Lektion hält auf Wörtern, die mit beginnen, nicht. Daraus folgt nicht, dass unentscheidbar ist: Eine andere Maschine entscheidet sie in einem Schritt. Entscheidbarkeit ist eine Eigenschaft der Sprache, nicht einer bestimmten Maschine.
Eine Turingmaschine akzeptiert jedes Wort aus und hält auf manchen Wörtern außerhalb von nicht. Was folgt sicher?
WHILE-Programme
Ein zweites Modell, näher an echten Programmiersprachen. Es gibt Variablen mit Werten in und genau diese Anweisungen ( ist eine feste Zahl):
- und , wobei die Subtraktion bei stehen bleibt ( ergibt ),
- : erst , dann ausführen,
- : wiederholen, solange ist.
Ein Programm berechnet , wenn es mit den Argumenten in und in allen anderen Variablen startet und genau dann endet, wenn definiert ist, und dann den Wert hat. Die Endlosschleife berechnet die Funktion, die nur bei definiert ist (mit Wert ).
Multiplikation als WHILE-Programm
Multiplikation als WHILE-Programm
Das Programm berechnet . Die Einrückung zeigt, was zu welcher Schleife gehört.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 2 | |
| 5 | 2 | |
| 6 | 1 | |
| 7 | 1 | |
| 8 | 0 |
Die äußere Schleife läuft -mal. Jedes Mal kopiert Zeile 2 den Wert nach , und die innere Schleife zählt um hoch. Mit , wird Zeile 4 zwölfmal ausgeführt, am Ende ist . Laufzeit: Zeile 4 läuft -mal, das Programm macht also Schritte.
Registermaschinen und -Kalkül
Registermaschine: Register mit Werten in und ein nummeriertes Programm aus den Befehlen "erhöhe um 1", "verringere um 1 (bei bleibt es )", "springe zu Befehl , falls " und "halte". Das ist ein Modell eines Prozessors mit unbegrenzt großen Speicherzellen.
-Kalkül: Es gibt nur Funktionen. Ein Term ist eine Variable , eine Abstraktion (die Funktion, die auf abbildet) oder eine Anwendung . Gerechnet wird mit einer einzigen Regel: wird zu , in dem jedes freie durch ersetzt ist. Zahlen werden als Funktionen kodiert: ist mit -mal .
Gleichwertigkeit der Modelle
Für eine partielle Funktion sind gleichwertig: ist Turing-berechenbar, ist WHILE-berechenbar, ist von einer Registermaschine berechenbar, ist im -Kalkül darstellbar.
Wir skizzieren die Richtungen zwischen Turingmaschinen und WHILE-Programmen; die übrigen Simulationen gehen nach demselben Muster.
WHILE nach TM: Jede Variable bekommt ein eigenes Band, auf dem ihr Wert binär steht. heißt: Band auf Band kopieren und -mal die Maschine "plus 1" laufen lassen; Subtraktion entsprechend. Hintereinanderausführung heißt: Zustandsmengen hintereinanderschalten. Eine WHILE-Schleife wird zu einem Zustand, der prüft, ob Band die Zahl trägt, und dann in den Rumpf springt oder weitergeht. Nach dem Satz über Mehrband-Maschinen genügt ein Band.
TM nach WHILE: Eine Konfiguration wird zu drei Zahlen: und als Ziffernfolgen zur Basis (jedes Bandzeichen ist eine Ziffer von bis ; wird von hinten gelesen, damit das Zeichen unter dem Kopf die letzte Ziffer ist) und als Nummer. Das Zeichen unter dem Kopf ist . Ein Rechenschritt ist eine Fallunterscheidung über die endlich vielen Paare aus Zustand und Zeichen, und jeder Fall ändert die drei Zahlen durch Multiplikation mit , Division durch und Addition. Das alles sind WHILE-Programme (Multiplikation steht oben, Division und Rest gehen ähnlich). Eine äußere Schleife "solange kein Haltezustand ist" wiederholt den Schritt.
Warum ist die Church-Turing-These nicht bewiesen worden?
Gödelnummerierung von Turingmaschinen
Damit Maschinen über Maschinen rechnen können, kodiert man jede Turingmaschine als Wort über . Nummeriere die Zustände (dabei sei der Start, , ), die Bandzeichen , , , und die Richtungen , , . Ein Übergang wird zu
,
und die Kodierung ist die Folge aller Übergänge, getrennt durch . Da in einem einzelnen Übergang nie zwei Einsen nebeneinander stehen, lässt sich eindeutig zurücklesen.
Ein Wort, das keine Maschine kodiert, ordnen wir einer festen Maschine zu, die sofort verwirft. So gehört zu jedem Wort eine Maschine . Diese Vereinbarung macht spätere Beweise kürzer.
Ein Übergang als Wort
Ein Übergang als Wort
Der Übergang ist , also .
Die Länge ist . Umgekehrt liest man aus die Blöcke ab und erhält den Übergang zurück.
Universelle Turingmaschine
Es gibt eine Turingmaschine , die auf Eingabe (mit ) genau dann akzeptiert, verwirft oder nicht hält, wenn auf dies tut.
Beweisidee: arbeitet wie ein Interpreter mit drei Bändern. Band 1 enthält , Band 2 das Band von (jedes Zeichen als , getrennt durch ), Band 3 den aktuellen Zustand als . Am Anfang schreibt das Wort in dieser Form auf Band 2 und (für ) auf Band 3.
Für einen Schritt von sucht auf Band 1 den Übergang, dessen erste beiden Blöcke mit Band 3 und dem Zeichen unter dem simulierten Kopf übereinstimmen. Dann ersetzt sie das Zeichen auf Band 2 (dabei muss sie eventuell den Rest des Bandes verschieben, weil die Kodierungen verschieden lang sind), bewegt den simulierten Kopf und schreibt den neuen Zustand auf Band 3. Steht dort oder , hält in bzw. . Die Simulation folgt Schritt für Schritt, also hält genau dann und mit demselben Ergebnis, wenn hält. Mit dem Mehrband-Satz geht es auch mit einem Band.
Abzählbar und überabzählbar
Eine Menge heißt abzählbar, wenn sie leer ist oder es eine surjektive Abbildung gibt: Man kann ihre Elemente in einer Liste aufschreiben, in der jedes Element irgendwann vorkommt. Sonst heißt überabzählbar.
Beispiel: ist abzählbar. Liste die Wörter der Länge nach und bei gleicher Länge wie Binärzahlen: Jedes Wort steht an einer endlichen Stelle. Gegenbeispiel einer untauglichen Liste: "erst alle Wörter aus Nullen, dann die anderen". Sie kommt nie bei an.
Es gibt nur abzählbar viele Turingmaschinen
Die Menge der semi-entscheidbaren Sprachen über ist abzählbar.
Jede semi-entscheidbare Sprache ist für eine Maschine , und jede Maschine ist für ein Wort (zum Beispiel ). Also ist eine surjektive Abbildung von auf die semi-entscheidbaren Sprachen, wobei die Liste aller Wörter von oben ist.
Cantor: Die Sprachen sind überabzählbar
Die Menge aller Sprachen über ist überabzählbar.
Beweisidee: Aus jeder vorgelegten Liste von Sprachen baut man eine Sprache, die sich von der -ten Sprache beim -ten Wort unterscheidet.
Angenommen, es gibt eine surjektive Abbildung von auf alle Sprachen. Schreibe die Zugehörigkeit als Tabelle: Zeile ist , Spalte ist das Wort , der Eintrag ist für und sonst . Definiere die Diagonalsprache
.
kehrt also die Diagonale der Tabelle um. Weil die Abbildung surjektiv ist, gibt es ein mit . Frage, ob in liegt: Nach Definition von gilt , und wegen heißt das . Das ist ein Widerspruch. Also gibt es keine solche Abbildung.
Nicht alles ist berechenbar
Es gibt Sprachen über , die nicht semi-entscheidbar sind, also von keiner Turingmaschine erkannt werden.
Wären alle Sprachen semi-entscheidbar, wäre die Menge aller Sprachen nach dem vorletzten Satz abzählbar. Das widerspricht dem Satz von Cantor. Nach der Church-Turing-These löst also kein Algorithmus der Welt das Wortproblem dieser Sprachen.
Die Diagonalsprache einfach hinzufügen
Die Diagonalsprache einfach hinzufügen
"Dann war die Liste eben unvollständig. Ich hänge vorne an, und jetzt ist sie vollständig." Und ein zweiter Fehler: "Der Beweis zeigt eine konkrete Sprache, die keine Maschine erkennt."
Auf die neue Liste lässt sich das Argument wieder anwenden und liefert eine neue Diagonalsprache, die fehlt. Der Satz sagt: Jede Liste ist unvollständig. Zum zweiten Punkt: Der Abzählbarkeitsbeweis zeigt nur, dass es solche Sprachen gibt. Eine konkrete liefert das Halteproblem in der nächsten Lektion, mit demselben Diagonalprinzip.
Zusammenfassung
Eine Sprache ist entscheidbar, wenn eine TM auf jeder Eingabe hält und richtig antwortet; semi-entscheidbar, wenn eine TM genau ihre Wörter akzeptiert.
Entscheidbare Sprachen sind semi-entscheidbar, und ihr Komplement ist wieder entscheidbar.
Turingmaschinen, WHILE-Programme, Registermaschinen und der -Kalkül berechnen dieselben partiellen Funktionen; man beweist das durch gegenseitige Simulation.
Die Church-Turing-These setzt "intuitiv berechenbar" mit "Turing-berechenbar" gleich. Sie ist nicht beweisbar, weil eine Seite kein mathematischer Begriff ist.
Eine Gödelnummerierung macht aus jeder TM ein Wort ; die universelle TM simuliert auf aus .
Es gibt abzählbar viele Turingmaschinen, aber nach Cantors Diagonalargument überabzählbar viele Sprachen. Also sind die meisten Sprachen nicht semi-entscheidbar.
Übungen
Die Sprache ist entscheidbar. Welche Aussage folgt?
In der Liste (der Länge nach, bei gleicher Länge wie Binärzahlen geordnet): Welchen Index hat das Wort ?
Wie viele Zeichen hat die Kodierung des Übergangs in der Gödelnummerierung der Lektion?
Welche dieser Mengen ist überabzählbar?
Zeige: Sind und semi-entscheidbar, so ist auch semi-entscheidbar. Warum darfst du nicht erst und danach laufen lassen?
Zeige mit einem Diagonalargument: Es gibt eine totale Funktion (überall definiert), die von keiner Turingmaschine berechnet wird.