Guten Morgen fangen wir an.
Sie haben ja in der letzten Woche bereits begonnen mit dem neuen
Kapitel Berechenbarkeit Turing-Maschinen.
Und das Konzept der Turing-Maschine wurde auch bereits eingeführt.
Daran werden wir jetzt gleich weiter anknüpfen.
Aber nochmal, was ist Sinn und Zweck dieses Kapitels?
Also innerhalb des ganzen Fokus oder Themas, das von der theoretischen
Informatik abgedeckt wird, ist das Kapitel Berechenbarkeit dasjenige,
was sozusagen diese ganz grundlegenden Fragen gibt es Grenzen der
Berechenbarkeit?
Gibt es irgendwelche Probleme, die nicht berechenbar sind, abklärt?
Das heißt, es ist ganz grundlegend, was wir hier in dem Kapitel
besprechen werden.
Und wenn wir dazu Turing-Maschinen betrachten, dann ähnlich wie bei
den endlichen Automaten, als ein abstraktes Modell für echte Rechner,
um Aussagen machen zu können darüber, was echte Rechner können und vor
allem, was sie nicht können.
Und das Turing-Maschinen-Modell, das wir kennengelernt haben,
sah also so aus.
Zunächst mal, das ist ein deterministisches Berechnungsmodell, das wir
jetzt betrachten.
Wir werden, das schon vorab, auch eine nicht deterministische Variante
der Turing-Maschine im nächsten Kapitel betrachten und auch darüber
uns dann Gedanken machen, was eigentlich deterministische und nicht
deterministische Turing-Maschinen miteinander zu tun haben oder wie
die zueinander bestehen.
Aber jetzt erst mal, die nicht deterministische Turing-Maschine
besteht aus einer Zustandsmenge Q, die endlich ist, wie beim endlichen
Automat, einem Eingabealphabet Sigma, das ebenfalls endlich ist, das
ist eben auch wie beim endlichen Automat.
Es gibt ein spezielles Symbol Plank, das nicht im Eingabealphabet ist
und wir betrachten noch weitere Symbole, die so Art Hilfssymbole sind
und diese Symbole zusammen mit dem Eingabealphabet und dem Plank
bilden das Bandalphabet Gamma, das aber eben auch endlich ist.
Wir haben einen ausgezeichneten Startzustand und wir haben eine
Übergangsfunktion, die nimmt sich einen Zustand her und ein Symbol aus
dem Bandalphabet und bildet die ab auf einen neuen Zustand, ein neues
Symbol aus dem Bandalphabet und eine Aktion, die sein kann, gehe nach
links, gehe nach rechts oder bleibe stehen.
Das heißt also, von einem Zustand wird in einen neuen Zustand
übergegangen, das ist so ähnlich wie beim endlichen Automat, aber das
konkret jetzt gelesene Symbol aus Gamma wird möglicherweise
überschrieben und dann geht der Lese-Schreibkopf nach links oder nach
rechts oder bleibt dort stehen, wo er ist und dann kann man noch eine
Menge von Endzuständen definieren, Zustände, für die gilt, wenn die
Turing -Maschine in einen dieser Zustände kommt, hält sie und man kann
dann eben auch noch definieren oder auch nicht, ob das akzeptierende
Endzustände sind, ob es mehr als einen akzeptierenden Endzustand gibt
und so weiter.
Das sozusagen nochmal zur formalen Einführung und dann haben Sie auch
schon gesehen an Beispielen, wie so eine Turing-Maschine arbeitet.
Heute werden wir weitere Beispiele betrachten.
Hier nur nochmal die wichtigen Punkte zur Arbeitsweise der Turing
-Maschine.
Also es geht wieder in erster Linie darum, ob dieses Maschinenmodell,
Turing -Maschine oder eine konkrete, eine vorgegebene Sprache
akzeptiert oder erkennen kann.
Und wir sagen, eine Turing-Maschine akzeptiert eine Eingabe über dem
Eingabealphabet, wenn sie nach Lesen der entsprechende Eingabe in
einem Zustand aus F stoppt.
Also diese Endzustände, so wie wir es jetzt erstmal in der Definition
festgelegt haben, sind akzeptierende Endzustände.
Und sie akzeptiert dann eine ganze Sprache, genau dann, wenn sie
ausschließlich aus Eingaben aus dieser Sprache in einem akzeptierenden
Endzustand stoppt.
Also wenn sie ausschließend oder genau die Worte aus der Sprache
akzeptiert.
Das ist im Prinzip so wie beim endlichen Automaten.
Und wir sagen dann, dass eine Sprache entscheidbar ist, anderes Wort
ist rekursiv, wenn es eine Turing-Maschine gibt, die auf allen
Eingaben stoppt und eine Eingabe W genau dann akzeptiert, wenn W aus
der Sprache ist.
Also hier geht es jetzt um sozusagen den Begriff Berechenbarkeit.
Im Zusammenhang mit Sprachen nennt man das Entscheidbarkeit.
Sie werden gleich auch den Begriff Berechenbarkeit kennenlernen.
Und es gibt jetzt sozusagen zwei Varianten.
Es kann sein, dass eine Turing-Maschine einer vorgegebenen Sprache auf
allen Eingaben hält und genau auf den Eingaben aus der Sprache in
einem akzeptierenden Endzustand hält.
Wenn es zu einer Sprache so eine Turing-Maschine gibt, dann heißt die
Sprache entscheidbar.
Es gäbe aber auch die Variante, dass man sagt, naja gut, was bei
Eingaben passiert, die nicht aus der Sprache sind.
Das interessiert uns nicht so.
Da fordern wir nicht unbedingt, dass die Turing-Maschine überhaupt
anhält.
Und eine Sprache heißt dann präkursiv aufzählbar oder semi
-entscheidbar, wenn es eine Turing-Maschine gibt, die genau die
Eingaben w akzeptiert, die aus l sind.
Und hier wird nichts darüber gesagt, was passiert, wenn w nicht in l
ist.
Das heißt also, hier könnte es so sein, dass bei w nicht aus l, also
Eingaben w, die nicht aus l sind, die Turing-Maschine auch gar nicht
anhält.
Diese beiden Konzepte, Entscheidbarkeit einerseits, Semi
-Entscheidbarkeit andererseits, die werden wir genauer betrachten.
Die stehen sozusagen für die intuitiven Begriffe von etwas ist
berechenbar oder nicht so richtig berechenbar, semi-berechenbar oder
gar nicht berechenbar.
Aber wie gesagt, das müssen wir noch genauer definieren.
Um jetzt über die Arbeitsweise einer Turing-Maschine reden zu können,
brauchen wir noch eine Notation, die im Prinzip beschreibt, wie ein
einzelner Zustand einer Abarbeitung der Turing-Maschine aussieht oder
wie man den kompakt beschreiben kann.
Das ist die Notation oder der Begriff der Konfiguration.
Wenn man uns eine spezielle Situation in der sich eine Turing-Maschine
M befinden kann anguckt, dann kann man diese Situation durch die
sogenannte Konfiguration beschreiben und eine Konfiguration sieht also
so aus, das ist ein Wort gefolgt von einem Zustand Q in Klammern,
gefolgt von einem Symbol, gefolgt von einem Wort.
Also eine Konfiguration hat die Form W, Q in Klammern, A, V, wobei W
und V eben Worte über dem Bandalphabet sind, A ein Symbol aus dem
Bandalphabet ist und Q ein Zustand.
Und was wird damit beschrieben mit W, Q in Klammern, A, V?
Damit wird beschrieben, dass zu diesem Zeitpunkt durch die
Konfiguration W, Q, A, V beschrieben wird.
Die Turing-Maschine sich gerade im Zustand Q befindet.
An der Stelle, wo der Lese-Schreibkopf steht, das Symbol A steht.
Links vom Lese-Schreibkopf das Wort W steht und rechts vom Lese
-Schreibkopf das Wort V steht.
Also dass wir Q gerade an die Stelle schreiben zwischen W und A, V
signalisiert oder zeigt oder kodiert, dass links vom Lese-Schreibkopf
das Wort W steht.
Der Lese-Schreibkopf direkt an der Stelle, wo der Lese-Schreibkopf
steht, das Symbol A steht und rechts daneben V.
Und dann muss man halt noch dazu sagen, in welchem Zustand die Turing
-Maschine ist und das ist eben gerade dann Q bei dieser Konfiguration.
Das ist ganz einfach.
Schauen wir uns einfach mal an, wie man dann eben eine Abarbeitung
einer speziellen Eingabe für eine spezielle Turing-Maschine über die
Konfiguration, die die Turing-Maschine durchläuft, beschreiben kann.
Wir haben hier eine Turing-Maschine, die sieht so aus.
Wenn eine 0 gelesen wird, bleiben wir im Anfangszustand S und gehen 1
nach rechts.
Das passiert so lange, bis eine 1 gesehen wird.
Dann gehen wir in den Zustand Q1, gehen wieder 1 nach rechts.
Soweit ist auch noch nichts geändert worden an der Eingabe.
Wenn dann im Zustand Q1 eine 1 gelesen wird, geht man wieder weiter
nach rechts, ändert nichts an der Eingabe, bis man an dem Ende der
Eingabe angekommen ist, also ein Blank gelesen wird.
Das Blank wird auch unverändert gelassen.
Die Turing-Maschine geht vom Zustand Q1 in den Zustand Q2 über und
geht wieder nach links.
Also von hier nach da bis wir hier hinkommen, sind wir sozusagen
einmal von links nach rechts über das Wort gegangen.
Und dann beim Zustand Q2 passiert folgendes, wenn eine 1 gelesen wird,
wird diese 1 durch ein Blank überschrieben und 1 nach links gegangen.
Und die Turing-Maschine geht in den Zustand Q3 und im Zustand Q3 wird
nichts anderes gemacht, als nach vorne zu gehen.
Also egal, ob dann eine 0 oder eine 1 gelesen wird, die 0 oder 1 wird
auf dem Band unverändert gelassen und dieser Schreibtopf geht nach
vorne.
Wenn wir hier waren, sind wir ganz nach rechts gegangen, gehen dann in
den Zustand und gehen hier wieder ganz nach links.
Also rechts haben wir die 1 gelöscht, dann gehen wir ganz nach links.
Und wenn wir ganz links am Anfang des Wortes angekommen sind und an
der Stelle davor, da steht ja dann ein Blank, gehen wir in den Zustand
Q4 über, lassen das Blank unverändert und gehen wieder nach rechts.
Wenn da eine 0 gelesen wird, wird die 0 durch ein Blank überschrieben,
nach Q5 gegangen und dann wird, je nachdem was gelesen wird, entweder
nach Q6 gegangen und die Eingabe unverändert gelassen, nämlich wenn da
ein 1 und ein 0 steht, oder wenn da ein Blank steht, wird in den
akzeptierenden Endzustand gegangen.
Und ansonsten, wenn da noch nicht ein Blank stand, dann gehen wir
wieder nach rechts, bei dem Übergang von Q5 nach Q6 und bei den
Übergängen von nach Q6 gehen wir wieder über die Eingabe ganz nach
rechts, verändern die Eingabe nicht, bis wir am Ende angekommen sind
und kommen dann wieder in unseren Zustand Q2 der genau dann, wenn eben
wir gehen nach Q2 und wieder 1 nach links und der eben genau dann,
wenn da am rechten Rand, also am Ende der Eingabe eine 1 steht, wieder
diese 1 überschreibt und dann hier durch diesen Zykel führt.
Und was macht dieser Zykel?
Ich habe schon gesagt, man geht nach rechts, wenn man eine 1 liest,
wird die gelöscht und geht wieder nach links und genau dann, wenn ganz
links eine 0 steht, wird die gelöscht.
Das heißt, bei jedem Durchlauf durch den Zykel wird rechts eine 1 und
links eine 0 gelöscht.
Und genau dann, wenn das sozusagen aufgeht und bei diesem Durchlauf
nur noch bei Planks landet, also genauso viele 1 in rechts wie 0 in
links gelöscht wurden, kommt man in den akzeptierenden Endzustand.
Aus dieser Studie dessen, was die Turing-Maschine macht, kann man
ableiten, dass sie also genau die Sprache 0 hoch N, 1 hoch N, N größer
gleich 1 akzeptiert.
Also die Sprache bestehend aus einer Folge von Nullen gefolgt von
einer Folge von Einsen.
Derart, dass die Anzahl der Nullen genau die Anzahl der Einsen ist.
Von dieser Sprache wissen wir, sie ist nicht regulär.
Es gibt keinen endlichen Automaten, der diese Sprache erkennen kann.
Aber offensichtlich gibt es eine Turing-Maschine, die diese Sprache
erkennen kann.
Und jetzt schauen wir uns mal an, sozusagen Schritt für Schritt, was
also diese Turing-Maschine bei einer Eingabe, die da gerade genau
passt, nämlich zwei Nullen gefolgt von zwei Einsen, macht und wie die
Konfigurationen aussehen, die dadurch laufen werden.
Also, sie startet in S und liest 0.
Die Konfiguration, die dies beschreibt, startet mit dem Wort, das
links von der Stelle steht, an der der Lese-Schreibkopf ist.
Das ist Plank, eine Folge von Planks.
Dann wird der Zustand in Klammern angegeben, in dem sich die Turing
-Maschine befindet, das ist S.
Genau daneben wird das Symbol angegeben, das an der Stelle steht, an
dem gerade der Lese-Schreibkopf ist, oder das gerade gelesen wird, das
ist hier die 0, gefolgt von dem Rest des Wortes, das rechts davon
steht.
Das ist 011.
Und was machen wir, wenn wir hier eine 0 lesen?
Wir lassen die unverändert und gehen mit dem Lese-Schreibkopf 1 nach
rechts.
Das heißt, die darauf folgende Konfiguration sieht so aus 0S in
Klammern 011.
Und dann wird wieder eine 0 gelesen und dann bleibt man wieder im
Zustand S und der Lese-Schreibkopf geht 1 nach rechts, das heißt,
darauf folgt dann die Konfiguration 00 S1 in Klammern 11.
Das heißt, da wo der Lese-Schreibkopf ist, da steht eine 1, rechts
davon eine weitere 1 und links davon 2 Nullen.
Wir sind im Zustand S1.
So, wenn jetzt im Zustand S1 eine 1 gelesen wird, gehen wir in einen
neuen Zustand über, nämlich in Q1 und der Lese-Schreibkopf geht 1 nach
rechts und ansonsten bleibt das Ganze unverändert.
Das heißt, die darauf folgende Konfiguration ist dann 001 Q1 gefolgt
von 1.
Was ich hier nicht dazu schreibe, ist, dass danach dann lauter Planks
kommen.
So, im Zustand Q1 wird, wenn eine 1 gelesen wird, diese 1 unverändert
gelassen, wir bleiben im Zustand Q1, der Lese-Schreibkopf geht 1 nach
rechts.
Das heißt, die folgende Konfiguration sieht dann so aus 0011 Zustand
Q1 Plank.
So, wenn jetzt ein Plank gelesen wird im Zustand Q1, dann gehen wir in
den Zustand Q2 über das Plank wird unverändert gelassen und der Lese
-Schreibkopf geht wieder 1 nach links.
Das heißt also, die folgende Konfiguration sieht dann so aus 001
Zustand Q2, Lese-Schreibkopf steht an der 1.
Rechts davon nur Planks.
So, bei Q2 ist es so, wenn eine 1 gelesen wird, wird diese 1 durch
einen Plank überschrieben und wir gehen mit dem Lese-Schreibkopf 1
nach links und der neue Zustand ist Q3.
Das heißt also, auf diese Konfiguration folgt die Konfiguration 00 Q3
1.
In Q3 ist es ja so, wenn 0 oder 1 gelesen wird, gehen wir einfach nach
links.
Die Eingabe bleibt unverändert.
Das heißt also, was dann gefolgt ist, hier 1 nach links rücken, also
die Konfiguration 0 Q3, gefolgt von 01 und dann wieder wenn wir hier
eine 0 lesen, 1 nach links rücken, also Plank Q3 001 und dann wenn wir
jetzt die 0 lesen, wieder bleiben unverändert in Q3 gehen 1 nach
links, also Plank Q3 Plank 001.
So, jetzt wird ein Plank gelesen, wenn in dem Zustand Q3 ein Plank
gelesen wird, gehen wir nach Q4.
Plank wird unverändert gelassen und der Lese-Schreibkopf geht wieder 1
nach rechts.
Das heißt, es folgt dann die Konfiguration Plank Q4, gefolgt von 001.
Und in Q4 wird jetzt auch die Eingabe wieder verändert, nämlich wenn
dann eine 0 gelesen wird, wird die 0 durch ein Plank überschrieben und
1 nach rechts gegangen.
Hier wird tatsächlich... und in Q5 übergegangen.
Hier wird tatsächlich eine 0 gelesen.
Das heißt also, die folgende Konfiguration ist Plank Q5 01.
Und wenn wir in Q5 eine 0 lesen, wird die unverändert gelassen.
Wir gehen nach Q6 und es wird einfach 1 nach rechts gegangen.
Das heißt also, darauf folgt die Konfiguration 0 Q6 1.
Wenn wir Q6 0 oder 1 lesen, wird einfach nach rechts gegangen.
Die Eingabe unverändert gelassen.
Das heißt also, danach ist die Konfiguration 01 Q6 Plank.
So, jetzt wird ein Plank gelesen.
Wenn wir im Zustand Q6 ein Plank lesen, dann gehen wir einfach wieder
nach links und gehen in den Zustand Q2.
Das heißt, darauf folgt dann die Konfiguration 0 Q2 1.
Und dann geht es wieder hier durch den Zykel durch.
Das gehe ich jetzt nicht einzeln durch, bis wir tatsächlich bei Q5 ein
Plank lesen.
Dann gehen wir nach rechts und in den akzeptierenden Endzustand.
Okay.
Gut.
Das heißt also, über diese Mutation, Konfiguration kann man die
Berechnung einer Turing-Maschine zu einer konkreten Eingabe
vollständig beschreiben.
Okay.
Bisher haben wir nur darauf geschaut, ob zu einer bestimmten Eingabe
die Turing-Maschine in einem akzeptierenden Endzustand endet oder
nicht.
Gar nicht endet oder in einem nicht akzeptierenden Zustand hält.
Wir haben aber hier an dem Beispiel gesehen, dass die Turing-Maschine
auch das, was auf dem Band als Eingabe steht, verändert.
Hier bei diesem Beispiel wurde die Eingabe letztendlich gelöscht.
Das ist nicht sonderlich spannend, aber man könnte sich ja auch
anderes vorstellen.
Und dann wären wir bei der Sichtweise, zu einer Eingabe wird eine
Ausgabe produziert.
Was ja eigentlich das Interesse ist, dass ein Rechner zu einer Eingabe
eine bestimmte Ausgabe produziert.
Das kann man mit der Turing-Maschine eben auch formal fassen.
Nämlich das, was da passiert, wir geben eine bestimmte Eingabe rein,
die Turing-Maschine verändert das, was da auf dem Band als Eingabe
steht und hält dann am Schluss mit irgendeiner Ausgabe auf dem Band.
Das kann man interpretieren als die Realisierung einer Funktion.
Und entsprechend sagen wir, eine Funktion, die von den Worten über dem
Eingabe -Alphabet in die Menge der Worte über dem Band-Alphabet führt,
heißt Turing-berechenbar oder total rekursiv.
Wenn es eine Turing-Maschine gibt, die bei Eingabe von irgend so einem
Wort aus Sigma-Sternchen gerade den Funktionswert f von dem Wort, das
ist was aus Gamma-Sternchen, ausgibt.
Wenn also bei Eingabe w am Schluss f von w auf dem Band steht.
Und wir sagen dann eben auch, die Turing-Maschine realisiert oder eine
Turing -Maschine realisiert so eine Funktion f von Sigma-Stern nach
Gamma -Stern, falls gilt, dass f von w ist eben genau die Ausgabe der
Turing -Maschine, wenn sie bei Eingabe w stoppt und wenn sie nicht
stoppt, umdefiniert.
Und hier haben wir mal ein Beispiel einer solchen Turing-Maschine, die
eine sinnvolle Ausgabe zu einer Eingabe produziert.
Das Eingabe-Alphabet ist 0,1 0,1, ein Wort über 0,1 kann man natürlich
als binäre Zahl interpretieren.
Und genau das macht die Turing-Maschine hier.
Sie interpretiert die Eingabe als eine binäre Zahl und akzeptiert
genau solche Eingaben, die entweder nur die 0 sind, also die Eingabe,
die nur aus 0 besteht, oder keine führende 0 haben.
Und was macht sie mit der Eingabe?
Sie addiert eine 1 drauf.
Das ist das, was hier passiert.
Schauen wir uns das mal genauer an.
Wenn bei s eine 0 gelesen wird, bleibt die 0 auf dem Band stehen.
Der Lese-Schreibkopf geht 1 nach rechts und die Turing-Maschine geht
in den Zustand Q4 über.
Wenn in Q4 danach Plank gelesen wird, dann war also die Eingabe nur
die 0, bleibt das Plank unverändert und der Lese-Schreibkopf geht
wieder 1 nach links und die Turing-Maschine geht in Q5 über.
Dort liest sie dann 0, diese 0, die hier am Anfang gelesen wird.
Diese 0 wird in 1 geändert.
Der Lese-Schreibkopf geht wieder 1 nach links und die Turing-Maschine
geht in den akzeptierenden Endzustand.
Das heißt, wenn die Eingabe 0 war, ist die Ausgabe tatsächlich 1.
Also erstmal die Eingabe wird akzeptiert.
Wir enden im akzeptierenden Endzustand F und das, was auf dem Band
danach steht, ist die 1.
Gut, das war jetzt noch der einfache Fall.
Die einzige andere Möglichkeit, wo die Turing-Maschine etwas macht,
also nicht total undefiniert ist, ist, wenn sie als allererstes eine 1
liest.
Und was macht sie dann?
Sie lässt die 1 unverändert stehen, geht 1 nach rechts und geht in den
Zustand Q1 über.
Bei dem Zustand Q1 passiert nichts anderes, als dass ganz ans Ende der
Eingabe gegangen wird.
Wird 1 oder 0 gelesen, unverändert gelassen, mit dem Lese-Schreibkopf
1 nach rechts gegangen, in Q1 geblieben.
Es wird nichts anderes gemacht, als ganz nach rechts ans Ende der
Eingabe gegangen oder die Eingabe vollständig gelesen.
Wenn wir dann am Ende der Eingabe sind, dann folgt ein Blank-Symbol.
Dieses Blank-Symbol wird unverändert gelassen.
Wir gehen wieder 1 zurück, an die letzte Stelle der Eingabe und in den
Zustand Q2.
Wenn ganz hinten eine 1 stand, wird stattdessen eine 0 geschrieben, 1
nach vorne gegangen und wieder nach Q2 gegangen oder in Q2 geblieben.
Und in Q2 ist, solange da eine 1 gelesen wird, passiert immer
dasselbe.
Es wird diese 1 durch eine 0 überschrieben und 1 nach vorne gegangen.
Das geschieht so lange, bis irgendwo eine 0 gelesen wird.
Diese 0 wird zu einer 1 gemacht.
Noch 1 weiter nach vorne gegangen und dann nach Q3 gegangen, wo nichts
anderes passiert, als dass Nullen und Einsen gelesen und unverändert
gelassen werden und immer weiter nach vorne gegangen wird.
Bis man an einem Blank ankommt und dieses Blank führt uns dann zum
akzeptierenden Endzustand.
Was wäre in dem Fall passiert?
Wir haben eine Eingabe, da hinten sind Einsen.
Wenn man eine 1 aufsummiert, wird die 1 zu einer 0 und man muss einen
Übertrag sich merken.
Das heißt, wenn eine weitere 1 kommt, wird wieder die 1 zu einer 0 und
man muss sich den Übertrag merken.
Und das ist das, was hier genau passiert.
Solange, bis man vorne angekommen ist
oder solange, bis man irgendwann die Chance hat oder irgendwann eine 0
steht und da den Übertrag los wird und danach bleibt alles
unverändert.
Andere Möglichkeit ist, die ganze Eingabe besteht nur aus Einsen.
Da würden alle diese Einsen immer durch eine 0 ersetzt, bis wir ganz
vorne angekommen sind, das heißt also an dem Symbol vor der Eingabe,
das ist ein Blank-Symbol, und dort unseren Übertrag loswerden, also
dort dann eine 1 hinschreiben.
Man könnte sagen, sie bleibt jetzt irgendwo stehen, aber die
Konvention guckt sich nicht mehr den Rest der Eingabe nochmal an, aber
die Konvention sagt, sie soll in jedem Fall egal, ob der Übertrag an
einem Blank losgeworden wurde oder bei einer 0 losgeworden wurde, ganz
nach vorne wieder gehen.
Das ist richtig beobachten.
Hier haben wir auch nochmal hingeschrieben, welche Funktion also
realisiert wird.
Ja, das ist richtig.
Es steht 1 vor dem Wort.
Gut, das Wort hat eine gewisse Länge, das hat irgendwie mit irgendwas
gestartet.
Danach steht sie auf jeden Fall 1 vor dem Wort.
Also entweder wird das sozusagen das, was vor dem Wort stand, das
Blank durch eine 1 überschrieben oder es bleibt unverändert.
Und da steht sie.
So, und die Funktion, die realisiert wird, ist eben, die Eingabe wird
als Binärzahl aufgefasst und es wird eine 1 drauf addiert.
Beziehungsweise, es wird eine 1 drauf addiert und es wird aber auch
nur gemacht bei Binärzahlen, die so aussehen, entweder ist die
Binärzahl die 0 oder eine Zahl beginnend mit einer 1.
Das ist keine Einschränkung an das, was die Turing-Maschine im Prinzip
kann, denn für jede Binärzahl ist im Prinzip interessant, das was
passiert ab der ersten 1.
Aber das ist jetzt einfach per Konvention so, dass wir sagen, hier
wollen wir nur Eingaben akzeptieren, die folgendermaßen aussehen, das
ist die 0 oder das ist eine Binärzahl, die mit einer 1 beginnt.
Und wenn dem nicht so ist, dann ist das, was diese Turing-Maschine
macht, dass sie die Eingabe auf undefiniert abbildet.
Das passiert bei so einer Eingabe, die eben nicht 0 ist oder mit einer
1 startet, nicht definiert ist.
Und die Zustände, um das nochmal zu beschreiben, haben verschiedene
Aufgaben.
Innerhalb von Q1 oder solange wir in Q1 sind, passiert nichts anderes,
als dass der Leseschreibkopf bis ans Ende der Eingabe geht.
Q2 ist zuständig für die Bildung des Übertrags durch Addition von
einer 1 zu einer bereits vorhandenen 1.
Q3 ist zuständig für die Bewegung des Leseschreibkopfes nach links,
nachdem eben die Aufsummierung abgeschlossen ist, also kein Übertrag
mehr untergebracht werden muss.
Und Q4 und Q5 sind sozusagen die Sonderbehandlung für den Fall, dass
die Eingabe nur die 0 ist und F ist der akzeptierende Endzustand.
Entscheidbarkeit von Sprachen und Berechenbarkeit von Funktionen kann
man auch direkt als Konzepte zusammenbringen.
Was heißt nochmal Entscheidbarkeit einer Sprache?
Also eine Turing-Maschine akzeptiert eine Sprache, wenn sie genau auf
den Eingaben aus der Sprache in einem ausgezeichneten Endzustand
stoppt.
Und eine Sprache heißt entscheidbar, wenn es eine Turing-Maschine
gibt, die auf allen Eingaben stoppt und genau diese Sprache
akzeptiert.
Und andererseits heißt eine Funktion berechenbar, wenn es eine Turing
-Maschine gibt, die gerade diese Funktion realisiert.
Und wieso sind diese beiden Konzepte gleich?
Naja gut, vielleicht machen wir jetzt erstmal eine Festlegung, die der
Vereinfachung dient, wenn man über Turing-Maschinen spricht.
Man kann eine Turing-Maschine, die auf allen Eingaben stoppt, immer so
modifizieren, dass sie genau zwei ausgezeichnete Zustände hat, auf
denen gestoppt wird.
Der eine heißt Qj für Qja und der andere heißt Qn für Qnein.
Und das Stoppen heißt in dem einen Fall, wenn in Qj gestoppt wird,
akzeptieren und im anderen Fall, naja, nicht akzeptieren.
Also wenn die Turing-Maschine bei allen Eingaben stoppt, dann kann man
sozusagen für die einen, die akzeptierenden, nach Qj noch den Übergang
machen und für die anderen, die nicht akzeptieren, nach Qn.
Das heißt, Qj hat sozusagen die Rolle akzeptierender Endzustand und Qn
die andere Möglichkeit, zu stoppen.
Dann ist eine Sprache genau dann entscheidbar, wenn es eine Turing
-Maschine gibt, die immer in einem dieser Zustände Qj oder Qn anhält,
also egal wie die Eingabe aussieht, in Qj oder Qn anhält und gerade
für die Eingaben W aus L in Qj anhält.
Und mit dieser Turing-Maschine, die zwei Haltezustände kennt, einen
akzeptierenden Qj und einen nicht akzeptierenden Qn, kann man 1 zu 1
übersetzen in eine Turing-Maschine, die in dem einen Fall eine 1 als
Ausgabe produziert und in dem anderen Fall eine 0 als Ausgabe
produziert.
Also dann kann man das übersetzen in eine Sprache ist entscheidbar
genau dann, wenn ihre charakteristische Funktion berechenbar ist.
Und charakteristische Funktion das ist gerade die Funktion, die die
Worte aus L auf 1 abbildet und die anderen auf 0.
Das heißt also, Berechenbarkeit dieser Funktion ist genau dasselbe wie
Entscheidbarkeit der entsprechenden Sprache oder Entscheidbarkeit der
Sprache L ist dasselbe wie Berechenbarkeit der charakteristischen
Funktion zu L.
Gut, jetzt gibt es ja auch Sprachen, vermutlich zumindest, die semi
-entscheidbar sind.
Da haben wir nur dieses Halten in einem ausgezeichneten Zustand für
den Fall, dass die Eingabe aus der Sprache ist.
Im anderen Fall kann auch passieren, dass die Turing-Maschine
überhaupt nicht hält.
Da wird also dann eine Funktion berechnet, die eben gerade die Wörter
aus L auf 1 abbildet, aber für andere Wörter undefiniert ist.
Also, entscheidbar, semi-entscheidbar und Berechenbarkeit der
charakteristischen Funktion und dieser, ich sag mal, abgewandelten
charakteristischen Funktion Schießstern L kann man sozusagen in
Einklang bringen.
Aber wir werden meistens nur über Akzeptieren von Sprachen oder nicht
Akzeptieren von Sprachen reden.
So, die Churchill-These, ganz wichtig, die besagt jetzt, die Menge der
Turing -berechenbaren Funktionen ist genau die Menge der im intuitiven
Sinne überhaupt berechenbaren Funktionen.
Das ist eine These, das ist kein Satz, das kann man nicht beweisen,
aber das ist eine These, die etwas darüber aussagt, ob die Turing
-Maschine das Modell ist für das, was wir intuitiv sozusagen als
Berechnen auffassen.
Hier ist intuitiv berechenbar oder im intuitiven Sinne überhaupt
berechenbare Funktion ein Begriff, der an unsere Intuition anspricht
und der nicht definiert ist.
Die Interpretation der Turing-Maschine sind formale Modelle für
Algorithmen.
Das ist letztendlich das, was uns interessiert, ein abstraktes,
möglichst einfach zu beschreibendes Modell dafür, was ein Algorithmus
macht.
Zugegebenermaßen ist die Turing-Maschine relativ weit entfernt erstmal
von dem, was wir uns unter einem Algorithmus vorstellen.
Die Random Access-Maschine ist da deutlich näher dran, aber für
Beweise über Berechenbarkeit oder Komplexität von Problemen ist die
Turing -Maschine ein geeignetes Modell.
Die Churchill-These sagt eben, ja, und die ist auch das Modell, das
sozusagen den Berechenbarkeitsbegriff abstrahiert.
Und sie sagt, kein Berechnungsverfahren kann algorithmisch genannt
werden, wenn es nicht von einer Turing-Maschine ausführbar ist.
Also nochmal, die Churchill-These ist ohne eine präzise Definition von
intuitiv, berechenbar nicht beweisbar.
Es ist nur eine These.
Sie wird aber in der Informatik allgemein akzeptiert.
Wenn man über Berechnungsmodelle spricht, dann ist die Turing-Maschine
nach wie vor das Modell, das alles das, was wir uns als Computer, den
man bauen kann, technisch realisieren kann, sozusagen abstrahiert.
Und das bleibt auch unverändert trotz Quantencomputer oder anderer
Entwicklungen oder biologischer Computer.
Bisher gibt es keinen Hinweis darauf, dass es einen Rechner geben
wird, Rechner in welchem Sinn auch immer, der nicht durch die Turing
-Maschine abstrahiert.
Das steht hier also nochmal.
Keine Beispiele von Funktionen, die man intuitiv als berechenbar
ansehen würde, die aber nicht Turing-berechenbar sind.
Das ist die eine Seite.
Und auf der anderen Seite Versuche, Modelle, Abstraktionen von echten
Computern aufzustellen, die mächtiger sind als Turing-Maschinen, das
fliegen alle fehl.
Das führt immer wieder auf diese einfache Turing-Maschine mit ihrem
Einband und ihrem Lese-Schreibkopf in ihren Zuständen, ihrer
Übergangsfunktion.
Das ist ja wirklich ein ganz, ganz primitives Modell.
Und man kann insbesondere auch für die andersartigen Ansätze, die
Abstraktionen eines Computers zu definieren, immer zeigen, was diese
Maschine kann, ist entweder weniger mächtig als das, was eine Turing
-Maschine kann, oder eben äquivalent zu einer Turing-Maschine,
sozusagen simulierbar durch eine Turing-Maschine, wie zum Beispiel die
Register -Maschine.
Und einfach nur der Vollständigkeit halber dann schnell für Varianten
der Turing-Maschinen, die man auch betrachten kann, die aber alle
immer durch eine Einband-Turing-Maschine mit einem Lese-Schreibkopf,
wie wir es hier betrachten, simuliert werden kann.
Zum Beispiel eine Turing-Maschine mit einem Band, die aber mehrere
Lese -Schreibköpfe hat.
Meinetwegen Endstück.
Die auf das Eingabeband zugreifen und durch eine endliche Kontrolle
gesteuert werden.
Das schlägt sich halt darin nieder, wie die Übergangsfunktion
aussieht.
Da hat man dann statt einem Übergang von Q kreuz Gamma einen Übergang
von Q kreuz Gamma hoch N.
Jeder, der N Lese-Schreibköpfe, liest irgendein Symbol aus Gamma und
abhängig von diesem N-Tuppel von Symbolen und dem Zustand, in dem die
Turing -Maschine ist, wird was gemacht.
Und was wird gemacht?
Gut, es wird mit einem neuen Zustand übergegangen und an diesen N
Stellen, an denen Lese-Schreibköpfe stehen, wird das Symbol
überschrieben und es wird dann mit jedem Lese-Schreibkopf nach links
oder nach rechts gegangen oder gar nichts gemacht.
Das heißt also, der Übergang geht nach Q kreuz Gamma hoch N kreuz
Menge L für links, N für nichts, R für rechts hoch N.
Ja, man könnte sich das natürlich so vorstellen, dass man diese
Zustände für jeden dieser Lese-Schreibköpfe sozusagen sagt, was wird
jetzt in Abhängigkeit von dem, was du jetzt liest, gemacht.
Kann man als N-Tuppel auffassen.
An jeder Stelle steht jeweils, wie der Zustand zu interpretieren ist,
in Abhängigkeit von dem, was der entsprechende Lese-Schreibkopf liest.
Und natürlich muss man hier noch ein paar weitere Festlegungen
treffen.
Wenn zwei Lese-Schreibköpfe an derselben Stelle stehen und der eine
bei Lesen des entsprechenden Symbols vielleicht das eine schreiben
würde und der andere das andere, dann gäbe es ja einen Konflikt oder
haut das nicht hin.
Also hier muss man natürlich dann irgendwelche Prioritätsregeln auch
noch festlegen, was in so einem Fall passiert, damit das wirklich eine
wohl definierte, arbeitende Turing-Maschine ist.
Sie können sich genauso so ein Konzept vorstellen von einer Turing
-Maschine, die mehrere Bänder hat und noch mal ein Lese-Schreibkopf,
der auf jedes dieser Bänder zugreifen kann.
Die Übergangsfunktion ist dann so, Delta geht von Q-Kreuz, Gamma
-Kreuz, 1 bis N, 1 bis N für die N-Bänder über zu Q-Kreuz, Gamma
-Kreuz, links, rechts, N-Kreuz, 1 bis N also in Abhängigkeit von dem
Zustand und dem, was gelesen wird auf dem Band, wo man gerade ist wird
in einen neuen Zustand übergegangen an der Stelle, an dem die Lese
-Schreibkopf gerade war, ein neues Symbol geschrieben oder Symbol
überschrieben, nach links oder rechts gegangen oder stehen geblieben
und das möglicherweise bei einem anderen Band eins nach unten gegangen
oder nach oben eins nach rechts
und das kann man sich jetzt natürlich auch so vorstellen, dass man
diese N-Bänder hat und für jedes Band einen eigenen Lese-Schreibkopf
und dann ist die Übergangsfunktion Delta eine, die von Q-Kreuz, Gamma
-Hoch, N-Kreuz, 1 bis M-Hoch, N geht nach Q-Kreuz, Gamma-Hoch, N
-Kreuz, L N, R-Hoch, N-Kreuz, 1 bis M-Hoch, N oder aber das Band ist
nicht nur einfach so ein eindimensionales Band, sondern ein
zweidimensionales Feld und der Lese-Schreibkopf, also wir haben jetzt
wieder nur einen Lese-Schreibkopf kann nicht nur nach links und rechts
gehen, sondern auch nach oben und unten.
Dann sieht also die Übergangsfunktion so aus.
Wir haben eben nicht ein Arbeitsband, sondern ein Arbeitsfeld.
Und, und, und.
Das war jetzt nur mal so ganz grob, was man sich so alles vorstellen
kann.
Festgelegt werden muss zum Beispiel, wann so eine Mehrkopfmaschine
dann wirklich stoppen würde, welcher Kopf gewinnt, wenn es irgendwie
Konflikte gibt, also mehrere Lese-Schreibköpfe verschiedene Symbole an
die selbe Stelle schreiben würden und so weiter.
Sowas muss bei diesen Modifikationen der Einband-Turing-Maschine
geklärt werden.
Aber egal, wie Sie sich das sinnvoll vorstellen oder was Sie da
sinnvoll im Konzept aufstellen, alle diese Modelle sind äquivalent zur
normalen Turing-Maschine.
Und äquivalent sein, ich gehe mal davon aus, dass das in der Übung
dann auch vertieft wird, heißt, man kann das, was die eine Turing
-Maschine macht, durch die andere simulieren.
Also das, was irgendwie eine Mehrband-Turing-Maschine macht, durch so
eine Einband-Turing-Maschine mit einem Lese-Schreibkopf, wie wir sie
hier immer betrachten, simulieren.
Gut, jetzt haben wir bisher, wie beim endlichen Automat, auch immer
eine ganz spezifische Turing-Maschine betrachtet.
Die kann eine einzige Aufgabe erfüllen, eine bestimmte Sprache
akzeptieren oder nicht, eine bestimmte Funktion berechnen oder nicht.
Das ist ja noch was anderes als das, was ein Computer kann, der
durchaus unterschiedliche Funktionen berechnen kann.
Was so eine Turing-Maschine macht, entspricht eher einem konkreten
Programm oder einer Realisierung eines bestimmten Lösungsalgorithmus
auf einem Chip, der genau einen bestimmten Algorithmus durchführen
kann.
Aber wir wollen doch über universelle Maschinen Aussagen treffen, also
eine Maschine, der man ein Programm gibt, und dann eine Eingabe, auf
der dieses Programm abläuft.
Das ist jetzt der nächste große Schritt, dass wir die universelle
Turing -Maschine definieren, die praktisch die verschiedensten
konkreten Turing-Maschinen, wie wir sie bisher betrachtet haben,
realisieren kann.
Das heißt, diese Turing-Maschinen, die wir so bisher betrachtet haben,
spezielle Turing-Maschinen, die auch so eine Binärzahl 1 addiert oder
die 0 hoch n, 1 hoch n erkennen kann, als Programm auffassen und eine
Turing -Maschine betrachten, die so ein Programm bekommt und dann
genau das macht, was diese spezielle Turing-Maschine, die durch das
Programm beschrieben wird, tun würde bei einer bestimmten Eingabe.
Und um das hinzubekommen, also sozusagen das Denkmodell einer
universellen Turing-Maschine, normieren wir Turing-Maschinen.
Also spezielle Turing-Maschinen normieren wir in dem Sinne, dass wir
sagen, naja, die sehen alle irgendwie gleichartig aus.
Wir wollen ja eine spezielle Turing-Maschine im Prinzip als ein
Programm ausdrücken.
Das heißt, wir müssen es irgendwie kodieren als etwas, was wir der
universellen Turing-Maschine als Eingabe geben.
Hier, tu folgendes.
Dafür also jetzt die Normierung der Turing-Maschine und Normierung
heißt, naja, gewisse Festlegungen, die Zustände werden durchnummeriert
von Q1 bis Qn und der erste, Q1, ist gerade der Startzustand und der
zweite, Q2, ist der akzeptierende Endzustand, wenn wir sowas festlegen
wollen.
Und genauso wird das Eingabe-Alphabet einfach durchnummeriert.
Das sind die Symbole A1 bis AK.
Und für das Band-Alphabet gilt, die ersten K-Symbole sind gerade diese
Symbole aus Sigma, A1 bis AK, und dann folgen die weiteren, AK plus 1
bis AL.
Und wenn wir das so machen, ist das natürlich keine Einschränkung der
Mächtigkeit einer Turing-Maschine.
Man kann bei jeder beliebigen Turing-Maschine das so hinkriegen, dass
sie diese Form hat, durch Unbenennung.
Anderes wird hier noch nicht gemacht.
Das Gute aber ist, dass man eine so normierte Turing-Maschine kodieren
kann als 0,1-Wort.
Das ist jetzt ganz wichtig.
Eine normierte Turing-Maschine M lässt sich eindeutig als Wort über 0
,1 Sternchen kodieren.
Wie geht das?
Was macht eine Turing-Maschine aus?
Was die Arbeitsweise einer Turing-Maschine oder die Arbeit einer
Turing -Maschine ausmacht, ist eben, welche Übergänge sie macht bei
bestimmten Konfigurationen.
Was ist die Konfiguration, die auf eine bestimmte Konfiguration folgt?
Das heißt, wenn wir eine Turing-Maschine M haben, bestehend aus
Zustandsmenge Q, Sigma, Gamma, Delta, S und F, dann wollen wir die
durch 0,1 kodieren und diese 0,1-Kodierung heißt Gödelnummer von M,
bezeichnet auch als M in diesen eckigen Klammern.
Dann ist dafür diese Kodierung wichtig und das Entscheidende, wie die
Übergänge sind.
Alle denkbaren Übergänge müssen kodiert werden.
Ein Übergang sieht allgemein so aus.
Turing-Maschine ist in irgendeinem Zustand QI und es wird AJ gelesen.
Und dieses Delta, die Übergangsfunktion, sagt was dann passiert,
nämlich die Turing-Maschine geht in den Zustand QR, AJ wird durch AS
überschrieben und der Lese-Schreibkopf macht eine von drei möglichen
Bewegungen, links, rechts oder tue gar nichts, die man auch kodieren
kann als links ist die erste Möglichkeit, also Index 1, rechts ist die
zweite Möglichkeit, Index 2 und nichts tun ist die dritte Möglichkeit,
Index 3.
Das heißt, worauf es hier ankommt, sind ja eigentlich nur die Indizes,
die da stehen.
Wir haben die Zustände durchnummeriert und die Nummer des Zustands,
wievielte in unserer Nummerierung bei der Nummerierung ist das, ist
eigentlich nur entscheidend.
Genauso bei einem Symbol, das wir lesen, das wievielte in unserer
Nummerierung ist das und für das, was danach passiert, ist genauso nur
entscheidend für den Zustand, in den wir gehen, der wievielte ist das
denn in unserer Nummerierung.
Für das Symbol, das beschrieben wird, das wievielte ist es denn aus
unserem Bandalphabet und für die Aktion, die gemacht wird, die
wievielte von den drei Möglichkeiten ist es eigentlich.
Das heißt also, so einen Übergang kann man nummieren als so viele
Nullen, wie der Index von dem Zustand ist, in dem wir uns befinden,
gefolgt von einer 1, um klarzustellen, jetzt ist der Zustand codiert,
gefolgt von so vielen Nullen, wie der Index des Symbols, das gerade
gelesen wird, gefolgt von einer 1, um zu sagen, okay, jetzt haben wir
also die Codierung von dem Zustand, in dem die Turing-Maschine ist,
und die Codierung des Symbols, das sie gelesen hat, und was jetzt
kommt, ist eben das, was die Folge von dem ist.
Also gefolgt dann von so vielen Nullen, wie der Index des
Folgezustands ist, gefolgt von einer 1, weil die Einsen haben hier nur
die Funktion zu trennen, Trennsymbol zu sein, gefolgt von so vielen
Nullen, wie der Index des Symbols ist, das jetzt hier geschrieben
wird, also mit dem aj überschrieben wird, also s, as, 0 hoch s,
gefolgt von einer 1, gefolgt von so vielen Nullen, wie der Index der
Aktion ist, die jetzt gemacht wird.
Das ist ganz einfach.
So, und wenn Sie jetzt alle möglichen Übergänge, die die Turing
-Maschine machen kann, jeweils so codieren, und in irgendeiner
beliebigen Reihenfolge hintereinander schreiben und dann zwischen
Codierung von einem Übergang und dem nächsten einfach nur zwei Einsen
schreiben als Trennsymbol und dann vielleicht noch vorne drei Einsen,
um zu zeigen, jetzt geht's los, jetzt kommt die Codierung einer Turing
-Maschine und am Schluss drei Einsen, um zu codieren, und jetzt ist
Schluss, jetzt ist die vollständig beschrieben, dann haben Sie die
Turing -Maschine codiert durch ein Wort, das nur aus Nullen und Einsen
besteht.
Das ist die Gödelnummer einer Turing-Maschine.
Also, Code i ist einfach der i-te Übergang von allen möglichen
Übergängen, die die Turing-Maschine machen kann, nach irgendeiner
beliebigen, aber festgewählten Reihenfolge der Übergänge.
Codierungen einzelner Übergänge werden getrennt durch zwei Einsen, am
Anfang stehen drei Einsen, am Ende stehen drei Einsen, und das ist die
ganze Codierung.
Das ist die Gödelnummer.
Die können natürlich, die Codierungen, ziemlich lang werden, denn
diese Indizes, die werden einfach durch Nullen codiert.
Das ist eine Unerkodierung.
Nichts mit Binär, das ist einfach unnäher kodiert.
Und die Einsen, die haben eigentlich nur die Funktion, Trennsymbol zu
sein, als Trennsymbol zu dienen.
Jede Turing-Maschine wird auf die Art durch irgendein 01-Wort kodiert.
Wenn Sie jetzt alle möglichen 01-Worte betrachten, sind da natürlich
etliche drunter, die passen nicht zu einer Turing-Maschine, weil die
Codierung einer Turing-Maschine fängt ja immer mit drei Einsen an.
So geht es schon mal los.
Und da ist noch etliches mehr, was irgendwie unpassend sein kann, wenn
Sie ein beliebiges 01-Wort nehmen.
Man kann aber jetzt vereinbaren, dass alle die 01-Worte, die nicht wie
eine Gödelnummer aussehen, einfach eine Turing-Maschine codieren, die
die leere Menge akzeptiert.
Und dann haben Sie eine 1-zu-1-Beziehung zwischen 01-Worten und Turing
-Maschinen.
Wir vereinbaren, dass ein Wort, das keine Turing-Maschine in diesem
Sinne kodiert, Y000, eine Turing-Maschine kodiert, die die leere Menge
akzeptiert.
So, und die universelle Turing-Maschine, die erhält jetzt als Eingabe
so eine Kodierung einer speziellen Turing-Maschine, das kann man
interpretieren als Programm, und dann irgendwie ein Eingabewort.
Und was sie macht ist, sie simuliert diese spezielle Turing-Maschine,
deren Gödelnummer sie als Eingabe bekommen hat, auf dem Eingabewort.
Eine universelle Turing-Maschine erhält als Eingabe ein Paar,
Gödelnummer einer Turing-Maschine, gefolgt von einem Wort W, und wir
gehen jetzt immer nur noch davon aus, dass unser Eingabealphabet 0,1
ist, also W ist eben auch so eine 0,1-Folge, und sie simuliert eben
diese Turing-Maschine M, deren Gödelnummer sie bekommen hat, auf der
Eingabe W.
Hier mal einfach irgend so eine Turing-Maschine, das ist einfach ein
kleines Beispiel, was keinen sonderlichen Sinn machen braucht, und wie
die Codierung dieser Turing-Maschine aussieht, also wie die
Gödelnummer aussieht.
Hier haben wir eine Turing-Maschine mit drei Zuständen, Q1, Q2, Q3.
Zwei Symbolen, 0 und 1.
Jetzt die Indizierung ist, dass es A1 und das ist A2.
Das Plank-Symbol wäre dann A3, kriegt den Index 3.
Das Bandalphabet ist eben 0,1.
Plank-Symbol, Übergangsfunktion Delta, so wie hier beschrieben.
Anfangszustand Q1, akzeptierender Endzustand Q2.
Und hier haben wir so ein paar konkrete Übergänge.
Und wenn man die jetzt kodieren würde, dann sieht die Eingabe für die
universelle Turing-Maschine folgendermaßen aus, wenn man die
Gödelnummer dieser Turing-Maschine zusammen mit der Eingabe 1011
dieser gäbe.
Das geht los mit drei Einsen, dann kommt die Kodierung der Turing
-Maschine, wo eben eine 0 dieses Q1 hier kodiert.
Dann kommt eine 1 als Trend-Symbol.
Dann kommen zwei Nullen, die diese 1 kodieren.
Wir haben unser Bandalphabet durchnummeriert in A1, A2, A3.
A1 ist die 0, A2 ist die 1, A3 ist das Plank-Symbol.
Das heißt also, die 1 wird durch zwei 0 kodiert.
A1 wieder als Trend-Symbol, dann kommt hier Q3, die 3 wird durch die
drei Nullen kodiert.
Dann kommt wieder eine 1 als Trend-Symbol, dann wird diese 0 kodiert,
das ist das A1, also da kommt eine 0, dann wieder eine 1 als Trend
-Symbol.
Dann gehen nach rechts, das war die zweite Möglichkeit der drei
Möglichkeiten, D1, D2, D3, was der Lese-Schreibkopf machen kann.
Also zwei Nullen und dann sind wir mit dem ersten Code fertig.
Das heißt, dann kommen zwei Einsen, um anzuzeigen, was als nächstes
kommt, ist die Kodierung des zweiten Übergangs.
Und dann der zweite Übergang, Delta Q3 0 gleich Q1 1 R, beginnt dann
mit der Kodierung von Q3, das sind drei Nullen, dann wieder eins als
Trend -Symbol, dann Kodierung von der 0, das ist eine 0, dann wieder
eins als Trend-Symbol und so weiter.
Und dann kommen irgendwann diese drei Einsen, die anzeigen, jetzt ist
die Gödel-Nummer unserer eingegebenen Turing-Maschine fertig und was
danach kommt, ist das Eingabewort.
Das heißt, danach kommt dann diese 1 0 1 1, die wir hier als
Eingabeball festgelegt haben.
Also so sähe dann eine Eingabe für eine universelle Turing-Maschine
aus.
In dem Fall die Eingabe, diese Turing-Maschine mit diesem Eingabewort.
Und unsere universelle Turing-Maschine kann dann mit der Information
genau das machen, was diese Turing-Maschine bei dieser Eingabe tun
würde.
Man kann also diese Turing-Maschine auf der Eingabe 1 0 1 1
simulieren.
So, jetzt bezeichnen wir eine spezielle Turing-Maschine, die codiert
wird durch ein Wort W aus 0 1 Sternchen, also deren Gödel-Nummer W
ist, als T und W.
Das ist die Turing-Maschine mit Gödel-Nummer W.
Beziehungsweise, wenn das W keine Gödel-Nummer ist, die Turing
-Maschine, die die Lehrermenge akzeptiert.
Und L von T W ist dann die Sprache, die durch T W akzeptiert wird.
Und worauf wir hinaus wollen, ist Sprachen aufzustellen, die nicht
entscheidbar sind.
Der erste Schritt, die erste Sprache, bei der man das machen kann, der
das beweisen kann, dass sie nicht entscheidbar ist, ist die
Diagonalsprache.
Sie haben in der Übung das Kantor- Argument gehabt, das ist eine gute
Vorbereitung für die Definition der Diagonalsprache.
Für die Diagonalsprache betrachtet man folgendes.
Man betrachtet einfach 0, 1 Worte in einer kanonischen Reihenfolge
sortiert.
Also sortiert nach der Länge und unter Worten gleicher Länge
lexikografisch sortiert.
Das heißt also, das erste ist die 0, das zweite ist die 1, das dritte
ist 0, 0, das vierte ist 0, 1, dann kommt 1, 0, dann 1, 1 und so
weiter.
So, und wir haben also jetzt Turing-Maschinen, die durch ihre Gödel
-Nummer kodiert sind.
Die Turing-Maschine MJ, sagen wir, das ist die, die durch das J-Wort
in dieser Sortierung der 0, 1-Worte kodiert wird.
Dann kann man so eine Tabelle konstruieren, die Zeilen und die Spalten
entsprechen 0, 1-Worten in dieser kanonischen Reihenfolge.
Die Interpretation ist aber, die Zeilen, also die 0, 1-Worte zu den
Zeilen entsprechen Eingaben und die 0, 1-Worte zu den Spalten
entsprechen Gödel-Nummern.
Das heißt also, wir haben Positionen i und j zwischen eins und
unendlich, also nach rechts und nach unten unendliche Tabelle.
Die einzelnen Positionen entsprechen solchen w, i beziehungsweise m,
j.
Die Zeilen solchen Eingaben wi, die Spalten solchen Turing-Maschinen
m, j.
Wir schreiben in die Tabelle einfach rein an der Stelle i, j ob das
Wort wi von der Turing-Maschine m, j akzeptiert wird oder nicht.
Also an der Position i, j steht eine 0, wenn wi nicht in der von m, j
akzeptierten Sprache ist und eine 1, wenn wi in der von m, j
akzeptierten Sprache ist.
Und was uns interessiert, sind jetzt die Einträge auf der Diagonalen.
Also für die Position i, j gilt, da steht eine 1, falls m, j wi
akzeptiert und eine 0, falls m, j wi nicht akzeptiert.
Und jetzt die Diagonalen angucken, dann gucken wir genau an die
Positionen i, i.
Diese Positionen i, i, die stehen für dasselbe Wort wi, aber
einerseits als Eingabe aufgefasst, Zeile, andererseits als Gödelnummer
einer Turing-Maschine aufgefasst, Spalte.
Also das wi steht für das Eingabewort wi, ist aber gleichzeitig die
Gödelnummer von m, i.
Und wenn wir auf die Diagonale gucken, dann zeigt uns eine 1 oder 0 an
so einer Stelle, ob die Turing-Maschine m, i, das Wort wi, also genau
so aussieht wie die Gödelnummer dieser Turing-Maschine, akzeptiert
oder nicht.
Und die Diagonalsprache ist definiert als die Menge der wi, für die
gilt die Turing-Maschine m, i, also die Turing-Maschine, deren
Gödelnummer grad wi ist, akzeptiert die Eingabe wi nicht.
Also ld, Diagonalsprache, enthält also alle wi, für die auf dieser
Diagonalen an der Stelle i, i grad eine 0 steht.
Diese Definition führt dann zu einem Nichtentscheidbarkeitsbeweis, der
große Ähnlichkeiten zu dem Diagonal- Argument von Kantor hat.
Aber gucken wir uns das jetzt einfach nochmal an.
Also wie sieht unsere Tabelle aus?
Wir haben unsere 0,1-Worte sortiert in lexikografischer Anordnung.
Bei den Zeilen ist die Interpretation unserer 0,1-Wort ist eine
Eingabe, bei den Spalten ist unsere Interpretation unserer 0,1-Wort
ist eine Gödelnummer und an so einer Stelle i, j steht eine 1, wenn
die Turing-Maschine mit Gödelnummer wi, j die Eingabe wi akzeptiert
und 0 sonst.
Und was uns interessiert für die Diagonalsprache ist nur das, was hier
auf der Diagonalen steht.
Also an der Stelle i, i steht eine 0, das heißt die Turing-Maschine
mit Gödelnummer wi akzeptiert die Eingabe wi nicht, das heißt wi ist
in der Diagonalsprache, wie die Diagonalsprache definiert ist.
Und hier an der Stelle j, j steht eine 1, das heißt die Turing
-Maschine mit Gödelnummer wi, j akzeptiert die Eingabe wi, j das
heißt, so wie unsere Diagonalsprache definiert ist, dass wi, j nicht
in der Diagonalsprache ist.
Also wenn da eine 1 steht, dann ist das entsprechende Wort nicht in
der Diagonalsprache.
Wenn da eine 0 steht, ist es in der Diagonalsprache.
Diagonalsprache ist die Menge der wi, für die gilt mi akzeptiert wi
nicht.
Und jetzt kann man ganz leicht zeigen, das sind nur 5 Zeilen, dass die
Diagonalsprache nicht entscheidbar ist.
Das ist natürlich ein Widerspruchsbeweis, man nehme an, die
Diagonalsprache wäre entscheidbar.
Dann gibt es eine Turing-Maschine, die stets hält und genau die Wörter
aus der Diagonalsprache akzeptiert.
Und diese Turing-Maschine gehört natürlich auch zu unseren Turing
-Maschinen, die wir durch Gödelnummern codiert haben und die jetzt da
in diesen Spalten w1 bis w irgendwas stehen.
Also alle Turing-Maschinen, dazu gehört eine Gödelnummer, wenn wir
diese 0,1 folgen, die eine Gödelnummer sein können oder eben eine
Codierung der Turing-Maschine, die die leere Menge akzeptiert, der
Reihe nach durchgehen, kommt irgendwann auch die Turing-Maschine mi,
die es geben muss, wenn ld entscheidbar ist.
Es geben muss, wenn ld entscheidbar ist und die eben stets hält und
genau die Wörter aus ld akzeptiert.
Und jetzt wenden wir diese Turing-Maschine auf die Eingabe an, die
gerade der Gödelnummer dieser Turing-Maschine entspricht.
Also wir wenden mi auf wi an.
Da gibt es jetzt zwei Fälle.
Das wi ist in der Diagonalsprache oder das wi ist nicht in der
Diagonalsprache.
Wenn das wi in der Diagonalsprache ist, dann wird wi deshalb von mi
akzeptiert.
Das ist aber ein Widerspruch dazu, dass die Diagonalsprache gerade die
wi enthält, die von mi nicht akzeptiert werden.
Und wenn i nicht in ld ist, dann akzeptiert mi das Wort wi wegen zwei.
Das ist aber wieder ein Widerspruch zur Definition von ld.
Bei ld enthält ja gerade die wi, die nicht akzeptiert werden von mi.
Das heißt, wir haben da so einen Widerspruch in sich durch
Selbstanwendung produziert.
Das ist ein bisschen komisch, aber das ist natürlich liegt an der
Definition und an dem Beweis.
Das ist so ein Paradoxon, was dahinter steckt.
Gucken wir uns gleich nochmal an.
Aber nur der Vollständigkeit halber ist es vielleicht ein bisschen
komisch, dass dieses ld gerade definiert ist, als die Menge der Worte
wi, für die gilt die entsprechende Turing-Maschine mi akzeptiert wi
nicht.
Man hätte natürlich auch die Komplementsprache als Diagonalsprache
definieren können.
Das ist eher ein technischer Grund, warum man das so macht.
Für die Diagonalsprache, für das Komplement der Diagonalsprache gilt
natürlich genauso, dass sie nicht entscheidbar ist.
Denn sie können ja einfach akzeptieren, nicht akzeptieren, für
Eingaben umdrehen.
Und das Prinzip, das wir hier jetzt eigentlich bei dem Beweis
anwenden, ist das Prinzip, das wir ganz oft dann bei
Nichtentscheidbarkeitsbeweisen anwenden, dass wir sagen, naja gut,
wenn jetzt die Sprache entscheidbar wäre, dann wäre auch eine andere
entscheidbar.
Für die wir aber schon gezeigt haben, sie ist nicht entscheidbar.
Widerspruch, also Sprache kann nicht entscheidbar sein.
Das ist das Prinzip der Reduktion, wenn wir ganz, ganz, ganz oft
benutzen.
Also hier, um dieses Korrelat zu beweisen, nehmen wir also mal an,
dass zwar ld nicht entscheidbar ist, also wir wissen, ld ist nicht
entscheidbar, aber nehmen wir mal an, dass ld-Kompliment entscheidbar
wäre.
Falls ld-Kompliment entscheidbar ist, dann gibt es natürlich eine
Turing -Maschine, die eben gerade ld-Kompliment entscheidet.
Aber die können wir jetzt leicht umbauen in eine Turing-Maschine, die
ld entscheidet.
Wir sagen einfach, wenn diese Turing-Maschine Eingabe nicht
akzeptiert, dann soll sie hierzu eine Eingabe akzeptieren und
umgekehrt.
Das heißt, es wäre ein klarer Widerspruch zur Unentscheidbarkeit der
Diagonalsprache, wenn deren Kompliment jetzt plötzlich entscheidbar
wäre.
Und hier dran sehen wir schon etwas Allgemeineres, nämlich dass
Entscheidbarkeit abgeschlossen ist gegenüber Komplementbildung.
Wenn eine Sprache entscheidbar ist, dann auch ihr Komplement.
Das muss so sein.
Okay, ich habe ja eben gesagt, dass was bei der Unentscheidbarkeit der
Diagonalsprache gemacht wird, das ist so ein bisschen paradox.
Das ist folgende Art von Paradoxon, das dahinter steckt.
Selbstbezüglichkeit.
Das kennen Sie vielleicht.
Der Barbier von hinter Tupfingen rasiert genau die Männer im Dorf, die
sich nicht selbst rasieren.
Wer rasiert den Barbier?
Wie auch immer Sie das beantworten, haben wir einen Widerspruch.
Oder Daniel Düsentrieb behauptet, eine allwissende Maschine erfunden
zu haben und stellt eine Ja-Nein-Frage, so wie bei einer Turing
-Maschine und die Antwort leuchtet auf.
Jetzt kauft Dago Verdag diese Maschine, will aber nur bezahlen, wenn
die Maschine auch wirklich immer korrekt antwortet.
Und deshalb stellt er der Maschine die Frage, wirst du mit Nein
antworten?
Tja, also diese Art von Paradoxon steckt hinter der
Nichtentscheidbarkeit der Diagonalsprache.
Das könnte Sie jetzt natürlich dazu führen, zu sagen, naja, aber so
richtig wichtige Fragen oder sinnvolle Probleme sind vielleicht doch
alle berechenbar.
Und das große Gegenbeispiel ist das Halteproblem.
Das wissen Sie auch, das kennen Sie, Sie studieren ja Informatik.
Die Frage, gegeben ein Programm und eine Eingabe, kann ich
entscheiden, ob das Programm auf der Eingabe hält?
Das ist das Halteproblem.
Das ist ein echtes Problem.
Ein echtes Problem, wenn man das entscheiden könnte, wäre sehr manches
in der Informatik anders aus, als es aussieht.
Und hierzu einfach mal so als grafische Vorstellung, wie sozusagen die
Nichtentscheidbarkeit des Halteproblems argumentiert werden kann.
Also Halteproblem, so ein Programm, das entscheiden kann, ob ein
Programm auf ein vorgegebenes Programm einer vorgegebenen Eingabe
hält, sähe so aus, ist wie so eine Blackbox.
Da kommt eine Eingabe rein, Programm mit Eingabe, und rauskommt Ja
oder Nein.
Wenn wir so etwas hätten, dann könnten wir Folgendes bauen.
Ein Programm Test, das sieht so aus.
Da geht eine Eingabe rein, dann wird durch dieses Halt geschickt,
durch dieses Programm Halt.
Wenn dieses Programm Halt als Output Ja sagt, geht Test in der
Endschlussschleife, hält also nicht.
Und wenn Halt Nein sagt, dann stoppt Test, hält also.
Und jetzt machen wir Selbstbezüglichkeit oder Anwendung auf sich
selbst.
Jetzt wenden wir dieses Programm auf sich selbst an, also auf Test mit
einer Eingabe an.
Halt kriegt diese Eingabe, wenn die Antwort ist Ja, also Test hält auf
bestimmten Eingaben, die wir mitgeben, dann ist die Antwort Ja, dann
geht das Ganze in der Endschlussschleife, hält nicht.
Und wenn Test bei der entsprechenden Eingabe nicht hält, dann würde
Halt sagen Nein, dann würde aber Test stoppen, also halten.
Sie haben die gleiche Art Paradoxon oder Widerspruch wie bei dem
Babier von Hintertupfingen.
So und jetzt der formale Beweis dazu.
Wir haben bisher nur über Sprachen und Akzeptieren von Sprachen
gesprochen.
Wir haben auch Realisieren von der Funktion mal betrachtet, aber
eigentlich werden wir fast immer in der Vorlesung, auch wenn wir
später über echte Probleme reden, ein Konzept zugrunde legen, bei dem
Probleme formuliert werden als wird eine Sprache akzeptiert oder
nicht.
Das heißt also zum Halteproblem brauchen wir jetzt eine Sprache.
Und die Sprache, die das Halteproblem beschreibt, sieht folgendermaßen
aus.
Das ist die Menge der Wörter WV, für die gilt, die Turingmaschine mit
Gödelnummer W hält auf der Eingabe V.
Sind also kombinierte Worte WV und da sind in der Sprache zum
Halteproblem gerade die kombinierten Worte drin, für die gilt, die
Turingmaschine zum ersten Teil des Wortes hält auf der Eingabe, die so
aussieht wie der zweite Teil des Wortes.
Dann kann man die Nichtentscheidbarkeit dieser Sprache leicht
beweisen, also Interpretation ist, diese Sprache entscheiden heißt das
Problem, aber eine Turingmaschine auf einer Eingabe stoppt ist nicht
entscheidbar.
Wieder Prinzip der Reduktion, also wir führen die Annahme, die Sprache
zum Halteproblem wäre entscheidbar, zu einem Widerspruch, in dem wir
folgern, dann wäre auch eine der Sprachen, von denen wir schon wissen,
dass sie nicht entscheidbar sind, entscheidbar.
Und zwar benutzen wir hier die Komplementsprache der Diagonalsprache.
Also angenommen, es existiert eine stets haltende Turingmaschine, die
gerade die Sprache zum Halteproblem entscheiden kann.
Also wenn das hier nicht stimmt, also H entscheidbar ist, dann muss es
sowas geben.
Daraus konstruieren wir jetzt eine stets haltende Turingmaschine, die
die Komplementsprache der Diagonalsprache entscheidet und das wäre ein
Widerspruch zu dem Corolla, was wir gerade hatten.
So, sei jetzt W eine Eingabe, für die wir eben entscheiden wollen, ob
W in dem Komplement der Diagonalsprache ist.
Dann könnten wir mit dieser stets haltenden Turingmaschine zu H
folgendes machen.
Wir berechnen erstmal das I, sodass die Eingabe gerade das I-te Wort
in unserer Sortierung der 0,1-Worte ist.
Wir betrachten die durch W I kodierte Turingmaschine, MI heißt sie,
und wir wenden H auf Kodierung von MI gefolgt von W I an.
So, was passiert dann?
Naja gut, also das MI W I wird entweder akzeptiert oder nicht
akzeptiert.
Falls MI W I nicht akzeptiert wird, was heißt das?
Das heißt, dann hält MI nicht auf W I.
Nach Definition von der Sprache des Halteproblems ist also das W I in
der Diagonalsprache und damit nicht im Komplement der Diagonalsprache.
Und andererseits, falls MI W I akzeptiert wird durch die
Turingmaschine zum Halteproblem, dann hält MI auf W I, dann können wir
aber auf der universellen Turingmaschine die Berechnung von MI auf W I
vollständig simulieren.
Das heißt also, wir haben diese Annahme wir haben so eine stets
haltende Turingmaschine für die Sprache H zu einem Widerspruch dazu
geführt, dass die Komplementsprache der Diagonalsprache nicht
entscheidbar ist.
Indem wir gesagt haben, die könnte man dann aber auch benutzen, um LD
Komplement zu entscheiden.
Da müssen Sie sich dran gewöhnen, das ist ein bisschen schwere Kost,
aber diese Beweise, diese Nichtentscheidbarkeitsbeweise sind
typischerweise ganz kurz, wenige Argumente, aber Sie müssen sozusagen
dieses Prinzip der Reduktion, angenommen die Sprache von der ich
beweisen will, sie ist nicht entscheidbar, wäre entscheidbar,
zurückgeführt auf, dann ist eine andere Sprache, von der wir schon
bewiesen haben, sie ist nicht entscheidbar, entscheidbar, also diese
Art von Widerspruchsbeweis die müssen Sie, ich sag mal so,
verinnerlichen.
Das ist eigentlich alles.
So, und das ist jetzt auch alles für heute.