Wir haben in der letzten Woche die Turing-Maschine eingeführt.
Und das ist eine ganz kurze Zusammenfassung der Bestandteile und der
Funktion einer Turing-Maschine.
Also das ist die deterministische Turing-Maschine.
Die hat einen Lese- und Schreibkopf, der liest und schreibt Zeichen
auf einem Band.
Es gibt eine endliche Kontrolle, die befindet sich immer in einem von
endlich vielen Zuständen.
Das sind quasi die Zustände aus den endlichen Automaten, die wir
vorher kennengelernt haben.
Und es gibt eben dieses unendliche Rechenband, auf dem die Turing
-Maschine arbeiten kann.
Das ist der größte Unterschied.
Dort steht am Anfang die Eingabe und die Turing-Maschine kann diese
Eingabe jetzt ablaufen, ändern, sich andere Sachen auf das Band
schreiben, was irgendwie hilft, um diese Eingabe zu bearbeiten.
Also insbesondere ist es nicht mehr so, dass die Eingabe nur einmal
Zeichen für Zeichen abgearbeitet wird, sondern die Turing-Maschine
darf mehrmals, so viel sie möchte, über diese Eingabe drüber gehen.
Sie darf sie ändern, sie darf sich zusätzliche Sachen
zwischenspeichern und so weiter.
Formal war das so ein Siebentupel.
Turing-Maschinen werden üblicherweise mit M abgekürzt.
Es ist so ein Siebentupel.
Q ist die Menge der Zustände, in der die endliche Kontrolle sein kann.
Sigma ist, so wie vorher auch schon, unser Eingabealphabet.
Und jetzt gibt es noch so ein Blank-Symbol, was einfach heißt, dort
steht nichts auf dem Band.
Das ist das Nichts auf dem Band.
Und dann gibt es Gamma, das ist jetzt eine Übermenge von Sigma und dem
Blank -Symbol, das ist das Bandalphabet.
Also eventuell hat die Turing-Maschine noch zusätzliche Zeichen zur
Verfügung, die sie auf das Band schreiben kann.
Dann gibt es einen Startzustand, dann gibt es eine Übergangsfunktion
und dann gibt es eine ausgewählte Menge von akzeptierenden
Endzuständen, die wieder hier mit F bezeichnet ist.
Und die Übergangsfunktion, die ja sozusagen das Eigenleben oder das
Innenleben der Turing-Maschine beschreibt, die kriegt jetzt sozusagen
als Eingabe ein Tupel Q und A und das korrespondiert dazu, Q ist der
Zustand, in dem sich die endliche Kontrolle im Moment befindet und A
ist das Band-Symbol, was der Leseschreibkopf gerade liest an seiner
Position auf dem Band.
Und in Abhängigkeit von diesen beiden Sachen wird jetzt in der
Übergangsfunktion spezifiziert, was denn als nächstes passieren soll.
Also was ist der neue Zustand, in den die endliche Kontrolle gehen
soll, Q', was ist das Zeichen, was statt dieses A's auf diesem Band an
dieser Stelle jetzt geschrieben werden soll.
Das könnte wieder A sein oder es wird verändert, vielleicht wird es
gelöscht durch ein Blank oder so ersetzt.
Also was ist A', was soll dann auf diesem Band stehen an dieser
Position und was soll mit dem Leseschreibkopf passieren, nämlich soll
er einen Schritt nach links nicht bewegen oder einen Schritt nach
rechts gehen.
Und ich hatte es gerade schon ein bisschen angedeutet, diese Turing
-Maschine, das Verhalten ist jetzt ganz anders als von einem endlichen
Automaten, insbesondere haben wir drei wesentliche Möglichkeiten, die
eintreten könnten, wenn eine Eingabe W auf dieser Turing-Maschine
jetzt bearbeitet wird.
Dass eine Eingabe bearbeitet wird, heißt einfach, die Eingabe steht am
Anfang auf diesem Rechenband drauf und dann startet die Turing
-Maschine in ihrem Startzustand mit dem Leseschreibkopf links auf dem
ersten Symbol der Eingabe.
Also es gibt drei Möglichkeiten.
Die Möglichkeit 1 ist, die Turing-Maschine tut etwas, in Abhängigkeit
davon, was diese Übergangsfunktion ihr sagt, wechselt sie diese
Zustände und eventuell modifiziert das Band und bewegt den
Leseschreibkopf und es könnte sein, dass sie irgendwann bei diesem
Zustandswechsel mal in einen Zustand in F wechselt.
Und sobald sie das tut, stoppt die Turing-Maschine und akzeptiert.
Wir sagen, wenn das passiert, dann akzeptiert die Turing-Maschine das
Wort W, was in der Eingabe war.
Insbesondere ist es jetzt nicht mehr ganz klar, wann das passieren
soll.
Vielleicht hat die Turing-Maschine noch nicht mal das ganze Wort
gesehen oder so.
Sie könnte das sofort tun oder ganz spät, erst nach 20 Mal drüber
laufen über das Wort und 10 Mal verändern.
Aber irgendwann läuft sie eventuell in so einen Endzustand aus F.
Und sobald sie den Zustand betritt, ist sofort Schluss.
Jetzt könnte es aber auch noch sein, dass sie nicht in so einen
Zustand aus F läuft, aber irgendwann in einen Übergang läuft, der so
aussieht.
Delta von QA ist gleich QA und N.
Das heißt, wenn die Turing-Maschine diesen Übergang benutzt, wenn sie
da reinläuft, dann ändert sich dieser Zustand, in dem sich die
endliche Kontrolle befindet, nicht.
Ändert sich das Zeichen, was da steht auf dem Band, an der Stelle des
Lese -Schreibkopfes nicht.
Und die Position des Lese-Schreibkopfes ändert sich auch nicht, weil
da hinten ja ein N steht.
Also die Turing-Maschine ist sozusagen angewiesen, nichts zu tun.
Bleib in dem Zustand, lass das Zeichen und bewege dich nicht.
Und in dem Fall sagen wir auch, jetzt stoppt die Turing-Maschine.
Das ist also die zweite Möglichkeit, wie die Turing-Maschine stoppt,
indem sie in so einen Übergang läuft.
Und wenn sie das tut, dann sagen wir, die Turing-Maschine lehnt das
Wort ab.
Oder wir sagen, das ist so das, was ich mir vorstelle, wir sagen, die
Turing -Maschine stoppt und akzeptiert nicht.
Und dann gibt es noch die dritte Möglichkeit, nämlich, dass keins von
diesen beiden hier vorne passiert.
Also sie läuft nicht in so einen Zustand f und sie läuft nicht in so
einen Übergang, der alles konstant lässt.
Dann läuft sie und läuft sie und läuft sie und läuft sie und nichts
davon tritt ein.
Das heißt, sie läuft unendlich lange.
Das können Sie sich entweder vorstellen durch so etwas wie eine
Endlosschleife, sie wiederholt immer das Gleiche.
Oder aber auch nicht eine Endlosschleife, vielleicht ist es auch so,
dass sie immer weiter nach rechts geht.
Oder sie geht immer einen Schritt nach rechts, zwei nach links, drei
nach rechts, vier nach links, fünf nach rechts, sechs nach links und
so weiter.
Also es kann auch ganz kompliziert sein, aber sie läuft unendlich
lange und tut irgendwas.
Und in diesem Fall sagen wir, die Turing-Maschine stoppt nicht.
Also es ist ganz wichtig, dass Sie sich bewusst machen, was diese drei
Eigenschaften unterscheidet und dass das alles passieren könnte.
Die linken beiden, da sagen wir einfach, die Turing-Maschine stoppt,
bei der rechten stoppt sie nicht.
Nur bei dem linkesten sagen wir, die Turing-Maschine akzeptiert das
Wort, bei der rechten sagen wir, das Wort wird nicht akzeptiert.
Aber Sie müssen mit den Feinheiten aufpassen.
Wenn ich sage, nicht akzeptiert, kann es auch sein, dass sie einfach
unendlich lange läuft.
Gut, also das sind so die drei Möglichkeiten, was jetzt essenzieller
Unterschied zu den endlichen Automaten war.
Die endlichen Automaten, die haben das Wort genommen und abgelaufen
und wenn sie am Ende des Wortes waren, war Schluss.
Da war nichts mehr zu lesen und dann wussten wir also, die hören auf
jeden Fall auf.
Und dann war bloß noch die Frage, hören die auf in einem Zustand aus F
oder hören die auf in einem Zustand nicht aus F und so weiter.
Und der Unterschied war auch bei den endlichen Automaten, da durften
wir zwischendurch durch Zustände aus F laufen, ohne gleich
abzubrechen.
Hier brechen wir sofort ab, wenn wir in so einen Zustand aus F kommen.
Dann hatten wir angefangen uns ein erstes Beispiel anzugucken, das war
diese kleine Turing-Maschine.
Und wir hatten uns schon überlegt, dass wenn die Eingabe mit einer 1
beginnt, dann starten wir hier in diesem Zustand S und dann sagt es,
der Lese-Schreibkopf steht auf dem ersten Symbol der Eingabe und wenn
das jetzt hier eine 1 ist, dann wird diese 1 gelöscht, der Lese
-Schreibkopf geht nach links und wir gehen in diesen Zustand Q2 und
der ist ein finaler, also die Turing-Maschine stoppt und akzeptiert,
egal was danach kommt nach der 1.
Jetzt merken Sie schon, dass wir hier hinten noch diese Pfeile
rangemacht haben, das ist eigentlich ziemlich unnötig, weil sowieso,
sobald man in so einen Zustand reinkommt aus F, brauchen wir uns nicht
mehr überlegen, was passiert denn, wie sehen denn Übergänge aus, die
aus diesem Zustand rausführen, weil sofort gestoppt wird, also nehme
ich die einfach mal weg.
Das ist vielleicht ein bisschen sauberer.
Also wenn die Eingabe mit einer 1 beginnt, dann akzeptiert die Turing
-Maschine, sie stoppt und akzeptiert.
Und wenn die Eingabe jetzt nicht mit einer 1 beginnt, dann ist die
Eingabe entweder leer und sie bleibt hier die ganze Zeit in diesem S
drin und bewegt den Schreibkopf nach rechts oder die Eingabe fängt an
mit einer 0, dann lässt sie die 0 und geht auch mit dem
Leseschreibkopf nach rechts, geht in diesen Zustand Q1 über, wo dann
auch einfach immer nur noch nach rechts gegangen wird, ohne die
Eingabe zu verändern.
Und das wird also niemals in so einen Zustand kommen, der in F ist,
wir werden nicht mehr in diesen Zustand Q2 kommen und wir werden auch
nicht in so einen Übergang laufen, wo es heißt, lasst den Zustand,
lasst das Zeichen und bewegt den Kopf nicht.
Weil es so einen Übergang hier überhaupt nicht gibt.
Das heißt, wenn die Eingabe nicht mit einer 1 beginnt, dann werden wir
in der dritten Möglichkeit, die Turing-Maschine wird nicht stoppen.
Okay.
Gut.
Jetzt ist die Frage, okay, jetzt müssen wir diese drei Möglichkeiten
irgendwie wieder verwurschteln mit den Sprachen, die irgendwie
dazugehören zu der Turing-Maschine und...
Oh, vorher noch was anderes.
Wenn die Turing-Maschine fertig ist, wenn sie stoppen sollte, dann
steht ja am Ende irgendwas auf dem Band, auf dem Rechenband.
Und eventuell ist es sogar noch wichtig, was da drauf steht für uns.
Also wir könnten dieses Rechenband sozusagen als eine Art Ausgabe
sehen.
Das Programm ist fertig, die Turing-Maschine ist fertig, sie stoppt
und dann gibt es noch eine Ausgabe.
Und diese Ausgabe möchte ich aber nur interpretieren, wenn die Turing
-Maschine akzeptiert.
Also wenn die Turing-Maschine stoppt, dann gibt es immer noch die
Möglichkeit, warum stoppt sie.
Entweder sie akzeptiert oder sie stoppt, weil sie in diesen Übergang
läuft, der sagt nichts mehr tun.
Nur in dem Fall, dass sie akzeptiert, gucke ich mir an, was auf dem
Band ist.
Für mich im Kopf ist es vielleicht ein bisschen so, das Programm
akzeptiert, wenn es ordentlich durchgelaufen ist und die Ausgabe
wirklich was Sinnvolles ist und dieses andere ist vielleicht mehr
sowas wie eine Fehlermeldung.
Es stürzt ab oder so das Programm.
Und dann interessiert mich nicht, was da gerade für partielle
Informationen irgendwo im Zwischenspeicher stehen.
Wir sagen dann, dass eine Turing-Maschine eine partielle Abbildung
oder Funktion realisiert.
Nämlich auf der linken Seite ist das, was ich raufschreibe auf das
Rechenband als Eingabe und auf der rechten Seite ist das, falls das
akzeptiert wird, was dann auf dem Rechenband am Ende steht.
Und das ist nur eine partielle Funktion, weil für einige Eingaben, die
überhaupt nicht stoppt, und dann gibt es keine Aufgabe.
Also in diesem Beispiel sähe diese partielle Funktion so aus, dass der
Funktionswert eines Wortes W ist gerade das Wort V, wenn W V ist mit
einer führenden Eins vorne dran.
Das ist das, was die Turing-Maschine tut.
Sie löscht die führende Eins und stoppt dann und dann steht auf dem
Band also nur noch V.
Und ansonsten sage ich einfach, es ist undefiniert.
Wenn sie unendlich lange läuft, ist sowieso unklar, was die Ausgabe
sein soll.
Und auch wenn sie in so einem Nichtstun-Übergang gerät, gucke ich mir
das Band nicht an.
Es ist einfach undefiniert.
Wir werden diese Turing-Maschinen oft nicht vollständig hinmalen.
Zum Beispiel diese Turing-Maschine ist äquivalent zu der, die ich
davor gezeigt habe.
Ich habe gerade schon gesagt, dass ich hier hinten an diesen
Finalzuständen mich eigentlich gar nicht mehr darum kümmern muss, was
da für Übergänge rausgehen.
Die werde ich nicht hinmalen.
Und manchmal werde ich auch an Nicht-Finalzuständen gewisse Übergänge
nicht mehr hinmalen.
Zum Beispiel hier ist jetzt nicht mehr spezifiziert, was passiert
eigentlich, wenn ich ein S bin und ich lese eine Null.
Und wir gehen dann einfach davon aus, dass immer wenn ich bei einer
Kombination Q und A bin, also ich bin in einem Zustand und einem
Zeichen und ich habe diesen Übergang nicht hingemalt, also dieses
Delta Q A ist irgendwie nicht definiert oder nicht in diesem Bild,
dann gehe ich davon aus, dass die Maschine stürzt ab.
Also sie stoppt und akzeptiert nicht.
Fehlermeldung oder sowas.
Also zum Beispiel können wir uns insgeheim denken, dass für diese
Kombination hier die Übergangsfunktion gerade sagt, mache nichts mehr
und dann ist per Definition stoppen ohne akzeptieren.
So und jetzt wollen wir ausklamüsern, wie diese drei Fälle, in die die
Turing -Maschine laufen könnte, mit den Sprachen zusammenhängen.
Also wie schon gesagt, die Turing-Maschine akzeptiert eine Eingabe,
ein Wort W, wenn nach dem Lesen von W oder bei Eingabe von W die
Turing -Maschine in so einen Finalzustand aus F geht, läuft.
Dann akzeptiert sie das Wort.
Und die Menge der Wörter, die akzeptiert wird, das ist die Sprache,
die von dieser Turing-Maschine akzeptiert wird.
Also ein Wort ist in der Sprache von der Turing-Maschine, wenn dieses
Wort akzeptiert wird von der Turing-Maschine.
Das ist die akzeptierte Sprache.
Das spezifiziert jetzt erstmal noch nicht, was passiert mit den
Wörtern, die nicht in der Sprache sind.
Wir wissen nur, nicht der erste Fall.
Aber ob es der zweite oder der dritte Fall ist, wissen wir nicht.
Das wollen wir nicht spezifizieren.
Wir wollen einfach nur die Sprache zu der Turing-Maschine, also die
Menge der Eingaben, wo die in den ersten Fall kommt.
Jetzt wollen wir das noch ein bisschen spezifizieren.
Wir sagen, eine Sprache heißt entscheidbar, oder manche nennen es auch
rekursiv, obwohl das vielleicht irreführend ist.
Also entscheidbar ist, glaube ich, der Begriff, den wir hier eher
verwenden wollen.
Wenn es eine Turing-Maschine gibt, die diese Sprache akzeptiert und
zusätzlich diese Turing-Maschine immer stoppt.
Also diese Turing-Maschine, die wird nur Möglichkeit 1 und 2 haben.
Es wird unmöglich sein für uns, die zum unendlich Laufen zu bringen.
Also die hat nur Möglichkeiten 1 und 2 und die geht genau in
Möglichkeit 1, wenn das Wort aus der Sprache kommt.
Also wichtig ist, die Sprache heißt entscheidbar, wenn es eine Turing
-Maschine gibt, die auf allen Eingaben stoppt.
Die dritte Möglichkeit ist ausgeschlossen und eine Eingabe genau dann
akzeptiert, wenn das Wort in der Sprache liegt.
Und semientscheidbar heißt es jetzt, wenn wir auch erlauben, dass die
Wörter, die nicht in der Sprache sind, eventuell in Möglichkeit 3
fallen.
Also eine Sprache, einfach eine Menge von Wörtern, heißt
semientscheidbar oder rekursiv aufzählbar, wenn es eine Turing
-Maschine gibt, die die Eingaben W genau dann akzeptiert, wenn sie in
dieser Menge L drin sind.
Wenn das W jetzt nicht in der Menge L drin ist, dann weiß ich, sie ist
entweder in 2 oder in 3, aber ich spezifiziere das hier nicht.
Das ist mir egal, wie die Turing-Maschine damit umgeht.
Sie geht dann entweder in 2 oder in 3.
Also hier steht hier unten das Verhalten bei einer Eingabe W nicht in
L ist nicht genau definiert, wir wissen nur, Möglichkeit 1 ist
verboten, aber zwischen 2 und 3 ist uns das egal.
Um so ein Verhalten einer Turing-Maschine zu analysieren, definieren
wir uns die sogenannte Konfiguration, in der die Turing-Maschine sich
gerade befindet.
Und die Konfiguration spezifiziert alles, was wir dafür brauchen.
Es ist dann wiederum egal für uns, wie wir da hingekommen sind,
sondern das ist der Ist-Zustand mittendrin im Programm.
Und wir schauen uns an, was gerade da ist.
Und dafür ist natürlich wichtig, was steht gerade auf dem Band, in
welchem Zustand befindet sich die endliche Kontrolle und wo steht der
Lese -Schreibkopf.
Und das wird dann so formal notiert.
W ist ein Wort, Q ist ein Zustand, A ist ein Zeichen und V ist wieder
ein Wort.
Und das heißt, dass die Turing-Maschine, die endliche Kontrolle,
befindet sich in Zustand Q auf dem Lese-Schreibkopf, der zeigt gerade
irgendwo auf dem Band und da steht das Zeichen A und rechts davon
steht noch ein Wort V und links davon steht ein Wort W.
Und dann können wir uns jetzt zum Beispiel so eine Turing-Maschine
angucken und die für eine bestimmte Eingabe einfach durchspielen,
indem wir diese Folge von Konfigurationen, die sie einnimmt,
durchgehen.
Ich sage Ihnen das jetzt einfach so, diese Turing-Maschine akzeptiert
die Sprache Wörter der Form 0 hoch N, 1 hoch N, N eine natürliche
Zahl.
Das ist eine Sprache, die haben Sie schon mal gesehen, das war eine
Sprache, die konnte von endlichen Automaten nicht erkannt werden.
Und das ist jetzt sozusagen, ich werde das nicht formal beweisen, aber
Sie werden schon gleich ein Gefühl dafür kriegen, warum das gilt, das
zeigt Ihnen, dass die Turing-Maschine schon mal mehr kann als ein
endlicher Automat diese Sprache hier zum Beispiel erkennen.
Und wir spielen das jetzt einfach mal durch anhand der Eingabe W0011,
die sollte akzeptiert werden, wenn das hier stimmt, weil dieses Wort
hat diese Form, nämlich für endlich zwei.
So, wie würde man das jetzt machen?
Das ist die Liste der Konfigurationen, die die Turing-Maschine
durchgeht.
Das ist eine deterministische Turing-Maschine, da ist genau
festgelegt, was passiert.
Also gehen wir durch, wir fangen an mit der endlichen Kontrolle in
Zustand S.
Auf dem Band steht dieses Wort 0011, das müssen Sie jetzt so sehen,
dass die erste Null ist ein Zeichen und dahinter kommt ein Wort.
Die erste Null, das was direkt hinter der geschlossenen Klammer steht,
ist das Zeichen, auf dem der Lese-Schreibkopf gerade zeigt.
Okay, gut.
Und dann gucken wir jetzt in die Turing-Maschine, was passiert denn,
wenn wir uns befinden in Zustand S und das Zeichen Null lesen.
Naja, das heißt, dieses Zeichen wird gelöscht, da wird jetzt ein Blank
hingeschrieben stattdessen und der Lese-Schreibkopf geht einen Schritt
nach rechts.
Man sieht also, die nächste Konfiguration sieht so aus.
Ich habe jetzt hier dieses gelöschte Zeichen mal mit so einem Blank
hingeschrieben.
Und wir sind jetzt im Zustand Q1, wir sind einen Schritt nach rechts
gegangen, wir zeigen jetzt mit unserem Lese-Schreibkopf auf diese
Null, auf die zweite Null, die ja noch da ist.
Und dann gucken wir, jetzt sind wir in Zustand Q1 und wir lesen eine
Null und gucken, was sollen wir da machen.
Naja, wenn wir in Q1 sind und eine Null lesen, dann haben wir hier
diese Schlaufe, die sagt, lasse die Null und gehe einen Schritt nach
rechts.
Und lasse Q1 auch.
Das heißt, wir haben einfach nur den Lese-Schreibkopf eins nach rechts
bewegt.
Dann sind wir in dieser dritten Konfiguration.
Jetzt lesen wir dort eine Eins, sind immer noch in Zustand Q1 und
sehen, dass wiederum es heißt, lasse die Eins dort stehen auf dem Band
und bewege dich nach rechts.
Dann sind wir hier in dem vierten.
Und dann machen wir das wieder nochmal, wenn wir noch die zweite Eins
lesen und jetzt sind wir immer noch in Zustand Q1 und jetzt ist aber
unser Lese-Schreibkopf zeigt jetzt auf die freie Stelle des Bandes
hinter dem Eingabewort.
Das ist also ein Blank-Symbol, was es dort liest.
Und wenn man jetzt in Q1 ist und ein Blank-Symbol liest, dann hat die
Turing -Maschine sozusagen jetzt erkannt, dass sie am Ende ist des
Wortes, ist einmal durchgegangen.
Dann sagt sie, okay, geh wieder einen Schritt zurück, damit ich auf
dem letzten Buchstaben des Wortes bin und wechsele den Zustand in Q2.
Das signalisiert mir, ich habe erkannt, ich bin am Ende.
Und wenn ich jetzt in Q2 bin, dann gucke ich mir jetzt also das letzte
Zeichen an und für uns ist jetzt gut, wenn da eine Eins steht.
Wir wollen ja die Sprache 0 hoch N, 1 hoch N erkennen.
Wir haben ganz am Anfang eine Null gelöscht und wollen jetzt sozusagen
die zugehörige Eins am anderen Ende finden und löschen.
Wenn da jetzt keine Eins steht, dann ist hier gar nicht spezifiziert,
was passiert mit Q2.
Dann ist Fehlermeldung Abbruch.
Sie akzeptiert nicht, aber stoppt.
Gut, wenn da aber eine Eins steht, wird die Eins gelöscht und wir
gehen nach links in den Zustand Q3.
Jetzt sind wir wieder auf dem vorletzten Symbol sozusagen des Wortes.
In dieser Konfigurationsreihenfolge sind wir dort.
Die Konfiguration ist 0, Q3 1.
Und jetzt haben wir diesen Q3 Zustand, der sieht, wenn da noch eine
Eins ist, dann sind wir noch nicht fertig.
Dann gehen wir in den Zustand Q4 über und laufen nach links.
Der Zustand Q4 ist einfach ein Zustand, der wieder den Leseschreibkopf
ganz nach links laufen lässt.
Alles festlässt, bis wir merken, wir sind ganz nach links gelaufen und
lesen jetzt schon das erste Blank, was vor dem Rechenband steht und
merken, jetzt ist es sozusagen, wir gehen nach rechts, dann sind wir
auf dem ersten Zeichen und in den Zustand S.
Das ist jetzt sozusagen alles auf Anfang.
Aber wir haben sozusagen Fortschritt gemacht, dadurch, dass wir ganz
vorne eine 0 und ganz hinten eine 1 gelöscht haben und jetzt
wiederholen wir das Ganze.
Löschen wieder vorne eine 0, hinten eine 1, wieder vorne eine 0,
hinten eine 1 und so weiter.
Bis wir irgendwann nach dem Löschen der 1, das passierte ja hier bei
dem Übergang ganz unten, die 1 wird gelöscht, wenn wir da merken, dass
das Wort jetzt leer ist, dass wir merken, wir lesen das Blank-Symbol.
Und wenn wir das merken, dann wissen wir, wir haben das ganze Wort
abgebaut durch Nullen und Einzen und wir gehen in Q3 und die Turing
-Maschine stoppt und akzeptiert.
Was ist das?
5.
Entschuldigung.
Wir gehen in Q5.
Also, so funktioniert diese Turing-Maschine.
Jetzt nochmal zu den Funktionen.
Wir sagen, dass eine Funktion berechenbar ist oder Turing berechenbar,
wenn ich eine Turing-Maschine finde, die diese Funktion realisiert.
Also die Funktion sagt für jede Eingabe sozusagen, was ich mir wünsche
als Ausgabe.
Und wenn ich eine Turing-Maschine finde, die bei der Eingabe W genau
dann akzeptiert, wenn dieser Funktionswert nicht undefiniert ist und
dann nicht nur, dass es akzeptiert, sondern außerdem auch noch diesen
Funktionswert auf dem Band am Ende ausgibt.
Das klingt jetzt noch schwieriger.
Also wir wollen ein Wort erkennen, da soll die Turing-Maschine Ja
sagen, indem sie in den finalen Endzustand geht, aber zusätzlich soll
sie noch ein Ergebnis liefern.
Also zum Beispiel zwei Zahlen addieren und dann soll die als Eingabe
kommen und soll auf dem Band am Ende das Ergebnis stehen oder sowas.
Da werden wir ja daran interessiert.
Also wir sagen dann, dass die Turing-Maschine diese Funktion, die wir
uns wünschen, realisiert, wenn sie genau das Gewünschte tut.
Also wenn die Eingabe akzeptiert wird, dann steht auf die Ausgabe der
Turing -Maschine gerade in diesem Funktionswert drin.
Und wenn die Eingabe nicht akzeptiert wird, weil wir da zum Beispiel
gar keine Additionsaufgabe aufs Band geschrieben haben oder so, dann
ist auch undefiniert, was die Ausgabe sein soll.
Machen wir dafür auch ein Beispiel.
Das ist wieder eine kleine Turing-Maschine und die Eingabe, die sie
kriegt, ist ein Wort aus 0,1 und das fassen wir jetzt auf als eine
binär kodierte Zahl.
Und jetzt ist es nicht ganz so, dass jedes Wort aus 0,1 eine binär
kodierte Zahl ist.
Zum Beispiel das leere Wort ist keine binär kodierte Zahl oder sowas
wie 0,0,0,0,1 ist auch keine binär kodierte Zahl.
Also wir wollen das so wie in Dezimaldarstellung, wie Sie es auch
gewöhnt sind, wir wollen keine führenden Nullen haben, es sei denn,
die Zahl ist einfach nur 0.
Dann soll es einfach nur 0 sein.
Also das ist sozusagen das erste, was die Turing-Maschine tun muss.
Sie muss erstmal erkennen, ob die Zahl überhaupt eine ordentliche
binär kodierte Zahl ist.
Und für den Fall, dass sie das ist, soll sie jetzt als Ausgabe haben,
binär kodiert, addiere zur Eingabe eine 1.
Einfach plus 1 soll die rechnen.
Und das Ergebnis dieser binären Addition soll dann auf dem Band stehen
am Ende.
Und wir gehen das gleich durch, warum das so ungefähr sein wird, dass
die Turing-Maschine das tut.
Nur nochmal kurz den Bogen schlagen zu diesen realisierenden
Funktionen.
Also diese Turing-Maschine, wenn das wirklich so ist, dann würde sie
die folgende Funktion, parzelle Funktion realisieren.
Der Funktionswert eines Wortes ist gerade w plus 1, wenn w diesem
Ausdruck genügt, also wenn w eine ordentlich binär kodierte Zahl ist.
Wobei jetzt w und w plus 1 beides als binär kodiert interpretiert
wird.
Also das Wort, das hier heißt, erst w binär kodiert interpretieren,
dann plus 1 rechnen, dann wieder das Ergebnis binär kodieren.
Sie wissen, was ich meine.
Und falls es keine ordentliche Eingabe ist, dann ist es einfach
undefiniert.
Dann soll sie gar nicht akzeptieren.
Warum sollte das so ungefähr sein?
Naja, wiederum ist es so wie davor vielleicht auch, dass gewisse
Zustände haben gewisse Aufgaben, um diese große Aufgabe, das große
Problem zu lösen.
So wie davor mit diesem 0 hoch n, 1 hoch n, da gab es Zustände, die
waren dafür da, einfach nur das Wort, den Schreibkopf ganz nach hinten
zu schieben.
Gab es Zustände, die waren dafür da, die letzte 1 zu löschen.
Ein anderer Zustand, der war dafür da, wieder ganz nach vorne zu gehen
mit dem Lese-Schreibkopf usw.
Und so ist es hier jetzt ähnlich, die Zustände haben gewisse Aufgaben.
Also, das erste ist, gehen wir mal hier nach oben in diesen Zustand
q1, das heißt also, das erste Zeichen dieser Binärzahl ist wirklich
eine 1, also es ist eine positive binär kodierte Zahl.
Und dann ist der Zustand q1 wieder ganz ähnlich wie vorher, einfach
nur dafür da, ganz ans Ende zu gehen.
Der lässt immer drauf, was auf dem Band steht und bewegt den
Schreibkopf nach rechts, bis irgendwann mal ein Blank gelesen wird.
Und dann wissen wir, wir sind ganz am Ende der Eingabe.
Und dann machen wir wieder diesen Trick, wir sagen, wir lesen das
Blank, wir lassen das Blank und bewegen uns aber wieder einen Schritt
nach links und wechseln den Zustand.
Das heißt, wenn wir jetzt hier angekommen sind in q2, wissen wir, q2
steht auf dem letzten Zeichen des Eingabeworbs.
Und q2 ist jetzt dafür da, diese Addition zu machen.
Also wir wissen, dass wenn da eine 0 steht, dann soll da eine 1 hin,
weil wir wollen ja plus 1 rechnen.
Und wenn da eine 1 steht, dann muss da eine 0 hin und wir müssen
sozusagen diesen Übertrag nach vorne durchs Wort schieben, bis wir mal
auf eine 0 treffen, die wir zu einer 1 machen können.
So funktioniert binäre Addition.
Also wenn da... ja, ist schon richtig, ich war kurz verwirrt.
Also wenn der schwierige Fall ist, wenn da eine 1 steht, dann müssen
wir das zu einer 0 machen und die Addition ist noch nicht fertig, weil
wir das nach vorne durchschieben müssen.
Wir gehen nach vorne, wir gehen nach links und wenn da wieder eine 1
ist, dann müssen wir wieder zu einer 0 machen, gehen wieder nach
links, bis wir mal auf eine 0 treffen, die wir zu einer 1 machen
können.
Entweder treffen wir auf eine 0 und können die zu einer 1 machen oder
wir treffen... das ganze Wort waren nur lauter Einsen und wir müssen
sozusagen eine Stelle mehr machen und ganz vorne noch eine 1
reinschreiben.
Das ist dieser zweite Fall.
In dem zweiten Fall sind wir dann sofort fertig.
In dem anderen Fall, wenn wir jetzt die 0 gefunden haben, die wir
endlich zu einer 1 machen konnten, dann gehen wir jetzt in diesen
Zustand Q3 und Q3 bewegt den Leseschreibkopf nach links, nachdem diese
Summation, diese Aufsummierung fertig ist und wir keinen Übertrag mehr
zu verarzten haben.
Es geht einfach nur nach links und lässt alles gleich, bis wir ganz am
Ende, ganz am Anfang des Wortes sind und in den akzeptierenden
Endzustand gehen.
Es gibt eine kurze Frage, hier hat jemand seinen Geldbeutel in der
vorigen Vorlesung liegen lassen.
Liegt der vielleicht hier irgendwo?
Ich glaube, wir sind jetzt durch mit diesem Fall und jetzt diese Q4,
Q5 Zustände, die sind einfach nur dafür, für den Sonderfall da, dass
die Eingabe exakt eine 0 ist.
Jetzt können wir uns da kurz nochmal überzeugen davon, wenn die
Eingabe mit zwei oder mehr Nullen anfängt, dann würden wir von hier
vorne diese 0 lesen und lassen und sobald wir jetzt hier noch eine 0
lesen würden oder eine 1, was ja beides verboten wäre, dann ist hier
gar kein Übergang spezifiziert und sie erinnern sich, das heißt für
uns, die Maschine stoppt und akzeptiert nicht.
Diskutieren wir ganz kurz, was denn der Unterschied ist zwischen
Wörter entscheiden oder Sprachen akzeptieren, also einfach nur in
einem ausgezeichneten Endzustand halten oder zusätzlich noch eine
gewünschte Ausgabe machen.
Das klingt ja nach sehr viel mehr, noch zusätzlich eine gewünschte
Ausgabe zu machen, zum Beispiel das Ergebnis von so einer Addition
aufs Band zu schreiben.
Tatsächlich sind diese beiden Fragestellungen aber sehr verwandt.
Also wir hatten ja gesagt, eine Turing-Maschine akzeptiert die
Sprache, wenn sie für jedes Wort in der Sprache auf einem
akzeptierenden Endzustand stoppt und für jedes Wort nicht in der
Sprache das Nicht tut.
Und die Sprache ist entscheidbar, das hatten wir auch schon gesagt,
wenn sie immer stoppt und akzeptierend stoppt genau dann, wenn das
Wort in der Sprache ist.
Und eine Funktion heißt berechenbar, hatten wir gerade auch, wenn es
eine Turing-Maschine gibt, die diese realisiert.
Also wenn die Funktion, die ist eine partielle Funktion, wann immer
die nicht undefiniert ist, muss die Turing-Maschine akzeptieren und
nicht nur akzeptieren, sondern zusätzlich muss dann am Ende auf dem
Band auch genau das stehen, was dieser Funktionswert f von w
behauptet.
Und jetzt ist es aber so, dass tatsächlich diese zusätzliche
Anforderung, dass es auf dem Band stehen soll, ganz eng verwandt ist
mit akzeptieren oder nicht akzeptieren.
Man kann zum Beispiel, wenn man eine Turing-Maschine hat und M heißt
die und die stoppt auf allen Ausgaben, auf allen Eingaben.
Die geht nie in diesen unendlich Fall.
Die geht immer nur in den ersten Fall oder in den zweiten Fall.
Dann kann man sie so modifizieren, dass sie dann in zwei
ausgezeichneten Zuständen stoppt.
Und zwar machen wir aus dem M eine neue Turing-Maschine M-Schlange.
Diese neue Turing-Maschine hat zwei Zustände, neue Zustände Qj und Qn.
Und die modifizierte Turing-Maschine, die wird immer akzeptieren,
immer.
Also die Sprache, die die Turing-Maschine akzeptiert, ist einfach
trivial, weil es alles akzeptiert.
Aber die Frage ist, was steht auf dem Band am Ende.
Sie akzeptiert in Qj oder in Qn, das sind die einzigen beiden
akzeptierenden Endzustände.
Und sie geht in Qj genau dann, wenn das W von der ursprünglichen
Maschine akzeptiert wurde.
Und in Qn andernfalls, das habe ich jetzt hier noch gar nicht, ich
bringe gerade Sachen durcheinander, das wird wahrscheinlich auf der
nächsten Folie sein.
Also das ist jetzt einfach nur, sie soll in Qj laufen, wenn
akzeptiert, wenn die ursprüngliche Maschine akzeptiert und in Qn
laufen, wenn die ursprüngliche Maschine stoppt und nicht akzeptiert.
Und dann können wir sozusagen in welchem Endzustand sie landet
ablesen, was die ursprüngliche Maschine macht.
Und die Sprache ist dann also genau dann entscheidbar, wenn es Turing
-Maschinen gibt, die genau zwei Zustände zum Stoppen haben und die
Wörter sind in der Sprache die, die in Qj überführen.
Ihre Aufgabe für heute ist, können Sie diese Modifikation M-Schlange
von M finden?
Genau, das ist noch ein bisschen einfacher als was ich gerade im Kopf
hatte.
Einfach nur gegeben, irgendeine Turing-Maschine als Blackbox, die hat
irgendwo akzeptierende Endzustände, die hat irgendwo diese Nichts-mehr
-tun -Übergänge und die wird immer in einen von diesen beiden
Kategorien landen.
Wir haben gesagt, die stoppt immer, die kommt in keine
Endlosschleifen.
Dann ändern Sie diese Turing-Maschine so, indem Sie zwei Zustände
hinzufügen, Qj und Qn und Übergänge hinzufügen, sodass wir sagen, wenn
wir einen akzeptierenden Endzustand laufen, soll die neue in Qj laufen
und wenn wir in so einen stehenbleibenden Übergang laufen, soll die in
Qn laufen.
Das sollte hoffentlich nicht so schwierig sein.
Und jetzt kann man das machen, was ich gerade schon im Kopf hatte.
Man kann noch weitergehen, man kann sagen, wir wissen, die läuft jetzt
immer in Qj oder in Qn und dann können wir auch noch von dort sagen,
okay, das sind noch nicht Finalzustände, sondern Sie dann anweisen,
lösche alles, was auf dem Band drauf ist, was Du gekriegt hast oder
was Du zwischendurch darauf geschrieben hast, um Deine Antwort zu
generieren, lösche alles und schreibe einfach nur eine einzelne Eins
drauf.
Oder von Qn auch lösche alles und schreibe auf das Band einfach nur
eine Null.
Das ist sozusagen, das Programm soll einfach als Ausgabe auf die
Kommandozeile oder so eine Eins oder eine Null schreiben, je nachdem,
ob das Wort akzeptiert wird oder nicht.
Und das Programm soll aber immer akzeptieren, also es soll immer
ordentlich beenden, sodass wir die Ausgabe auch lesen können.
Und das wäre dann sozusagen die Funktion, die dort realisiert wird,
wäre die charakteristische Funktion zu dieser Sprache.
Die wird mit einem Chi und einem L geschrieben.
Für jedes Wort sagt sie einfach nur, da kommt eine Null oder eine
Eins.
Und zwar nach diesem Schema, da soll eine Eins stehen, wenn das Wort
in der Sprache ist und eine Null, wenn das Wort nicht in der Sprache
ist.
Und dann können wir also sagen, eine Sprache ist genau dann
entscheidbar, wenn diese Funktion berechenbar ist.
Das ist einfach nur eine Aneinanderkettung unserer Definition, die wir
so hatten.
Und eine Sprache ist semi-entscheidbar, wenn diese partielle Funktion,
die in diesem akzeptierenden Stopp-Fall das Band löscht und eine Eins
schreibt.
Und in anderen Fällen ist egal, was sie auf das Band tut, wenn die
berechenbar ist.
So, jetzt haben wir ein bisschen so ein Gefühl dafür gekriegt, für
diese Turing-Maschinen.
Wir haben schon ein bisschen Gefühl dafür gekriegt, dass sie
vielleicht mächtiger sind als die Endlichen Automaten.
Wir haben diese Sprache gesehen, Null hoch N, Eins hoch N, die erkannt
werden kann von Turing-Maschinen, aber nicht von Endlichen Automaten.
Jetzt ist es nicht nur einfach ein weiterer Schritt von Endlichen
Automaten auf Turing-Maschinen und wenn man sich jetzt noch mehr
anstrengt, kommt irgendwie nächste Woche das noch bessere, so ist es
nicht.
Tatsächlich gibt es die sogenannte Churchill-These, die besagt, jede
berechenbare Funktion, also die im intuitiven Sinne berechenbar ist,
ist von einer Turing-Maschine berechenbar.
Die besagt also, Turing-Maschinen sind das Mächtigste, was möglich
ist.
Wenn etwas überhaupt irgendwie machbar ist, dann kann es eine Turing
-Maschine.
Natürlich ist es, also das ist die Interpretation, Turing-Maschinen
sind stark genug, um ganz allgemeine Algorithmen, alle möglichen
Algorithmen zu erfassen, die sie sich ausdenken können.
Wenn man etwas machen kann, berechnen kann, dann kann man das mit
einer Turing-Maschine.
Und genau, die Bemerkung, die ich jetzt gerade machen wollte, ist, das
ist nur eine These, das ist nicht ein Fakt, das kann man auch nicht
beweisen, das hat jetzt erstmal so keinen Wahrheitsgehalt, weil
überhaupt nicht klar ist, was intuitiv berechenbar heißen soll.
Aber es ist eben so, dass es in der Informatik allgemein akzeptiert
wird, dass die Turing-Maschine das stärkste und mächtigste
Berechnungsmodell ist.
Weil alles andere ist irgendwie nicht intuitiv, im intuitiven Sinne
berechenbar.
Warum?
Ja, warum ist es, also vielleicht gibt es ja noch was, wir wissen es
nicht, aber bisher hat zumindest niemand etwas gefunden, was besser
ist.
Was irgendwie deterministisch arbeitet und irgendwelche Entscheidungen
trifft und für irgendwelche Eingaben, irgendwelche Ausgaben
produziert, in einem sinnvollen Sinne.
Was nicht auch von der Turing-Maschine gemacht werden kann.
Also es gab Versuche natürlich jetzt, die Turing-Maschine noch stärker
zu machen, sie ist ja doch schon ziemlich eingeschränkt, dieser
Lesekopf kann immer nur ein Zeichen sehen und dieses Band ist
irgendwie nur so eindimensional und alles mögliche und es gibt endlich
viele Zustände.
Es gab Ansätze, das zu verbessern und es hat sich aber immer wieder
herausgestellt, dass diese ganzen extra Gimmicks, die man der Maschine
gegeben hat, auch simuliert werden konnte von der normalen Turing
-Maschine.
Und deswegen bleiben wir dabei, weil sie so schön einfach ist, aber
trotzdem mächtig.
Wir wollen ein paar von diesen Erweiterungen mal kurz diskutieren.
Also man könnte zum Beispiel auf die Idee kommen, der Turing-Maschine
mehrere Lese- oder Schreibköpfe zu geben.
Dann kann sie gleichzeitig auf mehrere Stellen des Rechenbandes
zugreifen und sozusagen mehr Input-Informationen kriegen, wie jetzt
weiter zu verfahren wäre.
Es wäre so, wie wenn Programme, die sie programmieren, in mehreren
Zeilen gleichzeitig was tun könnten.
Könnte man sich als theoretisches Berechnungsmodell überlegen.
Dann sagen wir mal, n ist die Anzahl dieser Lese-Schreibköpfe und dann
wäre die Übergangsfunktion, die hat jetzt eine endliche Kontrolle, ist
in einem Zustand und kriegt ein n-Tupel als Input.
Was Lesekopf 1 gerade liest, was Lesekopf 2 gerade liest, was Lesekopf
3 und so weiter bis n gerade liest.
Und die Anweisung würde dann sein, gehe in den nächsten Zustand, sage
Lesekopf 1, was er schreiben soll, sage Lesekopf 2, was er schreiben
soll, Lesekopf 3, was er schreiben soll und so weiter.
Und gebe auch noch für jeden von den Leseköpfen jetzt unabhängig an,
ob Lesekopf 1 jetzt einen Schritt nach links, rechts oder gar nichts
machen soll, Lesekopf 2 links, rechts oder gar nichts und so weiter.
Auch die Zustände, man kann jetzt auch sagen, das sieht ein bisschen
einschränkend aus, dass wir nur einen Zustand haben, vielleicht wollen
wir sozusagen für jeden Lesekopf einen eigenen Zustand haben.
Auch das ist möglich und dann wäre sozusagen ein Zustand ein n-Tupel
von Zuständen.
Dann simuliert man einen eigenen Zustand für jeden Lese-Schreibkopf.
Wobei, was der erste Kopf macht, der darf dann auch gucken, in welchem
Zustand der zweite Kopf gerade ist oder was der dritte Kopf gerade
liest oder so.
Also sehr allgemein.
Natürlich gibt es dann ein paar Kleinigkeiten, um die man sich kümmern
muss, also eine Prioritätenregel, wenn jetzt mehrere von diesen Köpfen
auf das gleiche Symbol zeigen und die kriegen jetzt unterschiedliche
Anweisungen, was sie damit zu tun haben, dann muss man das irgendwie
klären, wer da jetzt Priorität kriegt.
Aber es hat sich herausgestellt, dass man mit einer ganz normalen
Turing -Maschine, mit einem Lese-Schreibkopf genau das gleiche kann,
wie mit der.
Wenn man auf die Idee kommt, vielleicht mehrere Bänder zu benutzen,
dann wäre die Übergangsfunktion, würde sich dahingehend ändern, wir
hätten einen Zustand, wir hätten ein Bandsymbol, was wir gerade lesen,
aber dann kriegen wir noch die zusätzliche Information, von welchem
Band kommt es jetzt gerade.
Einfach nur der Index, das kommt übrigens von Band 3 oder so.
Und dann können wir sagen, okay, gehe nach links, rechts oder bleibe
stehen und springe eventuell in den Band, gehe auf Band 2 oder so.
Aber auch das hat sich herausgestellt, das kann nicht mehr als eine
normale Turing-Maschine, so wie wir sie gerade definiert haben.
Jetzt kann man natürlich das kombinieren, man kann sagen mehrere
Bänder und mehrere Köpfe gleichzeitig, also wenn wir M-Bänder und N
-Köpfe haben, dann wäre die Übergangsfunktion so ein Monstrum hier, wo
wir hier vorne für jeden Kopf ein Zeichen lesen und für jedes dieser N
-Zeichen kriegen wir noch gesagt, von welchem Band kommt denn das
jetzt gerade.
Und wir können dann jedem Kopf sagen, er soll das Zeichen ändern und
links, rechts gehen oder stehen bleiben und eventuell noch das Band
wechseln, aber auch das kann nicht mehr als eine normale Turing
-Maschine.
Da könnte man denken, ja, vielleicht machen wir das Band irgendwie
höherdimensional, statt irgendwie nur auf einer Linie zu arbeiten,
arbeiten wir jetzt im Zweidimensionalen auf einem Feld, auf einem
Arbeitsfeld oder dreidimensional oder siebzehndimensional und hat dann
als Richtungsanweisung, kann man dann nicht nur links, rechts gehen,
sondern man kann nach links oder nach oben oder nach rechts oder
stehen bleiben oder nach unten und so weiter.
Das klingt ja irgendwie noch mächtiger, kann aber auch nicht mehr als
die normale Turing-Maschine.
Und die Churchill-These sagt halt, egal was man sich dort ausdenkt, es
wird nicht mehr können als eine normale Turing-Maschine.
Wahrscheinlich.
Ja, natürlich bei diesen ganzen Sachen müsste man jetzt noch genau
spezifizieren, was ich nicht getan habe, wann stoppt die, wann
akzeptiert denn so eine Mehrkopf-Turing-Maschine, wenn jetzt einer von
diesen, oder wenn wir mehrere Zustände für jeden Kopf hätten und einer
von diesen Zuständen sagt jetzt akzeptieren und ein anderer sagt aber
nicht akzeptieren und sowas, muss man natürlich, diese ganzen
Kleinigkeiten muss man noch regeln oder wenn die auf die gleiche
Stelle verschiedene Symbole schreiben wollen, wer gewinnt dort.
Deswegen, alle diese angegebenen Modifikationen, ein paar davon werden
glaube ich auch in der Übung besprochen, wie genau man sowas zeigen
kann, dass es durch eine Ein-Kopf-Ein-Band-Turing-Maschine simuliert
werden kann.
Genau, alle diese Modifikationen können so simuliert werden, durch
eine Ein-Band-Ein-Kopf-Turing-Maschine, so wie wir sie kennenlernen
und deswegen werden wir uns einfach nur darauf beschränken, wir haben
einen Kopf, ein Band, zu beiden Seiten unendlich und fertig.
Gut, das war es zur Churchenthese.
Also Sie haben jetzt sozusagen in der Vorlesung, wir haben angefangen
mit endlichen Automaten, die waren relativ simpel, die haben ganz
unten in der Hierarchie gelebt und konnten ganz einfache Sachen
machen, aber dann auch ganz schnell Sachen, die irgendwie nicht mehr
möglich waren, Klammerausdrücke oder dieses 0 hoch N, 1 hoch N oder
Zählen oder irgendwas.
Die konnten auch nichts ausgeben, die konnten nur Ja, Nein sagen.
Und jetzt haben wir die Turing-Maschinen kennengelernt und sind ganz
nach oben in die Hierarchie gesprungen und haben die mächtigsten
kennengelernt, die wir kennen und vielleicht die mächtigsten, die es
gibt.
Die können sehr viel mehr als die endlichen Automaten, die können noch
eine Ausgabe machen, damit können wir quasi Programme im Computer
theoretisch erfassen.
Jetzt habe ich aber noch, genau, diese Mächtigkeit kann man jetzt
durch die universelle Turing-Maschine vielleicht am besten sehen.
Also wir hatten bisher immer nur eine Turing-Maschine, die hatte eine
Aufgabe.
Das ist so etwas wie ein Programm oder eine Funktion innerhalb eines
Programms.
Die hatte eine Aufgabe, die kriegte einen Input und die sollte einen
Output machen.
Und irgendwie zum Beispiel auf eine Zahl plus 1 drauf addieren oder
entscheiden, ob dieses Wort, diese Eingabe genau die Form 0 hoch N, 1
hoch N hat oder irgendwie sowas.
Und was wir jetzt aber wollen ist, wir wollen jetzt eine allgemeine
Turing -Maschine, die kann alles.
Die kann nämlich als Eingabe kriegen, ein Programm und eine spezielle
Eingabe für das Programm.
Und die Turing-Maschine lässt dieses Programm laufen auf dieser
Eingabe, schaut, was ist die Ausgabe und gibt uns diese Ausgabe aus.
Also diese universelle Turing-Maschine ist sowas wie ein Computer.
Quasi, wenn Sie Ihr Betriebssystem starten, dann ist es ja auch nur
ein Programm.
Ein Programm, was fähig ist, wenn man Ihnen andere Programme gibt und
Eingaben zu dem Programm, diese Programme laufen zu lassen und Ihnen
zu sagen, was denn die Ausgabe des anderen Programms auf dieser
Eingabe ist.
Also das ist die universelle Turing-Maschine.
Das ist eine Turing-Maschine, so hingeschrieben, die kann als Eingabe
ein Programm oder eine Turing-Maschine und eine Eingabe für die Turing
-Maschine kriegen und dann die da drauf simulieren.
Okay, das wollen wir jetzt machen.
Und die erste Frage ist natürlich, wie gibt man einer Turing-Maschine
eine Turing-Maschine?
Wie soll eine Eingabe aussehen?
Wir haben immer irgendwie davon geredet, Wörter aus dem Alphabet,
meistens 0,1 zu geben.
Naja, und das ist genau das, was wir tun werden.
Wir werden eine Turing-Maschine kodieren als ein Wort in 0,1.
Und das machen wir, indem wir zuallererst mal sagen, die Turing
-Maschine, die wir jetzt kodieren wollen, dieses Programm soll die
richtige Form haben, das normiert nennen wir das jetzt hier.
Also wir sagen, die Zustände sollen durchnummeriert sein von 1 bis N.
Das Eingabe-Alphabet soll nummeriert sein von A1 bis AK.
Das Band-Alphabet soll natürlich das Blank haben, es soll natürlich
auch A1 bis AK können und dann kann man vielleicht noch zusätzliche
Sachen aufs Band schreiben für diese Turing-Maschine K plus 1 bis L.
Der Startzustand soll auf jeden Fall der erste sein und als
akzeptierenden Endzustand haben wir nur den zweiten.
Keinen anderen.
Man kann das immer, das beschränkt nicht die Allgemeinheit.
Das heißt, für jede Turing-Maschine kann ich eine normierte Turing
-Maschine mit diesen Anforderungen konstruieren, die das gleiche tut.
Und jetzt haben wir eine normierte Turing-Maschine und die können wir
jetzt kodieren als ein Wort 0,1.
Irgendwas, um es dann der universellen Turing-Maschine als Eingabe zu
geben.
Und wie tun wir das?
Das ist die sogenannte Gödel-Kodierung oder die Zahl, Gödel-Nummer
einer Turing-Maschine.
Die geht wie folgt, also die Turing-Maschine ist hier oben gegeben in
normierter Form, dieses 7-Tupel und dann bezeichnen wir mit diesen
eckigen Klammern, das sind die Spitze-Klammern, ja, Spitze-Klammern M.
Das hier soll jetzt ein Wort sein aus 0,1 Hochstern.
Und das hat eine folgende Form.
Wir kodieren erstmal einen Übergang.
Ein Übergang sieht jetzt so aus, von irgendeinem qi und aj geht es in
ein qr und as, das sind ja jetzt hier die Zustände und die Zeichen und
irgendeine Richtung links, rechts nicht bewegen, was wir einfach mit
d1, d2, d3 machen.
Also dann kommt das hier in irgendein dt.
Und alles, was eigentlich jetzt interessiert, ist die Indizes.
Der wievielte Zustand ist es?
Das wievielte Zeichen des Eingabe-Alphabets ist es?
Der wievielte Zustand ist dieser Zielzustand?
Das wievielte Zeichen ist dieses, was jetzt ersetzt wird?
Und die wievielte Möglichkeit unter diesen dreien ist jetzt diese
Bewegungsanweisung?
Und das kodieren wir durch das hier.
Wir sagen einfach, ich schreibe so viele Nullen, also schreibe i
Nullen, wenn das hier vorne der i-te Zustand war.
Dann mach eine 1 als Trenner.
Und dann schreibe j Nullen, wenn das j-te Zeichen gerade gelesen wurde
für diesen Zustand.
Dann mach wieder eine 1 als Trenner.
Und dann schreibe eine r Nullen, wenn es der r-te Zustand ist, in dem
es abbildet.
1 als Trenner.
Mach s Nullen, wenn es das s-te Zeichen ist, was da geschrieben werden
soll.
Eine 1 als Trenner.
Und mach T Nullen, wenn es hier sozusagen die t-te Richtungsanweisung
ist.
Also einfach nur eine Null für links, zwei Nullen für rechts, drei
Nullen für nichts.
Und das, was wir da kriegen, diesen String hier, den nennen wir
einfach Code von Übergang.
Also irgendwie das Code-Wort des Übergangs.
Und jetzt kann ich die ganze Turing-Maschine codieren dadurch, dass
ich sage, okay, irgendwie drei Einsen als Erkennungszeichen für, hier
fängt die Turing-Maschine an.
Dann schreibe ich das Code-Wort des ersten Übergangs, irgendeiner,
einen Übergang.
Dann schreibe ich zwei Einsen als Erkennungszeichen, dass hier ein
Übergang fertig ist und ein neuer Übergang anfängt.
Dann schreibe ich das Code-Wort des zweiten Übergangs, wieder zwei
Einsen und so weiter.
Und am Ende, nachdem ich alle Z-Übergänge so codiert habe, schreibe
ich nochmal drei Einsen als Zeichen.
Die Codierung ist zu Ende.
Das heißt, die Werte werden dort unnäher durch Nullen einfach
beschrieben.
Diese Indizes, ITER-Zustand sind I-Nullen dort und dort.
Und die Einsen sind nur Begrenzungen, wobei eine einzelne Eins ist
eine Begrenzung innerhalb dieses Zustands.
Zwei Einsen hintereinander ist die Begrenzung zwischen zwei
Beschreibungen von zwei verschiedenen Zuständen und drei Einsen ist
die Begrenzung von der ganzen Turing-Maschine Anfang und Ende.
Und so kann jede Turing-Maschine überführt werden in so ein Wort aus 0
,1 Sternen.
Und wenn man die Codierung kennt, dann kriegt man auch all die
Informationen aus dem Wort aus 0,1 Sternen wieder raus, was die Turing
-Maschine tut.
Jedes Wort aus 0,1 Sternen beschreibt höchstens eine Turing-Maschine.
Natürlich gibt es Wörter, die jetzt dieser Codierung einfach nicht
entsprechen, zum Beispiel 0,0,0, jede codierte Turing-Maschine muss ja
mit 1,1,1 anfangen.
Wir sagen einfach, wenn das Quatsch ist, wenn es keine Turing-Maschine
darstellt, wenn es nicht eine Gödel-Darstellung, eine Gödel-Zahl von
einer Turing-Maschine ist, dann sagen wir einfach, dann gehört das zu
einer Turing-Maschine, die akzeptiert die leere Sprache.
Die universelle Turing-Maschine, jetzt haben wir schon mal den Input,
die kriegt die Gödel-Codierung einer Turing-Maschine und dann noch ein
Input -Wort W, OBDA aus 0,1 Sternen, binär codiert, was sozusagen
jetzt als Eingabe für diese Turing-Maschine M gedeutet werden soll.
Und die universelle Turing-Maschine, die baut sich sozusagen, die
liest diese Gödel-Codierung und liest das Wort W und kann jetzt die
Maschine M auf W simulieren.
Die hat alle Informationen, die sie braucht.
Ich werde das jetzt nicht explizit ausführen, wie das geht, aber im
Prinzip, wir gucken, die universelle Turing-Maschine weiß, okay, wir
wären jetzt in Startzustand Q1 und wir würden jetzt gerade hier hinten
dieses erste Zeichen von W lesen.
Dann geht sie zurück und guckt nach, was denn der Übergang sagt für
ich bin in dem Zustand und ich lese dieses Zeichen.
Dann kann sie sich das rauslesen, okay, das müsste also jetzt gemacht
werden auf dem Rechenband, dann geht sie wieder nach vorne und nach
hinten, tut das auf dem Rechenband und so weiter.
Und so kann sie das simulieren.
Hier ein Beispiel, also wenn ich jetzt so eine ganz einfache Turing
-Maschine habe, die hier drei Zustände, zwei Eingabealphabet und
irgendwie nur vier Übergänge hat, ich weiß keine Ahnung, was sie tut,
dann wäre die sozusagen codiert zusammen mit der Eingabe 1 0 1 1, also
ich möchte diese Turing-Maschine, auf diese Turing-Maschine möchte ich
1 0 1 1 loslassen und frage mich, was da passiert, dann würde ich der
universellen Turing-Maschine diesen String hier geben.
Vielleicht ein bisschen farblich codiert, also hier, das sind die drei
Einsen, die ansagen, hier fängt die Gödel-Codierung an, dann das hier
ist der erste von diesen drei Übergängen, dann zwei Einsen heißt,
Achtung, jetzt kommt ein neuer Übergang, ein neuer Übergang, wieder
zwei Einsen, ein neuer Übergang, das sind die vier, diese vier blauen
Blöcke sind die vier Übergänge hier oben, dann kommen wieder drei
Einsen, die mir sagen, okay, Gödel-Codierung ist fertig und dann kommt
am Ende in rot die Eingabe.
Aber natürlich, die universelle Turing-Maschine kriegt die jetzt nicht
farbcodiert, sondern muss es aus dieser Anzahl der Einsen und so
rauslesen.
Jetzt eine kleine Definition und dann wird es wieder handfester.
Also, wenn wir jetzt ein Wort haben, W aus 0,1, dann wollen wir mit T
unten W die Turing-Maschine bezeichnen, die diesem Wort entspricht,
wenn es jetzt eine ordentliche Gödel-Nummer wäre.
Also ein paar von diesen 0,1 Strings sind ordentlich codierte Turing
-Maschinen und ein paar sind es nicht.
Und wenn es eine ordentlich codierte Turing-Maschine ist, dann soll
die einfach TW heißen.
Und wenn, das hatte ich gerade schon gesagt, wenn es irgendwie Quatsch
ist oder so, irgendwie keine ordentliche codierte Turing-Maschine,
dann soll das einfach dann sei TW, trotzdem definiert, nämlich als
eine Turing-Maschine, die einfach die leere Sprache akzeptiert.
Und dann frage ich mich jetzt, was ist die Sprache, die diese Turing
-Maschine akzeptiert?
Also was ist L von TW?
Also das ist die Sprache, die von dieser Turing-Maschine akzeptiert
wird.
Und so kriege ich also für jedes Wort aus 0,1, kriege ich eine Sprache
aus 0,1 Stern.
Und die Sprachen, die ich da kriege, sind alle Sprachen, die von
Turing -Maschinen akzeptiert werden können.
Aber irgendwie, merken Sie jetzt schon, gibt es hier ein bisschen so
ein Problem.
Ich habe für jedes Wort aus 0,1, kriege ich eine Menge, eine
potenziell unendlich große Menge von Worten aus 0,1 Stern.
Und irgendwie gibt es doch sehr viel mehr potenzielle Sprachen, als es
Worte gibt.
Und da ist auch das Problem jetzt, dass wir merken, irgendwie kann es
gar nicht sein, dass jede Sprache akzeptiert werden kann durch eine
Turing -Maschine.
Weil irgendwie gibt es viel zu viele davon.
Es gibt ja nur, naja, zwar auf beiden Seiten unendlich, aber das sind
andere Formen von Unendlichkeit in der Hierarchie.
Ich werde es nicht mathematisch machen, aber wir werden uns jetzt
darum kümmern, dass es wirklich Sprachen gibt, die nicht von der
Turing -Maschine akzeptiert werden können.
Obwohl es eigentlich sozusagen, wenn man jetzt zufällig aus diesem 0,1
Stern eine zufällige Sprache rauswählen würde, dann wäre die mit
Wahrscheinlichkeit 100% nicht entscheidbar, nicht von der Turing
-Maschine.
Es ist trotzdem ziemlich schwierig, jetzt wirklich eine konkret zu
konstruieren.
Und wir konstruieren eine konkrete, und das wird die Diagonalsprache
sein, die wir mit LD bezeichnen.
Okay, wie konstruieren wir diese Sprache?
Das Erste ist, wir betrachten die Wörter aus 0,1 Stern in kanonischer
Reihenfolge, das heißt der Länge nach aufsteigend, zuerst das leere
Wort, das haben wir ganz am Anfang schon mal gemacht, erst das leere
Wort, dann die Wörter der Länge 1, die Wörter der Länge 2, dann die
Wörter der Länge 3, dann die Wörter der Länge 4 und so weiter.
Und innerhalb der gleichen Länge, also wenn ich jetzt die Wörter der
Länge 3 mir angucke, will ich jetzt nur wissen, in welcher Reihenfolge
will ich mir die anschauen, und dann mache ich es lexikografisch, so
wie sie im Lexikon auftauchen würden, oder als Binärzahl
interpretiert, aufsteigende Zahlen.
Okay, irgendwie festgelegt, lexikografisch.
Das ist die Reihenfolge, in der ich mir die Wörter anschaue.
Und dann hat jedes Wort sozusagen einen Index.
Ein Wort ist jetzt wj, irgendein Index j, das ist vielleicht das
zweimillionste Wort in der Liste.
Und dann sage ich mj ist die Turing-Maschine, die das als Gödel-Nummer
hat.
Eventuell habe ich ja Glück, und dieses Wort ist eine echte Kodierung,
das ist eine nicht-triviale Turing-Maschine, höchstwahrscheinlich ist
es eine ziemlich-triviale Turing-Maschine, nämlich die, die leere
Sprache akzeptiert.
Aber okay, so definiere ich mir das.
Die zweimillionste Turing-Maschine ist die, deren Gödel-Nummer dieses
zweimillionste Wort ist.
Jetzt schreiben wir uns das alles auf, diese unendlich vielen Sachen,
in eine Tabelle.
Wir schreiben uns eine Tabelle, die hat zwei Zeilen und Spalten, zwei
Koordinaten, und wir schreiben in die Zeile i und die Spalte j.
Da interessiert uns jetzt das i-te Wort in unserer Liste und die j-te
Turing -Maschine in unserer Liste.
Und was passiert, wenn ich dieser j-ten Turing-Maschine das i-te Wort
als Eingabe gebe?
Und in die Tabelle schreibe ich jetzt rein, an dieser Zelle der
Tabelle, Zeile i, Spalte j, da schreibe ich eine 1 rein, wenn die j-te
Turing -Maschine das i-te Wort akzeptiert.
Also wenn es dann in Fall 1 landet, sie stoppt in dem finalen
Endzustand.
Und da schreibe ich eine 0 rein, sonst.
Also wenn es zum Beispiel, wenn diese Turing-Maschine die leere
Sprache akzeptiert, wenn es irgendwie keine ordentlich kodierte, dann
ist diese ganze j-te Spalte lauter Nullen.
Ansonsten für eine feste Turing-Maschine, die jetzt wirklich sinnvoll
ist, dann hätte ich jetzt eine Spalte und dann steht dann für jedes
Wort immer akzeptiert oder nicht akzeptiert, immer 1 oder 0.
So, das ist so eine Tabelle.
Also die sieht dann...
Und jetzt aus dieser Tabelle, das ist einfach nur so ein theoretisches
Konstrukt, definiere ich mir die Diagonalsprache.
Und die Diagonalsprache ist jetzt eine Menge von Wörtern.
Und zwar gucke ich mir an, ob das Wort wi, also jedes Wort hat ja
einen Index in meiner Sortierung, und ich gucke mir an, ob dieses Wort
wi von der Turing-Maschine mi akzeptiert wird.
Also ich füttere sozusagen die Turing-Maschine mit ihrer eigenen
Gödelkodierung als Input.
Das kann, weiß ich nicht, mehr oder weniger sinnvoll sein.
Wenn die Turing-Maschine, was weiß ich, irgendwie Binärzahlen nimmt
und plus 1 addiert, dann wird sie das halt tun mit dieser komischen
Gödelkodierung.
Oder einfach nur entscheidet, ob der String der Form 0 hoch N, 1 hoch
N ist.
Dann wird sie das halt tun mit ihrer eigenen Gödelkodierung als
Eingabe.
Kann sie ja tun.
Das tue ich und schaue mir an, die, wo die Turing-Maschine ihre eigene
Gödelkodierung sozusagen mag, akzeptiert.
Und das sind die Worte in der Diagonalsprache.
Das heißt, wir gucken uns in dieser großen Tabelle im Prinzip die
Zeilen an oder die Wörter an, wo in der entsprechenden Diagonalstelle
eine 0 steht.
Oh, Entschuldigung, nicht.
Oh Gott, ich komme immer wieder durcheinander.
Nicht, die Diagonalsprache sind da, wo die Turing-Maschine ihre eigene
Kodierung nicht akzeptiert.
Also so ist diese Tabelle, so muss man sich die vorstellen.
Ich habe in diesen Zeilen jetzt also Wi als Wort gesehen und dann Wi
gehört zu einer Turing-Maschine, wenn ich Wi als Gödelkodierung
interpretiere und dann frage ich mich, okay, wenn es jetzt eine Turing
-Maschine ist und diesen Input kriegt, wird dieser Input akzeptiert
oder nicht?
Sagen wir mal, der Input wird nicht akzeptiert.
Dann steht in der Tabelle eine 0 und dann ist das Wort Wi in der
Sprache.
Zum Beispiel, weil das hier könnte so eine komplette Nullspalte sein.
Vielleicht ist das einfach keine ordentliche Gödelkodierung.
Aber manchmal haben wir vielleicht Glück und irgendwie, das ist eine
ordentliche Gödelkodierung und dann ist das eine ordentliche Turing
-Maschine und die hat ein paar Einsen in ihrer Spalte und vielleicht
ist gerade an dieser Stelle, wenn sie ihre eigene Kodierung als Input
kriegt, eine Eins.
Und wenn das der Fall ist, dann sagen wir, okay, das Wort ist nicht in
der Diagonalsprache.
Und jetzt ist diese Diagonalsprache die erste Sprache, die wir zeigen,
dass sie nicht entscheidbar ist.
Es gibt keine Turing-Maschine, die entscheidet, ob ein Wort, ob eine
Turing -Maschine ihre eigene Kodierung akzeptiert.
So ist der Beweis, per Widerspruch.
Wäre die Sprache entscheidbar, dann gäbe es eine Turing-Maschine M,
die die Sprache entscheidet.
Also sie muss stets halten, sie darf nicht unendlich lange laufen und
sie muss in einem akzeptierenden Zustand halten, genau dann, wenn das
Wort aus der Diagonalsprache kommt.
Jetzt.
Diese Turing-Maschine ist eine Turing-Maschine, das heißt, sie taucht
in...
die hat eine Gödel-Kodierung.
Das heißt, die ist irgend so ein Mi in unserer Liste aller Turing
-Maschinen.
Und dieses i gucke ich mir an.
Dieses Mi ist jetzt wieder als Wort gesehen, das i-te Wort in unserer
Liste.
Und jetzt schaue ich mir an, was passiert denn mit diesem i-ten Wort?
Ist es jetzt in der Diagonalsprache oder nicht?
Wenn das i-te Wort, was sozusagen die Gödel-Kodierung unserer
theoretisch existierenden Turing-Maschine ist, wenn das i-te Wort in
der Diagonalsprache ist, dann wird unsere theoretisch existierende
Turing -Maschine dieses Wort akzeptieren.
Wir haben ja gesagt, nach 2 wird er in der Diagonalsprache akzeptiert.
Wenn das Wort in diesem Fall, wenn das Wort in der Diagonalsprache
ist, dann akzeptiert m das Wort wi wegen 2.
Dass das Wort in der Diagonalsprache ist, heißt aber per Definition
der Diagonalsprache, dass mi wi nicht akzeptiert.
Aber mi ist ja das gleiche wie m.
Also irgendwie beißt sich da die Katze in den Schwanz.
Also die einzige Möglichkeit wäre, dann ist das Wort eben nicht in der
Diagonalsprache.
Wenn das Wort aber nicht in der Diagonalsprache ist, haben wir ein
ähnliches Problem.
mi, nach Definition der Diagonalsprache, akzeptiert dann das Wort
nicht.
Das heißt aber, mi akzeptiert das Wort nicht, das heißt, die Turing
-Maschine müsste das Wort akzeptieren.
Oh Gott.
Okay, also es ist der gleiche Widerspruch.
Also es ist irgendwie alles ad absurdum geführt und es kann so eine
Turing -Maschine nicht geben, weil es unklar wäre, was sie mit ihrem
eigenen Input tun sollte.
Sie würde sich selbst widersprechen.
Wir kriegen jetzt als Korollar auch das Kompliment der
Diagonalsprache, also die, die ich eigentlich schon mal erwähnt habe,
wo die Frage ist, ob eine Turing-Maschine ihre eigene Gödezahl
akzeptiert, ist auch nicht entscheidbar, weil wenn es dort eine Turing
-Maschine gäbe, die das Kompliment entscheiden würde, dann könnten wir
die einfach ummodifizieren, um die Originalsprache zu entscheiden.
Und das wäre dann ein Widerspruch zu der Unentscheidbarkeit der
Diagonalsprache.
Also dieser ganze Beweis, den wir gerade eben hatten, das ist so ein
bisschen dieses Selbstreferenzierende zum Widerspruchführende.
Sie haben das vielleicht schon mal, diese Paradoxien schon mal gehört.
Der Barbier von Hintertupfingen rasiert genau die Männer im Dorf, die
sich nicht selbst rasieren.
Also wenn man sich fragt, rasiert der Barbier diesen Mann?
Wenn der Mann sich selbst rasiert, dann rasiert der Barbier ihn nicht.
Und wenn der Mann sich nicht selbst rasiert, dann macht es der Barbier
dafür.
Und jetzt ist aber die Frage, wer rasiert den Barbier?
Wenn der Barbier sich selbst rasiert, dann muss der Barbier ihn ja
nicht mehr rasieren, weil er sich ja selbst rasiert.
Und wenn er sich nicht selbst rasiert, dann muss er sich rasieren.
Also genau, das ist diese Selbstbezüglichkeit.
Oder auch sehr beliebt ist dieses Deine-Düsen-Trieb-behaupteten
-Orakel, eine allwissende Maschine gebaut zu haben, die auf alle
Fragen korrekt mit Ja oder Nein antwortet.
Onkel Dagobert will die Maschine kaufen, sagt aber, ich bezahle sie
nur, wenn meine Testfrage korrekt beantwortet wird.
Und dann kriegt er die Maschine und er stellt ihr die Frage, wirst du
mit Nein antworten?
Und jetzt ist die Frage, was passiert, die Maschine kann jetzt nicht
mit Ja antworten, dann würde sie ja behaupten, mit Nein zu antworten,
was sie aber nicht getan hat, und sie kann aber auch nicht mit Nein
antworten, weil dann wäre ja die Antwort auf Dagoberts Frage Ja
gewesen.
Genau, und das sind so die Probleme, die wir hier ausnutzen.
Ein bekanntes, vielleicht sogar noch bekannteres Problem, was mit
dieser Selbstreferenzierung und damit einhergehenden
Unentscheidbarkeit behandelt, ist das sogenannte Halteproblem.
Das Halteproblem ist das folgende, es wäre doch schön, Sie haben das
sicherlich alle schon mal erlebt, Sie schreiben irgendwie ein
Stückchen Code, und dann lassen Sie das laufen, und wenn es nicht ganz
trivial ist, dann kann es auch schon mal die Berechnung eine Weile
dauern, und irgendwann sitzen Sie dann davor, und der rechnet und
rechnet und rechnet, und Sie beschleicht so das Gefühl, dass der
eventuell irgendwie in der Endlosschleife oder sowas gelaufen ist.
Sie wissen nicht, wird der jetzt fertig oder nicht.
Und wäre das nicht toll, ein Computerprogramm zu haben, oder den
Compiler zum Beispiel zu haben, der vorher checkt, ob das Ding in der
Endlosschleife laufen wird oder nicht.
Oder vielleicht in dem Programm selber so ein kleines Tool zu haben,
dass das Programm merkt, oh jetzt bin ich in der Endlosschleife, jetzt
breche ich mal lieber ab.
Wäre das nicht toll, so ein Programm zu haben.
Dann würden Sie das Halteproblem lösen.
Das Halteproblem fragt, eingegeben hier in diesen spitzen Klammern,
eine Gödel-Codierung von einer Turing-Maschine, also einfach nur ein
Programm, mit Eingabe, wird das in der Endlosschleife laufen oder
nicht.
Und das soll Ihnen dann sagen, ja, das wird in der Endlosschleife
laufen, oder nein, das wird auf jeden Fall fertig.
Entweder durch Fehlermeldung oder durch Akzeptieren.
Und dann könnten Sie sozusagen das Programm vorher fragen, wird das in
der Endlosschleife laufen und wenn er ja sagt, Ihr Programm kann ich
erst starten, das wäre doch toll.
Das Problem ist aber, so ein Programm kann es nicht geben.
Weil, wenn ich so ein Programm hätte, dann könnte ich jetzt ein neues
Programm schreiben.
Also sagen wir mal, ich habe so ein Programm, ich benutze es als
Blackbox, wie auch immer Sie das bewerkstelligt haben, dieses
Haltprogramm zu schreiben.
Das macht es aber korrekt, Sie behaupten, das macht es korrekt.
Dann schreibe ich ein Programm, das ist diese grüne Box.
Und was das Programm tut, ist, das wird erst mal Ihr Programm
aufrufen, mit Ihr Halteprogramm, und dann in Abhängigkeit davon, was
Ihr Programm behauptet, also wenn Ihr Programm behauptet, ja, das wird
halten, dann sende ich mein Programm ganz intentionell in eine
Endlosschleife.
Und wenn Ihr Programm sagt, nee, das wird in eine Endlosschleife
laufen, dann sage ich, ok, einfach Stopp und beende.
Also wenn Sie Ihr Programm hätten, dann würde ich mein Programm
machen.
Und mein Programm hat jetzt die Eigenschaft, dass es manchmal nicht
hält, nämlich in der Endlosschleife läuft und manchmal hält.
Und jetzt ist die Frage, was passiert mit meinem Programm, wenn ich
ihm mein Programm gebe, zum Testen.
Ja, dann wird mein Programm in Ihr Programm, in das Halteprogramm,
reinlaufen, und sagen wir mal, das Halteprogramm sagt, oh nee, mein
Programm wird unendlich lange laufen.
Dann hieß es also, ich bin hier oben, dann hieß es aber, dass Ihr
Programm am Anfang gesagt hätte, mein Programm läuft nicht unendlich
lange.
Und dann haben wir wieder den Widerspruch und entsprechend auch
andersherum.
Also das Halteproblem formal ist wie folgt definiert.
Wir geben eine Turing-Maschine, W, codiert, wieder mit Gödel
-Codierung, also TW, Gödel-Codierung, W, und eine Eingabe V, und wir
schreiben dieses Wort hier hin, so wie die Eingabe für eine
universelle Turing-Maschine, und wir sagen, okay, das sind diese
Codierungen, diese Inputs für die universelle Turing-Maschine, wo es
nicht unendlich lange laufen wird, wo es hält.
Entweder in akzeptierend oder in diesem zweiten Fall.
Das ist das Halteproblem als Sprache.
Und dann ist der Satz, diese Sprache ist nicht entscheidbar.
Also ich kann nicht vorher entscheiden, bevor ich es meiner
universellen Turing-Maschine gebe, ob das denn jetzt unendlich, diese
Simulation, die sie dann ausführen wird, ob die unendlich lange
brauchen wird oder nicht.
Ich kann das nicht vorher irgendwie abtesten mit einem anderen
Programm.
Das ist unentscheidbar.
Formal beweisen tun wir das wie folgt.
Wir führen es wieder zurück auf die Unentscheidbarkeit des
Komplementes der Diagonalsprache.
Wir wissen schon, die Diagonalsprache ist nicht entscheidbar, und wir
wollen jetzt zeigen, unser Halteproblem ist nicht entscheidbar.
Und die Strategie ist Kontraposition.
Nämlich wäre unser Halteproblem entscheidbar, gäbe es ein Programm für
das Halteproblem, dann gäbe es auch ein Programm für die
Diagonalsprache.
Wir konstruieren also aus einer fiktiven Turing-Maschine für das
Halteproblem, die ändern wir und erhalten eine Turing-Maschine für die
Diagonalsprache.
Und wir haben ja schon gezeigt, die kann gar nicht existieren, also
konnte vorher das nicht existieren.
Okay, das ist so die Strategie.
Führen wir das ganz schnell aus.
Angenommen, es existierte diese Turing-Maschine, die das Halteproblem
löst.
Sie behaupten, Sie haben ein kleines Zeichen Code geschrieben und das
kann das Halteproblem lösen.
Dann konstruiere ich daraus eine andere Turing-Maschine, indem ich
ihre Turing-Maschine als Unterprogramm verwende und behaupte, diese
Turing -Maschine würde jetzt das Komplement zur Diagonalsprache
entscheiden.
Wie mache ich das?
Also das Erste, was ich tue, ist, ich muss jetzt die Diagonalsprache
entscheiden.
Also mein Programm kriegt als Input ein Wort und soll entscheiden, ob
dieses Wort W im Komplement der Diagonalsprache ist.
Ich berechne erstmal den Index des Wortes in dieser lexikografischen
Aufreihung aller Wörter.
I.
Das kann ich machen.
Das kriegt eine Turing-Maschine hin, diesen Index zu berechnen.
Müssen Sie sich einmal klar machen.
Dann gucke ich mir an, die Turing-Maschine, die diesem Wort jetzt
zugehört, gesehen als Gülde-Kodierung.
Kann ich auch machen.
Jetzt wende ich Ihr Programm an, auf diese Turing-Maschine, mit diesem
Wort.
Von dem Sie behaupten, dass das entscheidet, das Halteproblem.
Jetzt sind wir hier, da sind wir.
Also wenn jetzt dieses, wenn dieses nicht akzeptiert wird von Ihrem
Programm, von Ihrem Halteproblem-Programm, wenn dort diese Eingabe
nicht akzeptiert wird, dann heißt es also, Ihr Halteprogramm ist ja
anscheinend korrekt, das Halteprogramm behauptet dieses, es wird nicht
halten.
Ihre Turing-Maschine behauptet, MI hält nicht auf Eingabe WI.
Dann heißt es also nach Definition des Halteproblems, dass dieses
Wort, nach Definition von der Diagonalsprache, MI akzeptiert
insbesondere WI nicht.
Es hält nicht darauf, also kann es auch gar nicht akzeptieren.
Also ist dieses Wort in der Diagonalsprache und damit ist das Wort
nicht im Komplement der Diagonalsprache.
Ich habe Ihre Maschine befragt und Ihre Maschine hat Nein gesagt und
ich kann daraus mir ableiten, dass dann das Wort nicht in der
Diagonalsprache ist, das heißt, ich beantworte auch Nein auf die Frage
Komplement der Diagonalsprache, auf die Frage, ist das im Komplement
der Diagonalsprache.
Ich gebe einfach die Antwort Ihres Programmes weiter.
Ihr Programm sagt Nein, das wird unendlich laufen, dann sage ich Nein,
ist nicht in der Diagonalsprache.
Nicht im Komplement der Diagonalsprache.
Wenn Ihr Programm jetzt sagt Ja, das Ding wird unendlich lange laufen,
dann heißt es also, dass...
Nee, das wird halten.
Ihr Programm sagt Ja, es wird halten.
Dann heißt es also, die Maschine MI hält wirklich auf diese Eingabe.
Dann kann ich aber die universelle Turing-Maschine nehmen, die auch
noch Teil meines Programms ist und einfach MI auf WI simulieren und
gucken, was denn jetzt MI auf WI macht.
Ich weiß, dass es hält, aber es könnte noch eventuell Möglichkeit 1
sein, es akzeptiert oder Möglichkeit 2, es hält und akzeptiert nicht.
Und je nachdem, was das dann sagt, gebe ich das weiter.
Und wenn es jetzt sagt, es hält und akzeptiert, dann sage ich, okay,
das Ding ist im Komplement der Diagonalsprache, was dann auch stimmt.
Und wenn es sagt, es hält und akzeptiert nicht, dann sage ich, das
Ding ist nicht im Komplement der Diagonalsprache, was dann auch
stimmt.
Okay, und das beendet den Satz für die Unanschaltbarkeit des
Halteproblems und nächste Woche machen wir dann weiter.
Nee, am Donnerstag machen wir weiter.