Guten Morgen, heute haben wir eine ganz wichtige Vorlesung.
Heute geht es um Entscheidbarkeit oder Berechenbarkeit und wir werden
heute zeigen, dass es nicht entscheidbare Sprachen gibt.
Sie wissen das schon aus Grundbegriffe der Informatik.
Sie kennen daher das Halteproblem und dort wurde ein Beweis geführt,
dass das Halteproblem nicht entscheidend ist.
Wir werden heute etwas mehr insgesamt zeigen und der Beweis, der Weg,
wie wir zeigen unter anderem, dass das Halteproblem nicht entscheidbar
ist, ist auch ein bisschen anders als bei den Grundbegriffen der
Informatik.
Wie ist das mit dem Mikrofon?
Hat das Aussetzer oder hat es keine?
Hat keine, gut, okay.
Gut, Sie erinnern sich aus der letzten Vorlesung, dass wir die
Gödelnummer einer Turing-Maschine kennengelernt haben.
Also eine Art, für jede Turing-Maschine eine eindeutige Kodierung über
dem Alphabet 01 aufzustellen.
Heute gehen wir davon aus, dass wir die kennen.
Wie die im Detail aussieht, ist jetzt nicht mehr so wichtig heute.
Also, wir betrachten ein Wort im Alphabet 01 und die Turing-Maschine
TW sei eben die Turing-Maschine, die gerade als Gödelnummer das Wort W
hat.
Also die Turing-Maschine mit der Gödelnummer B, beziehungsweise es
gibt ja 01-Strings, die nicht so aussehen wie Gödelnummern.
Und dafür haben wir gesagt, naja gut, diese 01-Worte, die sollen
gerade Turing-Maschinen kodieren, die die leere Menge akzeptieren.
Das heißt also, wir können jetzt für jedes 01-Wort W sagen, dazu gibt
es eine Turing-Maschine.
Und L von TW sei die Sprache, die von der Turing-Maschine, deren
Gödelnummer oder Kodierung W ist, akzeptiert wird.
Wir konstruieren jetzt die Diagonalsprache LD.
Wir betrachten Wörter über dem Alphabet 01 und wir sortieren die in
kanonischer Reihenfolge.
Das heißt, ein Wort WI ist in dieser kanonischen Reihenfolge vor dem
Wort WJ, wenn es kleinere Länge hat als WJ, echt kleinere Länge, oder
aber wenn es gleiche Länge hat, wenn das WI lexikografisch vor WJ
kommt.
Das heißt also, ab jetzt bedeutet WI, W mit Index i, dass es in dieser
Reihenfolge das i-te Wort ist.
Alle 01-Worte werden sortiert in kanonischer Reihenfolge und dann
durchnummeriert.
Das erste, das zweite, das dritte, die i-te und so weiter.
Also der Index gibt immer an, an welcher Stelle in dieser Sortierung
das entsprechende 01-Wort steht.
Das können wir natürlich auch interpretieren als die Gödelnummern von
Turing -Maschinen werden sortiert hingeschrieben.
Also wir können genauso sagen, naja gut und WJ, das J-Wort in dieser
Sortierung, ist gleichzeitig die Gödelnummer von MJ, der
entsprechenden Turing-Maschine, die durch WJ kodiert wird.
Also diese Sortierung der Wörter, die induziert gleichzeitig eine
Sortierung der Turing-Maschinen.
Also wir bezeichnen jetzt mit MJ die Turing-Maschine, die durch die
Gödelnummer WJ kodiert ist und WJ steht gerade in unserer Tabelle an J
-Stelle.
So, dann können wir eine entsprechende zweidimensionale Tabelle oder
Matrix aufstellen, bei der wir
die Zeilen als Eingabeworte betrachten und die Spalten als
Gödelnummern von Turing-Maschinen und wir schreiben dann an die
Position IJ, I die Zeile, J die Spalte, eine 0 oder eine 1.
Und zwar eine 1, wenn WI in der Sprache ist, die von MJ akzeptiert
wird.
Ansonsten eine 0.
Also die Einträge dieser Tabelle sind IJ, die Stelle IJ steht 1, falls
die Turing-Maschine MJ das Wort WI akzeptiert und 0 sonst.
Kann man machen.
Und aus dieser zweidimensionalen Tabelle können wir jetzt die
Diagonalsprache ablesen.
Wir definieren als Diagonalsprache die Sprache all der Wörter WI, für
die gilt, die Turing-Maschine MI, Gödelnummer ja gerade WI, akzeptiert
WI nicht.
Also LD ist die Menge der Worte WI, Turing-Maschine MI akzeptiert WI
nicht.
Also die Turing-Maschine MI, bloß gelassen auf ihre eigene
Gödelnummer, akzeptiert nicht.
Wenn wir diese Tabelle mit den Einträgen IJ aufgestellt haben, dann
können wir natürlich leicht ablesen, welche Wörter gerade in LD, in
der Diagonalsprache landen.
Das sind nämlich die Wörter, wo auf der Diagonalen eine 0 steht.
Die WI, wo an der Stelle II 0 steht.
Für MI akzeptiert WI nicht.
LD enthält also alle WI, für die auf der Diagonalenstelle II eine 0
steht.
Diese Sprache benutzen wir für einen Diagonalbeweis nach dem Prinzip
von Kantor und dieses Prinzip haben Sie ja schon in Grundbegriffe der
Informatik gesehen, vielleicht auch schon an anderer Stelle.
So sieht unsere Tabelle aus.
Die Zeilen interpretieren wir eben als korrespondieren zu Worten über
0,1 in der Reihenfolge, wie diese Worte halt in unserer kanonischen
Ordnung herkommen.
Und die Spalten korrespondieren zu Gödelnummern.
Korrespondieren natürlich zu denselben Worten, ja, W1 bis W unendlich,
aber jetzt aufgefasst als Kodierung von Turingmaschinen.
Und wir schauen jetzt auf die Diagonale, steht in der Diagonale an der
Stelle II eine 0 oder eine 1.
Wenn dort eine 0 ist, dann soll das entsprechende Wort BI in der
Diagonalsprache sein.
Wenn dort eine 1 steht, soll es nicht in der Diagonalsprache sein.
Hier in dem Fall, bei dem Beispiel wäre BI in LD, BJ nicht in LD, BK
nicht in LD.
Und diese Sprache, die wir so definiert haben, ist nicht entscheidbar.
Das können wir jetzt beweisen, weil wir dieses Diagonalkonzept
verwenden.
Also die Sprache LD ist nicht entscheidbar.
Diese Argumentation, Diagonalbeweis läuft über einen Widerspruch.
Das heißt also, wir nehmen an, die wäre entscheidbar und führen dies
zum Widerspruch.
Angenommen, LD ist entscheidbar.
Dann gibt es eine Turingmaschine, die stets hält und genau die W aus
LD akzeptiert.
Also genau für die W aus LD akzeptierenden Endzustand hält.
Stellen Sie sich hier ruhig so eine Turingmaschine vor, die zwei
Stoppzustände hat, einen akzeptierenden und einen nicht
akzeptierenden.
Und wenn diese Turingmaschine LD entscheiden kann, dann stoppt sie in
dem akzeptierenden Endzustand, gerade bei Eingaben, die aus LD sind,
und bei allen anderen in dem nicht akzeptierenden Endzustand.
Diese Turingmaschine, die sehen wir auch in unserer Tabelle, die wir
eben aufgestellt haben, die entspricht irgendeinem Wort WI.
Dementsprechend ist das also so ein MI.
Jetzt wenden wir diese Turingmaschine auf ihre eigene Gödelnummer an.
Wenn das die Ite Turingmaschine ist in unserer Sortierung der
Codierungen von Turingmaschinen, dann ist das ja MI und die
Gödelnummer ist WI.
Wir wenden jetzt MI auf WI an.
MI kann LD entscheiden.
Das heißt, wenn WI aus LD ist, dann wird WI von MI akzeptiert.
Wenn WI nicht in LD ist, dann akzeptiert MI WI eben nicht.
Aber das ist jetzt gerade umgekehrt zur Definition der
Diagonalsprache.
In der Diagonalsprache sind ja gerade die Wörter WI, die von MI, der
Turingmaschine, deren Gödelnummer WI ist, nicht akzeptiert werden.
Das heißt also, diese beiden Schlüsse, falls WI in LD, dann wird WI
von MI akzeptiert.
Falls WI nicht in LD, dann akzeptiert MI das Wort WI nicht, sind
gerade im Widerspruch zur Definition der Diagonalsprache.
Damit sind wir fertig.
Damit haben wir gezeigt, die Diagonalsprache ist nicht entscheidbar.
Ganz kurz, ein einfacher Beweis.
Bisschen komisch, weil da der Widerspruch sozusagen vorbereitet ist
über die Art und Weise, wie wir die Diagonalsprache definiert haben.
Okay, schauen wir mal weiter in die Welt der nicht entscheidbaren
Sprachen.
Das Kompliment der Diagonalsprache ist auch nicht entscheidbar.
Also die Diagonalsprache ist eine Sprache über dem Alphabet 01.
Die Wörter aus der Diagonalsprache, das sind irgendwelche Worte aus 01
Sternen.
Kompliment sind gerade die anderen.
Kompliment von LD, LD-Kompliment ist gerade 01 Stern ohne LD.
Das sind natürlich dann genau die Wörter WI, für die gilt die Turing
-Maschine MI, die Turing-Maschine, deren Möbelnummer WI ist,
akzeptiert WI.
Haben wir eben gezeigt, die Diagonalsprache ist nicht entscheidbar,
dann ist das Kompliment ja auch nicht entscheidbar.
Ich könnte ansonsten die Turing-Maschine zum Entscheiden des
Kompliments der Diagonalsprache auch nehmen, um die Diagonalsprache
selbst zu entscheiden.
Eine stets schaltende Turing-Maschine, die genau im akzeptierenden
Endzustand hält, wenn das Eingabewort aus LD ist, dann müssten wir
dann einfach diese beiden Stopp-Zustände, den akzeptierenden und den
nicht akzeptierenden, umdrehen.
Und dann könnte man mit der so leicht modifizierten Turing-Maschine
auch LD entscheiden.
Also das ist offensichtlich, dass das Kompliment einer nicht
entscheidbaren Sprache auch nicht entscheidbar ist.
Also nochmal, falls LD-Kompliment entscheidbar ist, dann gibt es eine
Turing -Maschine, die LD-Kompliment entscheidet.
Diese können wir aber leicht umbauen in eine Turing-Maschine, die
gerade LD entscheidet.
Einfach vertauschen die beiden Stopp-Zustände, akzeptierenden und den
nicht akzeptierenden.
Und da LD, wie wir gerade gezeigt haben, nicht entscheidbar ist, ist
LD -Kompliment auch nicht entscheidbar.
Das können Sie immer machen, wenn Sie eine nicht entscheidbare Sprache
haben, dann sofort schließen, dass auch das Kompliment dieser Sprache
nicht entscheidbar ist.
Eine Argumentation durchgeführt, die eigentlich unabhängig davon ist,
wie LD-Kompliment genau definiert ist.
Womit wir auch schon etwas bewiesen haben, was ich ganz am Schluss der
Vorlesung nochmal aufnehmen werde.
Nämlich, dass die Menge der nicht entscheidbaren Sprachen bezüglich
Komplimentbildung abgeschlossen ist.
So, nun ist die Diagonalsprache so definiert, dass dieser
Diagonalbeweis funktioniert.
Die ist ja im Prinzip genau dafür konstruiert, dass man diesen
Diagonalbeweis führen kann.
Die hat aber auch eine Interpretation.
Kann man interpretieren als das Problem, ob eine Turing-Maschine auf
einer Eingabe W stoppt.
Das, was wir hier gerade bewiesen haben, können wir interpretieren als
ein Turing-Maschine-Problem.
Oder zu entscheiden, ob eine Turing-Maschine auf einer Eingabe W
stoppt, ist ebenfalls nicht entscheidbar.
Das ist das Halteproblem.
Diese Diagonalsprache zum Kompliment wird auch oft als spezielles
Halteproblem bezeichnet.
Es gibt so leichte Varianten, wie genau man das spezielle Halteproblem
definiert, die Diagonalsprache bzw.
ihr Kompliment definiert, aber das ist im Prinzip dasselbe.
Und jetzt das Halteproblem etwas allgemeiner aus.
Als Halteproblem definieren wir folgende Sprache.
Sprache H.
Dort drin liegen die Wörter WV, für die gilt, die Turing-Maschine,
deren Gödel Nummer W ist, hält auf der Eingabe V.
Wörter, die man als Kombination oder Konkatenation von zwei Wörtern
auffasst.
Der erste Teil ist Codierung einer Turing-Maschine, der zweite Teil
Eingabewort.
Die kombinierten Wörter sind in H, in der Sprache zum Halteproblem,
für die gilt, die Turing-Maschine, die zu dem ersten Teil gehört, hält
auf der Eingabe, die zum zweiten Teil gehört.
Dieses Problem ist ebenfalls nicht entscheidbar.
Bei der Diagonalsprache haben wir die Nichtentscheidbarkeit direkt
bewiesen.
Da haben wir kein anderes Problem verwendet, von dem wir schon wissen,
dass es nicht entscheidbar ist.
Beim Komplement der Diagonalsprache haben wir schon ein Prinzip
verwendet, das wir jetzt immer wieder verwenden, nämlich, dass wir die
Entscheidbarkeit oder Nichtentscheidbarkeit reduzieren auf die
Nichtentscheidbarkeit der Diagonalsprache.
Wir haben sozusagen die Annahme, das Komplement der Diagonalsprache
sei entscheidbar, zum Widerspruch dazu geführt, dass die
Diagonalsprache nicht entscheidbar ist.
Und genauso machen wir es jetzt auch beim Halteproblem.
Also wir nehmen wieder an, es existiere, wir nehmen wieder an, das
Halteproblem oder die Sprache zum Halteproblem wäre entscheidbar.
Dann existiert eine stets haltende Turing-Maschine, die gerade diese
Sprache zum Halteproblem, die Sprache H, entscheidet.
Die für beliebige Eingaben gerade sagen kann, ist in H oder ist nicht
in H.
Daraus konstruieren wir jetzt eine stets haltende Turing-Maschine, die
das Komplement der Diagonalsprache entscheiden kann.
Und damit haben wir einen Widerspruch zum vorherbewiesenen
Nichtentscheidbarkeit der Komplementsprache, der Diagonalsprache.
Reduktion.
Das ist das, was wir hier machen.
So jetzt sei also W eine Eingabe, für die wir entscheiden wollen, ob W
ein Komplement der Diagonalsprache ist.
Mit der Turing-Maschine zu H können wir dann folgendermaßen vorgehen.
Zunächst, weil wir schauen also dieses Eingabewort an, das ist in
unserer Tabelle, wo wir alle Worte über 0,1 durchnummeriert haben,
jetzt an irgendeiner Stelle I.
Also berechne das I, sodass W gerade dieses WI ist.
Jetzt betrachten wir die durch WI kodierte Turing-Maschine, MI.
Und die Turing-Maschine fürs Halteproblem wenden wir jetzt an auf die
Eingabe Kodierung MI, BI.
Also diese Turing-Maschine zu H, die erwartet ja solche Eingaben,
kombinierte Worte.
Das erste ist Kodierung einer Turing-Maschine, das zweite eine
Eingabe.
Und so eins geben wir der jetzt, nämlich gerade Kodierung von MI, WI.
Und jetzt gucken wir nach, was die Turing-Maschine für die Sprache des
Halteproblems auf diese Eingabe macht.
Wenn sie die Eingabe nicht akzeptiert, dann heißt das ja, dass MI, die
Turing -Maschine, Mödelnummer WI, nicht auf WI hält.
Damit ist dann das WI insbesondere in der Diagonalsprache, Sprache der
Worte, WI, die von der entsprechenden Turing-Maschine MI nicht
akzeptiert werden.
Das heißt also, das WI ist nicht im Komplement der Diagonalsprache.
Und andererseits, wenn jetzt die Turing-Maschine zur Sprache des
Halteproblems Kodierung von MI, WI akzeptiert, dann heißt das, es hält
MI auf WI an.
Nach Definition der Sprache zum Halteproblem, also wenn so ein Wort
akzeptiert wird, dann heißt es ja, die Turing-Maschine zum ersten
Teilwort hält auf der Eingabe zum zweiten Teilwort an.
Das heißt also, wenn Kodierung MI, WI akzeptiert wird, dann hält MI
auf WI an.
Und dann können wir aber auch nachgucken, was MI auf WI machen würde,
akzeptieren oder nicht akzeptieren.
Das heißt also, wir können dann die Berechnung, die MI auf WI
durchführen würde, vollständig simulieren.
Das heißt also, dann können wir auch entscheiden, ob WI in LD oder in
LD -Komplement ist.
Also das ist jetzt vielleicht nicht ganz so trivialer Beweis für die
Nichtentscheidbarkeit einer Sprache.
Und der funktioniert so, dass wir die Annahme, die Sprache wäre
entscheidbar, zu einem Widerspruch führen dazu, dass eine andere
Sprache nicht entscheidbar ist, von der wir eben schon
Nichtentscheidbarkeit bewiesen.
Diesem Beweis sieht man auch an, warum wir die Diagonalsprache
sozusagen so umgekehrt, als man es vielleicht erwarten würde,
definiert haben.
Die Menge der Wörter WI, MI, Turing-Maschine mit Kodierung WI,
akzeptiert WI nicht.
Weil hier genau dieser Beweis durch eine Reduktion auf das Komplement
funktioniert.
Jetzt schauen wir uns noch eine weitere Sprache an, die nicht
entscheidbar ist.
Die sogenannte universelle Sprache.
Die universelle Sprache ist wieder eine Sprache über dem Alphabet 01
und die ist folgendermaßen definiert.
Sie enthält gerade die Wörter WV.
V wird, wenn der Turing-Maschine mit Gödelnummer W akzeptiert.
Oder anders ausgedrückt, V ist ein Element der Sprache, die von der
Turing -Maschine mit Gödelnummer W erkannt wird.
Universelle Sprache ist die Menge aller Wörter, WV, für die Turing
-Maschine mit Index W diejenige sein, deren Gödelnummer gerade W ist,
bei der Eingabe von V hält und V akzeptiert.
Diese Sprache ist jetzt wieder nicht entscheidbar und ihr Beweis
funktioniert wieder über Reduktion.
Denn was man leicht feststellen kann, ist, dass diese Sprache eine
Verallgemeinerung der Komplementsprache der Diagonalsprache ist.
Das Komplement der Diagonalsprache ist ja gerade die Sprache der
Wörter, in dieser Form ausgedrückt, der Wörter WW, TW, akzeptiert W.
Das war das Komplement der Diagonalsprache.
Und das, was wir hier als universelle Sprache definiert haben, ist ja
allgemeiner.
Wir nehmen jetzt an, die universelle Sprache ist entscheidbar.
Dann gibt es eine Turing-Maschine, die eben diese Sprache LU
entscheidet.
Wir zeigen, dass dann auch das Komplement der Diagonalsprache
entschieden wird.
Irgendwie folgt vor, wir betrachten das Wort, für das wir wissen
wollen, ob es in LD Komplement ist oder nicht, und berechnen wieder
dessen Index in der Tabelle aller 0-1-Worte.
Wir betrachten die durch WI kodierte Turing-Maschine MI und wir wenden
die Turing-Maschine für universelle Sprache gerade auf das Wort
Kodierung MIWI an.
Ein Wort, was so aussieht, wie die Worte aussehen sollen, die in der
Sprache zur universellen Sprache liegen.
Aber es ist noch spezieller.
Das ist so eine Art Wort, für das wir sagen können, das ist in LD
Komplement oder eben nicht.
Wenn LU also entscheidbar wäre, dann könnte man jetzt für dieses Wort
entscheiden, ob es in LD Komplement ist oder nicht.
Weil die Turing-Maschine zu LU insbesondere für solche Worte,
Kodierung einer Turing-Maschine, gefolgt von dem entsprechenden Wort,
entscheiden kann, ob es in LU ist oder nicht.
Das heißt also, wenn LU entscheidbar wäre, dann wäre auch LD
Komplement entscheidbar.
Was jetzt aber interessant ist, ist, dass diese universelle Sprache
sehr wohl semi-entscheidbar ist.
Also die universelle Sprache ist nicht entscheidbar, aber semi
-entscheidbar.
Was ist der Unterschied zwischen Entscheidbarkeit und Semi
-Entscheidbarkeit?
Um zu sagen, eine Sprache ist entscheidbar, muss es eine Turing
-Maschine geben, die auf allen Eingaben hält und genau die Eingaben,
die aus der Sprache sind, akzeptiert.
Da kann man sich immer diese schöne Turing-Maschine vorstellen, die
immer hält, zwei Stopp-Zustände hat, QJ und QN, entweder sie hält in
QJ oder sie hält in QN.
Wenn sie eine Eingabe aus QJ hält, dann akzeptiert sie sie.
Wenn sie bei einer Eingabe bei QJ hält, dann akzeptiert sie die
Eingabe.
Wenn sie bei einer Eingabe auf QN hält, dann akzeptiert sie sie.
Aber semi-entscheidbar dagegen heißt nur, es gibt eine Turing
-Maschine, die auf Worten aus der Sprache hält und diese akzeptiert.
Was bei den anderen Eingaben passiert, die nicht aus der Sprache sind,
sei dahingestellt.
Selbst die Möglichkeit, sie hält auch da, akzeptiert aber nicht oder
aber sie hält da gar nicht.
Das ist wirklich auf der Definitionsebene etwas anderes und die Frage
ist, ist es wirklich was anderes?
Wir zeigen, dass die universelle Sprache semi-entscheidbar ist, dann
sagt das insbesondere auch, dass semi-entscheidbarkeit und
entscheidbarkeit zwei verschiedene Sachen sind.
Entscheidbarkeit ist mehr.
Wir zeigen die Sprache LU, die Sprache der Wörter WV, V ist in der
Sprache, die von der Turing-Maschine mit Gödelnummer W akzeptiert
wird, ist semi-entscheidbar.
Dafür müssen wir jetzt eine Turing-Maschine angeben, die genau bei
Wörtern aus LU in einem akzeptierenden Endzustand hält.
Wir benutzen die universelle Turing-Maschine mit der Eingabe WV.
Sie simuliert die Turing-Maschine TW bei V, das heißt das.
Wenn TW die Eingabe V akzeptiert, dann geschieht das insbesondere nach
endlich vielen Schritten, dann hält sie insbesondere.
Das heißt, wir können dann sagen, die universelle Turing-Maschine
akzeptiert WV.
Wenn die Turing-Maschine mit Gödelnummer W die Eingabe V nicht
akzeptiert, dann wird WV von der universellen Turing-Maschine nicht
akzeptiert, aber das ist ganz egal, ob die jetzt stoppt oder nicht
stoppt.
Also wir können eine Turing-Maschine angeben, unter Benutzung von TW,
die LU entscheidet.
Für jede Eingabe WV simulieren wir auf der universellen Turing
-Maschine, was TW auf der Eingabe V machen würde.
Und wenn TW V akzeptiert, dann sagen wir, die universelle Turing
-Maschine akzeptiert WV.
Und ansonsten kann uns egal sein, was die universelle Turing-Maschine.
Mit diesem Satz und dem vorherigen haben wir also insbesondere
festgestellt, dass die Begriffe entscheidbar und semi-entscheidbar
Verschiedenes bedeuten.
Sprachen können semi-entscheidbar sein, aber nicht entscheidbar.
So,
jetzt geht es noch weiter.
Es gibt einen sehr allgemeinen Satz, den Satz von Reis, der uns im
Prinzip die Möglichkeit gibt, große Anzahl von nicht entscheidbaren
Sprachen anzugeben.
Das heißt also, diese nicht entscheidbaren Sprachen, die wir bisher
gesehen haben, das sind nicht jetzt irgendwelche Einzelfälle, sondern
man kann eine allgemeinere Aussage darüber treffen, was ist alles an
nicht entscheidbaren Sprachen.
Den Satz von Reis kann man nämlich so interpretieren, dass aus einem
Programm im Allgemeinen keine nicht-triviale Eigenschaft der Funktion
ableiten kann, die von dem Programm realisiert wird.
Beim Halteproblem haben wir im Prinzip zu einem Programm eine
bestimmte nicht-triviale Eigenschaft betrachtet, nämlich die, ob das
Programm auf einer Eingabe hält.
Nachgewiesen, dass dieses Problem nicht entscheidbar ist.
Man kann ganz allgemein zeigen, und das sagt der Satz von Reis, dass
man beliebige nicht-triviale Eigenschaft einer Funktion, die von einem
Programm realisiert wird, nicht an dem Programm ableiten kann.
Und dazu wird folgendes betrachtet.
Wird R betrachtet, die Menge der von Turing-Maschinen berechenbaren
Funktionen.
Und S sei jetzt eine beliebige nicht-triviale Teilmenge von R.
Nicht-trivial heißt weder leer noch ganz S.
Aber irgendeine beliebige Teilmenge von RS.
Und als die entsprechende Sprache definieren wir die Codierungen
jeweils der Turing-Maschinen, die irgendeine Funktion aus S berechnen.
Also die Sprache zu so einer Menge von Turing-Berechenbaren Funktionen
S.
Es definiert als L von S gleich Menge der Codierungen von der Turing
-Maschine M.
M berechnet irgendeine Funktion aus S.
Und diese Sprache ist also jetzt für eine beliebige nicht-triviale
Teilmenge S der Menge aller Turing-Berechenbaren Funktionen nicht
entscheidbar.
Damit haben Sie eine Riesenklasse nicht-entscheidbarer Sprachen.
Das beweisen wir jetzt nicht ausführlich.
Das Beweisprinzip ist so, wie wir jetzt schon mehrfach Nicht
-Entscheidbarkeitsbeweise geführt haben.
Wir reduzieren die Nicht-Entscheidbarkeit auf eine Sprache, von der
wir schon wissen.
Und zwar kann man das folgendermaßen machen.
Man betrachtet das spezielle Problem Sprache A-Epsilon.
Das ist die Menge aller Codierungen von Turing-Maschinen, die auf der
Eingabe Epsilon halten.
Auch für die kann man zeigen, dass sie nicht-entscheidbar ist.
Entsprechend ist auch das Kompliment dieser Sprache nicht
-entscheidbar.
Und dann führen wir einen Widerspruch.
Spruchsbeweis für die Unentscheidbarkeit zu einer Sprache L von S,
indem wir für Komplimentsprache dieser speziellen Halteproblemsprache
eine Turing-Maschine konstruieren, die diese entscheiden würde unter
der Turing-Maschine, die es nach Annahme Ls sei entscheidbar für Ls
geben.
Das ist jetzt einfach wieder das Schema eines Reduktionsbeweises.
So kann man den Satz von Reis beweisen.
Der Satz hat weitreichende Konsequenzen.
Es ist für Programme nicht-entscheidbar, ob die durch sie definierte
Sprache endlich ist, ob die leer ist, ob die unendlich ist, ob die
ganz Sigma Stern ist.
Alle diese Sprachen, die könnte man als Sprachen zu einer nicht
-trivialen Teilmenge der Turing-berechenbaren Funktionen definieren.
Das ist das, was man auf jeden Fall mitnehmen muss.
Nicht-entscheidbarkeit, das ist jetzt nicht nur für so ein oder zwei
spezielle Sprachen nachweisbar.
Eine große Klasse.
Und das andere, das Beweisprinzip, das wir hier angewendet haben,
mehrfach, Reduktionsbeweis.
Wir haben die Unentscheidbarkeit von dem Komplement der
Diagonalsprache, von der Sprache zum Halteproblem, der universellen
Sprache, zurückgeführt letztendlich auf die Unentscheidbarkeit der
Diagonalsprache.
Nur für die Diagonalsprache selbst haben wir direkt
Nichtentscheidbarkeit bewiesen.
Wenn sich das klar macht, dann wird wohl auch klar, warum sie so sehr
speziell definiert wird, die Diagonalsprache, die ist so definiert,
dass man dieses Kantorprinzip verwenden kann.
Aber für alle anderen Sprachen oder Probleme, die nichtentscheidbar
sind, kann man Unentscheidbarkeit zeigen, indem man Existenz eines
Entscheidungsverfahrens nutzen würde, um für ein anderes Problem auch
ein Entscheidungsverfahren zu haben.
Ein anderes Problem, von dem wir vorher aber bewiesen haben, es ist
nichtentscheidbar.
Wenn wir für ein neues Problem zeigen wollen, es ist
nichtentscheidbar, dann nehmen wir an, es wäre entscheidbar, nehmen
die entsprechende Turingmaschine her und benutzen sie, um dann eine
andere Sprache bzw.
ein anderes Problem zu entscheiden, von dem wir vorher bewiesen haben,
es ist nichtentscheidbar.
Das ist das Prinzip.
Und sowas nennt man Reduktionsbeweis.
Ich betone das hier auch deshalb, weil das ein Beweisprinzip ist, das
in der theoretischen Informatik auch an anderen Stellen intensiv
genutzt wird.
Wir werden im nächsten Kapitel über Komplexität von Problemen,
Sprachen sprechen und auch da werden wir solche Reduktionsbeweise
führen, um zu zeigen, dass eine Sprache zu sehr schweren gehört, zu
einer bestimmten Klasse von Sprachen.
Ich sehe, ich bin heute viel schneller, als ich eigentlich sein
wollte.
Ich weiß auch nicht, wie das jetzt passieren konnte.
Aber gut, bei den
Sprachen, die wir bisher betrachtet haben, das ist auch mein erster
Teil der Vorlesung, Diagonalsprache,
Sprache zum Halteproblem, da mögen Sie noch sagen,
die sind ja auch komisch definiert, die komischen Sprachen.
Sprache der Wörter, für die gilt, die Turing-Maschine mit dem
entsprechenden Wort kodiert ist, akzeptiert das Wort nicht.
Kompliment.
Halteproblem, Menge der Wörter, WV, die Turing-Maschine, die durch W
kodiert ist, hält auf der Eingabe V.
Das stecken ja keine Probleme dahinter, wo man kombinatorisch oder mit
irgendwelchen Rechnungen zur Lösung kommt.
Ich zeige Ihnen jetzt eines, Problem beziehungsweise die entsprechende
Sprache, das so eigentlich ganz harmlos aussieht auf den ersten Blick.
Wie so ein Problem, das man durch einfache Kombinatorik lösen kann.
Das aber auch nicht entscheidbar ist.
Das ist das Postschekorrespondenzproblem.
Postschekorrespondenzproblem sieht folgendermaßen aus.
Sie betrachten als Eingabe des Problems eine Menge von Paaren von
Worten.
Und die Reihenfolge, wie diese Paare daherkommen, ist wichtig.
Also Sie betrachten eine Folge von Wortpaaren, die aber endlich ist.
Also so eine Eingabe sieht so aus, das sind ein paar x1, y1, x2, y2
und so weiter bis xn, yn.
Worte sind ganz normal, wie wir es kennen, Worte über einem endlichen
Alphabet.
Die Frage, die Sie sich jetzt stellen, ist, kann ich mit xen dasselbe
Wort bauen wie mit ys, wobei die Indizes der xe, die ich benutze und
die Reihenfolge, in der ich sie benutze, auch bei dem aus den ys selbe
ist wie bei dem durch die ys kombinierten Wort.
Das heißt also, gibt es so eine Folge von Indizes, 1 bis ik, aus
dieser Indexmenge 1 bis n, hier durch die Eingabe n, sodass xi1 bis
xik, Worte xi1 bis xik einfach hintereinander geschrieben, dasselbe
Wort ergeben wie yi1 bis yik.
Also, diese Indizes können durchaus in einer anderen Reihenfolge
kommen als 1 bis n.
Da können auch bestimmte Indizes mehrfach drin vorkommen.
Und es kommt mir nur darauf an zu entscheiden, ob es überhaupt so eine
Folge von Indizes gibt, sodass die x, hintereinander geschrieben
entsprechend der Folge der Indizes, dasselbe Wort ergibt wie die
entsprechenden ys der entsprechenden Reihenfolge hintereinander.
Also diese i1 bis ik, das könnten ganz wenige sein, das könnten ganz
viele sein, das können also mehr als n sein, weil es bestimmte Indizes
mehrfach vorkommen, das können aber auch nur drei sein.
Die Frage ist einfach nur, gibt es überhaupt so eine Folge.
Das sieht, denke ich, auf den ersten Blick nicht so schrecklich aus,
für eine konkrete Eingabe sowas zu entscheiden.
Gucken wir uns mal so ein Beispiel an, wo es so eine Folge gibt.
Kleines Beispiel.
K besteht nur aus drei Wortpaaren.
Das erste Wortpaar ist 1,111, also x1 ist 1, y1 ist 111.
Das zweite Wortpaar ist 101111,10, also x2 ist 101111, y2 ist 10.
Und das dritte Wortpaar, y3, ist 10,0.
Diese Eingabe hat eine Lösung.
Für diese Eingabe gibt es so eine Folge von Indizes, sodass die xe
hintereinander geschrieben, entsprechend der Indizes, der Folge der
Indizes, dasselbe Wort ergibt, wie die entsprechenden ys
hintereinander geschrieben.
Nämlich die Folge 2113.
Schreiben wir einfach mal x2, x1, x1, x3 einerseits hin und
andererseits y2, y1, y1, y3.
Wenn x2, x1, x1, x3 hinschreibt, dann ist das x2, das ist 101111, 111.
Gefolgt von x1, das ist die 1, gefolgt nochmal von x1, das ist die 1,
gefolgt von x3, das ist 1,0.
Das heißt also x2, x1, x1, x3 ist 1011111110.
Andererseits schreiben wir mal hin, wie y2, y1, y1, y3 aussieht.
y2 ist 1,0.
y1 ist 111.
Nochmal y1 ist nochmal 111.
Und dann gefolgt von y3, das ist die 0.
Das heißt also y2, y1, y1, y3 ergibt dasselbe wie x2, x1, x1, x3.
Für diese Eingabe gibt es mindestens eine Lösung, nämlich die
Indexfolge 2, 1, 1, 3.
Es gibt genauso kleine Instanzen, die keine Lösung haben.
Etwa diese Eingabe, bestehend aus drei Wortpaaren, 1, 0, 1, 0, 1, 0,
1, 1, 1, 1, 0, 1, 1, 1.
Eine Eingabe ganz, die keine Lösung hat.
Man sieht jetzt nicht auf den ersten Blick, dass es keine Lösung hat,
kann man aber argumentieren.
Wenn man einen bestimmten Index verwenden würde, hat das weitere
Konsequenzen, welche Indizes man davor oder dahinter in der
entsprechenden Folge von Indizes verwenden müsste und führt das im
Prinzip zum Widerspruch.
Diese Instanz hat keine Lösung und hier haben wir eine Instanz, die
ist unwesentlich größer.
Es gibt halt vier Wortpaare und da ist es so, sie hat eine Lösung.
Dazu gibt es eine Folge von Indizes, sodass die X entsprechend dieser
Folge von Indizes hintereinander geschrieben, dasselbe Wort ergibt wie
die Y entsprechend dieser Folge von Indizes hintereinander
geschrieben.
Das ist aber eine Folge mit 66 Indizes.
Fragen Sie mich jetzt nicht, wie die aussehen.
Das müssen mal irgendwelche fleißigen Leute sich überlegen.
Ein Problem, das Postschul-Korrespondenz-Problem, bei dem man auf den
ersten Blick vielleicht sagen würde, ja, das ist doch sicher
entscheidbar, da muss man doch nur so ein bisschen Kombinatorik
anwenden.
Es ist aber so, dass dieses Problem nicht entscheidbar ist.
Das kann man beweisen, wieder nach dem Reduktionsprinzip, indem man
die Unentscheidbarkeit des Postschul-Korrespondenz-Problems reduziert
auf die Nichtentscheidbarkeit des Halteproblems.
Man nimmt an, es sei entscheidbar, dann gibt es eine Turing-Maschine,
die dieses Problem entscheiden kann, oder eine entsprechend dazu
definierte Sprache.
Dann benutzt man diese Turing-Maschine, um das Halteproblem zu
entscheiden, und das ist ein Widerspruch dazu, dass das Halteproblem
nicht entscheidbar ist.
Also nächste Beobachtung heute, es gibt durchaus harmlos aussehende
Probleme, die nicht entscheidbar sind.
So ein paar Eigenschaften von entscheidbaren bzw.
semientscheidbaren Sprachen.
Was wir schon festgestellt haben, ist, dass die Menge aller
entscheidbaren Sprachen abgeschlossen ist bezüglich Komplementbildung.
Habe ich schon argumentiert, als wir gezeigt haben, dass das
Komplement der Diagonalsprache nicht entscheidbar ist.
Wenn das entscheidbar wäre, dann wäre auch die Diagonalsprache selber
entscheidbar.
Im Prinzip kann man die Turing-Maschine für das eine immer für die
Turing -Maschine für das andere verwenden.
Entscheidbarkeit, wissen Sie ja immer, Sie haben eine Turing-Maschine,
die immer hält, bei allen Eingaben.
Bei denen, die aus der vorgegebenen Sprache sind, im akzeptierenden
Endzustand, bei anderen in einem nicht akzeptierenden Stopp-Zustand.
Wir stellen uns einfach immer diese Turing-Maschine vor, die genau
zwei Zustände hat, bei denen sie stoppt.
Das eine ist der akzeptierende, das andere ist nicht akzeptierende.
Das Komplement der Sprache kann man dann immer genauso entscheiden,
indem man einfach die Turing-Maschine nimmt, bei denen die beiden
Zustände vertauscht sind.
Also das ist offensichtlich.
Und was man daraus noch schließen kann ist, dass die Menge aller
entscheidbaren Sprachen auch bezüglich Durchschnittsbildung und
Vereinigungsbildung abgeschlossen ist.
Was heißt das?
Sie haben zwei entscheidbare Sprachen, dann ist auch die Sprache, die
Sie bekommen, wenn Sie den Durchschnitt, den mengentheoretischen
Durchschnitt bilden, entscheidbar.
Genauso die Sprache, die Sie bekommen, wenn Sie die Vereinigung der
beiden Sprachen nehmen.
Das werden Sie in großen Übungen oder in Tutorien angucken.
Das ist nicht schwer.
Bei semientscheidbaren Sprachen ist es ein bisschen anders.
Die Menge aller semientscheidbaren Sprachen ist zwar abgeschlossen
bezüglich Durchschnittsbildung und bezüglich Vereinigungsbildung, aber
nicht bezüglich Komplementbildung.
Das ist klar, bei semientscheidbarkeit, da haben Sie nicht diese
Symmetrie zwischen akzeptieren und nicht akzeptieren.
Bei semientscheidbaren Sprachen, da wissen Sie, es gibt eine
Turingmaschine, die auf den Worten der Sprache endet und zwar in einem
akzeptierenden Endzustand.
Was aber passiert bei Eingaben, die nicht aus der Sprache sind, ist
offen.
Die Turingmaschine hält möglicherweise noch nicht.
Das heißt also, diesen Trick, den man machen kann, um sich
klarzumachen, dass das Komplement einer nichtentscheidbaren Sprache
auch nichtentscheidbar ist, bzw.
dass das Komplement einer entscheidbaren Sprache auch entscheidbar
ist, den Trick können Sie da nicht machen.
Also die semientscheidbaren Sprachen sind nicht unter
Komplementbildung abgeschlossen, kann man sich leicht überlegen.
Der Trick, wie man beweisen kann, dass die entscheidbaren Sprachen
bezüglich Komplementbildung abgeschlossen sind, funktioniert.
Aber bezüglich Durchschnittsbildung und Vereinigung ist auch die Menge
der semientscheidbaren abgeschlossen.
In
ein bisschen anderen Worten ausgedrückt, das, was hier steht, Teil von
dem, was hier steht, folgender Satz.
Wenn Sie eine Sprache aus Sigma-Stern betrachten und ihren Komplement,
was ja nichts anderes ist als Sigma-Stern ohne die Sprache, dann gilt,
die Sprache ist genau dann entscheidbar, wenn ihr Komplement
entscheidet.
Jetzt schon wiederholt erklärt, wieso das so ist.
Das andere, was man sich überlegen kann, ist, wenn die Sprache und ihr
Komplement semientscheidbar sind, dann ist die Sprache sogar
entscheidbar.
Wie gesagt, das werden Sie in den Übungen und Tutorien noch machen.
Ich will jetzt noch mal so ein bisschen zusammenfassend was
aufschreiben.
Wir haben heute die Diagonalsprache betrachtet.
Die ist folgendermaßen definiert.
Die Sprache haben wir angeschaut und wir haben gezeigt, die ist nicht
entscheidbar.
Man kann sogar zeigen, sie ist nicht semientscheidbar.
Da kann man im Prinzip denselben Beweis nehmen.
Da haben wir in dem Beweis, dass LD nicht entscheidbar ist, gar nicht
verwendet, was wir angenommen haben bei dem Widerspruchsbeweis.
Es gibt eine stets haltende Turing-Maschine.
Da sollten Sie sich mal selber überlegen.
Wie gesagt, in der Übung wird das auch nochmal aufgeführt.
Dann haben wir LD-Kompliment betrachtet.
LD-Kompliment ist nicht entscheidbar.
Das haben wir bewiesen.
Hier gilt aber, dass LD-Kompliment semientscheidbar ist.
Das kommt auch in der Übung dann nochmal.
Aber ab einem gewissen Punkt sind die Beweise gar nicht so schwierig.
Wenn Sie ein gewisses Wissen angesammelt haben, auch bezüglich der
Abgeschlossenheitsfragen, dann kommen die Purzeln, diese Sachen direkt
als Folgerungen raus.
Wir hatten dann noch das Halteproblem oder die Sprache zum
Halteproblem.
Definiert als die Menge der Bau.
Spuringmaschine mit Gödel Nummer W hält bei Eingabe B.
Auch dazu haben wir gezeigt, dass H nicht entscheidbar ist.
Es gilt aber, dass H semientscheidbar ist.
Das können wir uns eigentlich nochmal ganz schnell klar machen.
Obwohl wir das bisher noch nicht explizit gezeigt haben.
Das kann man sich eigentlich leicht überlegen.
Es existiert eine Turing-Maschine
B, die zu Eingabe BV, die Turing-Maschine BW auf Eingabe V
simuliert.
Falls BW auf V hält, so akzeptiere die
Turing -Maschine T gerade die Eingabe BV.
Fertig.
Im Prinzip dasselbe Muster wie bei Entscheidbarkeit der universellen
Sprache.
Das kann man nicht für das Komplement des Halteproblems machen.
Und jetzt gehen wir nochmal zurück zu dieser Sache hier.
Wir haben hier diese Aussage, wenn L und L-Komplement semientscheidbar
sind, dann ist L sogar entscheidbar.
Und ich habe eben gesagt, L-D, die Komplementsprache, ist nicht
entscheidbar, aber semientscheidbar.
Genauso wie die Sprache zum Halteproblem.
Ist nicht entscheidbar, aber semientscheidbar.
Wenn dann jeweils auch die Komplementsprache semientscheidbar wäre,
dann hätte man einen Widerspruch.
Durch diese Aussage hier einen Widerspruch.
Für Nichtentscheidbarkeit.
Da ist also hier dieses Muster.
L-D-Komplement nicht entscheidbar, aber L-D-Komplement
semientscheidbar.
H nicht entscheidbar, aber H semientscheidbar.
Das ist genau dasselbe.
Und daraus folgt umgekehrt, dass das Komplement von L-D-Komplement,
also L-D, nicht semientscheidbar sein kann.
Das Komplement von H, also H-Komplement, nicht semientscheidbar sein
kann.
Also dieser eine Teil des Satzes, der ist gut zu gebrauchen, um sich
weitere Reduktionsbeweise etwa zu sparen.
Okay, das wäre es für heute.