Nach etwas häufigerem Start, willkommen zur Übung Theoretisch
-Grundlagen der Informatik.
Genau, das ist der dritte Übungstermin und heute werden wir über
Turing -Maschinen und über Berechenbarkeit reden.
Sie haben jetzt Turing-Maschinen in der Vorlesung kennengelernt und
vor allen Dingen sich darum gekümmert, was für Probleme berechenbar
oder entscheidbar sind, semientscheidbar, nichtentscheidbar und so
weiter.
Und heute bei den Turing-Maschinen reden wir über ein paar
Erweiterungen, die schon in der Vorlesung erwähnt wurden, sozusagen
Versuche oder naheliegende Versuche, etwas zu konstruieren, ein
Berechnungsmodell, was mächtiger ist als eine Turing-Maschine, indem
man erlaubt, mehrere Bänder oder mehrere Spuren oder sowas zu
verwenden.
Und wir werden das kurz diskutieren.
Für Sie sollte im Moment schon die Information da sein, dass wir nicht
wissen, ob es überhaupt irgendwo etwas gibt, was stärker ist als eine
Turing -Maschine, mächtiger als eine Turing-Maschine.
Also alle Erweiterungen, die wir uns heute angucken, sind nur genauso
mächtig wie die ganz normale Einkopf-Einband-Turing-Maschine.
Okay, springen wir da rein.
Ich mach mal die Maus hier weg.
Turing-Maschinen bestehen aus Tupeln von allerhand von Sachen.
Und die meisten Sachen kennen Sie bereits aus deterministischen
endlichen Automaten.
Zum Beispiel gibt es eine Zustandsmenge, Fu, die ist endlich.
Es gibt ein Eingabealphabet Sigma, das ist endlich.
Jetzt neu dazu kommt ein Blank-Symbol, was nicht im Eingabealphabet
ist.
Und dass das Bandalphabet größer sein könnte als das Eingabealphabet
mit Sigma zusammen.
Also wir erlauben der Turing-Maschine zusätzliche Symbole zu
reservieren, die garantiert nicht eingegeben werden können.
Dann gibt es den ausgezeichneten Start-Zustand S aus Q und eine
Übergangsfunktion.
Und die Übergangsfunktion, endliche Kontrolle, da war ich gerade.
Also die endliche Kontrolle, die befindet sich immer in einem von
diesen Zuständen.
Und die hat einen Lesekopf auf dem Eingabe- und Rechenband und da wird
immer ein Symbol gelesen.
Und jetzt sagt die Übergangsfunktion in Abhängigkeit davon, in welchem
Zustand die endliche Kontrolle sich befindet und welches Symbol
gelesen wird, von dem Eingabekopf gehe über in einen neuen Zustand aus
Q, ersetze das Symbol, was gelesen wurde, durch ein anderes,
vielleicht das gleiche Symbol aus Gamma und bewege den Kopf nach
links, rechts oder gar nicht.
Das ist die Übergangsfunktion und dann hat man eine Menge von
Endzuständen F, Teilmenge Q.
Sobald ein Endzustand erreicht wird, stoppt die Turing-Maschine und
akzeptiert das Wort.
Akzeptiert die Eingabe.
Die Turing-Maschine stoppt noch in einem anderen Fall, nämlich wenn
jemals dieses N benutzt wird.
Es ist relativ leicht einzusehen, dass es nicht viel Sinn macht,
dieses N zu benutzen, weil wir dann genau wissen, was auf dem Band
steht, wenn wir das N benutzt haben an der Stelle.
Das heißt, man kann gleich diesen Endschritt überspringen, es sei
denn, der Endschritt ändert das Band nicht.
Und in dem Fall, wenn der Endschritt da ist und das Band nicht ändert,
dann stoppt die Turing-Maschine auch und akzeptiert nicht.
In unserem kleinen Beispiel hier haben wir jetzt also diese ganz
konkrete Instanz von diesen sechs Zuständen, Q0 bis Q5.
Endliche Zustandsmenge.
Unser Eingabealphabet besteht aus 0, 1 und Hash.
Und unser Bandalphabet soll 0, 1, Hash mit dem Blank und mit so etwas
wie 0 quer, 1 quer.
Das sind zwei zusätzliche Symbole, die ich der Turing-Maschine zur
Verbindung stelle.
Mein Startzustand heißt jetzt Q0, also sozusagen das S aus der
Allgemeinbeschreibung.
Und die Übergangsfunktion wird durch diese Pfeile hier symbolisiert.
Wobei ein Pfeil einen Übergang symbolisiert.
Zum Beispiel picken wir uns mal den hier raus.
Das heißt, wenn meine endliche Kontrolle in Zustand Q1 ist und auf dem
Band 1 gelesen wird, dann wird dieser 1 ersetzt durch einen Blank.
Und der Schreibkopf bewegt sich nach links und man geht in den Zustand
Q2.
Jeder einzelne Pfeil oder jeder einzelne Label mit Pfeil gehört zu
einem Sum-Übergang, was dort passieren soll.
Und Endzustände kennzeichnen wir wieder, so wie bei endlichen
Automaten auch mit diesen Doppelkreisen.
Also in dem Fall ist Q5 der einzige Endzustand.
So, und dann können wir ja einfach mal gucken, was passiert, was diese
Turing -Maschine tut.
Wir gehen jetzt einfach mal durch, und zwar, ich schreibe auf das
Band, ich hoffe, Sie können es sehen, 111-111.
Und die Turing-Maschine fängt immer an in dem Startzustand und an der
linkesten Position auf dem Band, die nicht ein Blank ist.
Also bei dieser ersten 1.
Wir sind im Zustand Q0 und lesen direkt diese 1.
Der Kopf ist immer dort.
Gut, und jetzt gucken wir, was passiert denn, was sagt denn die Turing
-Maschine, was dort getan werden soll.
Also wir müssen an Q0 gucken, wo ist der ausgehende Pfeil, der hier
vorne eine 1 hat, und das ist der.
Und er sagt uns, lasse die 1 und gehe nach rechts.
Okay, dann sind wir in dieser Konfiguration.
Wir sind mit dem Schreibkopf 1 nach rechts gegangen, wir sind immer
noch im Zustand Q0 und der Leseschreibkopf liest im Moment diese
zweite 1.
Das heißt, er tut genau das gleiche, er geht wieder nach rechts, liest
wieder nach 1, geht wieder nach rechts.
Und so weiter.
Und jetzt, weil wir hier sehen, dass egal was er liest, solange es
kein Blank ist, geht er einfach nur nach rechts und lässt das Wort
unverändert.
Geht es sozusagen ein paar Schritte runter, bis wir ganz am Ende sind
und das erste Mal dieses Blank lesen.
Jetzt passiert was.
Nämlich, wir lesen von Q0 aus das Blank.
Wir lassen das Blank und gehen 1 nach links.
Okay, jetzt sind wir aber im Zustand Q1.
Und im Zustand Q1, wenn wir eine 1 lesen, dann löschen wir die 1 und
gehen 1 nach links.
Und gehen über in den Zustand Q2.
Das heißt, das sieht dann so aus.
Hier, diese 1 wurde gelöscht.
Die verschmilzt sozusagen mit der unendlichen Reihe von Blanks hier
hinten, die wir einfach nur noch durch einen Blank kennzeichnen.
Wir sind in 1 nach links gegangen, das heißt, diese 1, an der wir
jetzt stehen, ist die 1, die vorher dort war.
Und wir sind im Zustand Q2.
Im Zustand Q2 gehen wir immer nach links, wenn wir 0 oder 1 lesen.
Das heißt, wir lesen 1, wir gehen nach links, wir lesen 1, wir gehen
nach links.
Jetzt lesen wir aber ein Hash.
Und wenn wir ein Hash lesen, gehen wir auch nach links, gehen aber
über in den Zustand Q3.
Im Zustand Q3, wenn wir jetzt eine 1 lesen, dann benutzen wir unser
Zusatzsymbol 0 quer.
Schreiben das statt dieser 1 dorthin und gehen einen Schritt nach
links.
Das heißt, das sieht dann so aus.
Und gehen über in den Zustand Q4.
Dann haben wir diese 1 ersetzt durch eine 0 und sind 1 nach links
gegangen.
Und in Q4.
Jetzt folgen wir weiter.
Q4 liest eine 1, ersetzt sie durch eine 0 und geht auch nach links.
Und das passiert jetzt zweimal mit der 1 und mit der nächsten 1.
Dann sieht es so aus.
Dann haben wir die 1 hier durch 0 ersetzt und wir lesen jetzt blank.
Wir sind immer noch in Q4.
Wenn wir jetzt in Q4 blank lesen, dann ist es dieser lange Pfeil.
Wir ersetzen blank durch eine 1 und gehen nach rechts.
Und in den Zustand Q1, äh Q0, in unseren Startzustand.
Und jetzt geht das Spiel von vorne los, außer dass sich jetzt
natürlich ein bisschen was ändert.
Wir haben ja nicht mehr das gleiche bei uns auf dem Band.
Wir haben da einiges geändert.
Wir haben auch dieses 0 quer benutzt und so weiter, was spezielle
Sachen auslöst.
Also wenn wir das einfach durchgehen.
Wir wissen, Q0 geht einfach nur die ganze Zeit unverändert.
Das Band lässt das Band unverändert.
Geht nach rechts, bis es auf ein blank trifft.
Das heißt am Ende so.
Und dann wissen wir, wir gehen dann 1 nach links.
Wir ersetzen die 1 durch ein blank.
Wir gehen weiter nach links, bis wir das hash finden.
Wenn wir das hash finden, wird es vielleicht nochmal interessant.
Also wir haben das hash gefunden, gehen nach links.
Wir lassen diese neuen Symbole stehen.
Wenn wir auf eine 0 treffen, ersetzen wir es durch eine 1 quer und
gehen nach rechts.
Wenn wir auf eine 1 treffen, ersetzen wir es durch eine 0 quer und
gehen nach links.
Diesmal treffen wir auf 0.
0 quer, einfach nach links gehen, auf 0 treffen.
Das wird also eine 1 quer und wir gehen nach rechts.
Und in Zustand Q0 über.
Sieht dann so aus.
Und jetzt kann man sich das alles durch exerzieren.
Am Ende landen wir in dem Endzustand.
Kurz vorher sieht es so aus.
Wir haben dann auf dem Band zu stehen 1, 1 quer, 1 quer, 0 quer, hash.
Und wir lesen aus Zustand Q1, der hier die falsche Farbe bekommen hat,
lesen wir das hash und gehen über in den Endzustand.
Akzeptieren den Endzustand.
Und wir löschen noch das hash.
Das heißt, das hier ist dann die Endkonfiguration.
Und dieser String, 1, 1 quer, 1 quer, 0 quer, ist der Output, die
Ausgabe der Turing-Maschine zu der Eingabe 1, 1, 1, hash, 1, 1, 1.
Jetzt ist natürlich die Frage, was tut das Ding?
Aber bevor wir uns das fragen, wollen wir uns noch mal kurz fragen, ob
das denn überhaupt eine vollständig beschriebene Turing-Maschine ist.
Also kommt es mit jedem Input klar oder nicht?
Und damit klarkommen heißt einfach nur, ich muss darauf gefasst sein,
dass meine endliche Kontrolle in einem Zustand sich befindet, ich ein
bestimmtes Symbol lese und ich dann wissen muss, wie es weitergeht.
Das heißt, ich muss aus jedem Zustand, außer aus den Endzuständen,
ausgehende Pfeile haben mit jedem Symbol vorne.
Und vielleicht für Sie kurz zum Warmmachen, einfach kurz überprüfen,
ob es irgendwo Zustände gibt, die nicht wissen, wie sie mit einem
Symbol umgehen sollen.
Und einfach reinrufen, wenn Sie sowas entdecken sollten.
Also Q0 sieht gut aus.
Aus Q0 weiß ich, was ich tun soll, wenn ich 0, 1, Hash, 0, 1 oder
Blank lese.
Bei allen weiß ich Bescheid.
Bei Q1 weiß ich, was ich tun soll, wenn ich eine 1 lese, wenn ich eine
0 lese, wenn ich ein Hash lese.
Aber ich weiß gar nicht, was ich machen soll, wenn ich mal in Q1 bin
und 0 quer lese.
Oder in 1 quer lese.
Das heißt, der Vollständigkeit halber sollten wir dort Übergänge
zeichnen.
Wie wir es aber auch schon bei endlichen Automaten gemacht haben, sind
solche Sachen sollen dann in nicht akzeptierende Endzustände
sozusagen.
Also das sollte irgendwie so sein.
Dann machen wir einen neuen Zustand F.
Der sammelt all diese fehlenden Übergänge auf.
Alles führt nach F.
Und wenn ich in F bin, dann habe ich diese Endschleife, wo ich nichts
tue und das Band unverändert lasse.
Also die Turing-Maschine lehnt die Eingabe ab.
Wir werden wieder, so wie auch bei den endlichen Automaten ziemlich
häufig, diesen Zustand F dann nicht hinzeichnen, weil das doch das
Bild komplizierter macht.
Also wenn immer so ein Übergang fehlt, dann müssen Sie sich denken,
wenn ich versuche, einen Übergang zu benutzen, der nicht da ist, dann
heißt das, die Turing-Maschine lehnt ab.
Gut.
Jetzt ist die Frage.
Was berechnet denn diese Turing-Maschine?
Also warum ist bei 1.1.1 Hash 1.1.1 als Output rausgekommen, wenn ich
mich richtig erinnere.
Gucken wir nochmal nach.
1.1.1.0 Vergessen wir mal diese Queersachen.
Ja,
nicht schlecht.
Sehr gut.
Ist richtig.
Es ist nicht ganz so einfach zu sehen, oder?
Doch.
Also kann ich mit der Turing-Maschine beliebige Zahlen addieren?
Beliebige Binärzahlen addieren, indem ich erste Binärzahl schreibe,
zweite Binärzahl.
Leider nein.
Die Turing-Maschine kommt sehr gut mit so Binärzahlen klar, die nur
aus 1.1.1 bestehen.
Und addiert die auch richtig, wenn wir am Ende diese Queersachen
vergessen auf dem Ausgabewand.
Allerdings, wenn ich was eingebe, was eine 0 hat, dann läuft das
ziemlich schnell in diesen macht das Quatsch.
Ich müsste was ändern, insbesondere das hier zum Beispiel.
Am Anfang gehen wir ja ganz nach rechts, bis wir das Blank sehen.
Wir gehen also ans Ende der Eingabe.
Dann gehen wir einen Schritt nach links.
Wir sind jetzt hier in Q1 und auf dem letzten Zeichen.
Und wenn das letzte Zeichen eine 0 ist, dann löscht er die einfach.
Und verändert die Eingabe.
Und tut nichts.
Und dann sind wir wieder hier.
Diese 0 haben wir für immer verloren.
Und die wird nie wieder kommen.
Und damit natürlich das Ergebnis verfälschen.
Für Sie die erste Aufgabe.
Wir wollen die jetzt ändern, dass sie tatsächlich das Richtige tut.
Sie soll eine Turing-Maschine sein.
Sie soll zwei Binärzahlen addieren.
Also wenn zum Beispiel das auf dem Eingabewand steht.
100-110.
Dann soll das ausgeben als binär.
Meinetwegen mit Strichen oben drüber.
Das Ergebnis der binären Addition.
Eine Sache, die definitiv wichtig ist.
Wir sollten hier mit der 0 etwas Schlaueres machen.
Es steht jetzt, dass Sie drei Minuten Zeit haben.
Ich gebe Ihnen jetzt einfach mal drei Minuten Zeit.
Und dann reden wir darüber.
Okay, ich merke, Sie sind...
ähnlich begeistert von der Aufgabe.
Wie ich.
Vielleicht brechen wir das doch ab.
Aber ich möchte Ihnen ans Herz legen.
Um sich solche Gedanken mindestens einmal in dieser Vorlesung zu
machen.
Wenn Sie ein ganz konkretes angewandtes Problem haben.
Sie sollen eine Turing-Maschine konstruieren, die zwei Binärzahlen
addieren kann.
Das einmal so zusammen hochstellen, dass es funktioniert.
Im Prinzip steht hier schon das Rezept, was zu tun ist.
Die Lösung wäre, dass man mit der 0 eine ähnliche Schleife durchläuft,
wie man hier mit der 1 durchläuft.
Die Folien sind ja dann online.
Sie können sich dann die gerne angucken und sich davon überzeugen,
dass es das Richtige tut.
Viel interessanter, finde ich, ist doch über Erweiterung von Turing
-Maschinen zu reden.
Insbesondere, weil wir damit auch diese Aufgabe von gerade eben sehr
viel schöner lösen können.
Zum Beispiel eine mögliche Erweiterung wäre zu sagen, ich mache meine
Turing -Maschine vermeintlich mächtiger, indem ich sage, dieses Band,
dass da immer nur ein Symbol steht an jeder Zelle, ist irgendwie ein
bisschen doof.
Ich kann ja erlauben, dass auf dem Band mehrere Symbole an einer
Stelle stehen.
Das wäre dann eine mehrspurige Turing-Maschine.
Hier in dem Bild wäre es so zu sagen, ich habe drei Symbole auf dem
Band.
Ich kann ja dann spezifizieren, wie genau ich die Eingabe erhalten
möchte, ob die Eingabe auf die erste Spur nur geschrieben werden soll.
Aber so zum Rechnen ist es ganz gut, die mehrere Spuren zu benutzen.
So könnte ich zum Beispiel
Binärzahlen relativ simpel addieren.
Ich könnte mir am Anfang entweder spezifiziere, dass ich die beiden
Binärzahlen übereinander in ordentlicher Form haben möchte auf Spur 1
und Spur 2.
Oder ich spezifiziere, dass sie in Spur 1 ist und dann ist es nicht
schwierig, eine Turing-Maschine zu bauen, die die erst mal so
umstellt, dass es so aussieht.
Wenn ich erst mal hier bin, dann kann ich mir vorstellen, auf der
ersten Spur ist meine erste Binärzahl, auf der zweiten Spur ist meine
zweite Binärzahl.
Die haben die letzte Stelle auf der gleichen Zelle.
Und die dritte Spur ist für das Ergebnis.
Ich glaube, der steht hier auch.
Also die erste Spur für den ersten Summanden, zweite Spur für den
zweiten Summanden und dann die dritte Spur für das Ergebnis.
Und dann ist es recht einfach, wenn die endliche Kontrolle jetzt von
links nach rechts nach einer Methode aus der Schule durchgeht und
einfach sagt, okay, 1 plus 1 wird 0, merke 1, gehe einen Schritt nach
links.
Dann habe ich 1 plus 0 plus die 1, die ich mir gemerkt habe, wird
wieder 0 usw.
Dieses Merken würde ich dann regeln über die Zustände in der endlichen
Kontrolle.
Ein Zustand für, ich habe im Moment 0 mir gemerkt oder 1 mir gemerkt.
Und so kann ich das ziemlich einfach durchgehen von links nach rechts
die Binärzahlen addieren.
Klingt super, klingt sehr viel mächtiger als nur mit diesem einen Band
zu hantieren und dann die ganze Zeit von links nach rechts was zu
überschreiben ist tatsächlich aber kein mächtigeres Rechnungsmodell.
Ich kann, wenn ich so eine Turingmaschine mir ausgedacht habe, die auf
mehreren Spuren läuft, kann ich daraus relativ einfach eine
Turingmaschine mit nur einer Spur, die äquivalent ist, bauen.
Und zwar einfach durch das Ansehen unseres Bandalphabets als die K
-Tupel unseres früheren Bandalphabets.
Also ich schreibe mir auf das Band, statt 1 1 0, schreibe ich mir als
ein neues Symbol 1 1 0, als ein Symbol.
Dann schreibe ich mir daneben was ich nicht, zum Beispiel 1 0 blank
als ein Symbol 1 0 blank.
Das ist einfach nur das 3-Tupel von diesen drei Sachen.
Und dann kann ich auf diesen Symbolen und auf diesen Tupeln genauso
rechnen wie vorher.
Das beantwortet also diese Frage.
Diese mehrspurigen Turingmaschinen, die also wo das Band einfach
dicker ist, aber trotzdem nur einlese Schreibkopf haben, die sind
nicht mächtiger als die normalen Turingmaschinen.
Die können ziemlich leicht emuliert werden.
Die nächste Idee wäre vielleicht zu sagen, ja ok, wenn ich schon
mehrere Spuren habe, dann kann ich auch mehrere Köpfe benutzen.
Ich glaube, die Idee wurde auch schon in der Vorlesung erwähnt.
Ich könnte also im Prinzip die Bänder trennen und die Köpfe
unterschiedlich da lang gehen lassen auf den Bändern.
Die werden dann von der endlichen Kontrolle dann muss man sich erst
mal überlegen, wie man das genau jetzt umsetzen möchte, ob man jetzt
sagen möchte
wir haben ja nur eine Kontrolle, die in einem Zustand ist und dann
müssen sich diese drei Lese-Schreibköpfe sozusagen einigen wie sie
damit umzugehen haben.
Wir müssen also gucken wir haben aus einem Zustand und K gelesenen
Symbolen nämlich von jedem Band ein Symbol gehen wir in einen neuen
Zustand über, schreiben wieder die K-Symbole neu um und sagen für
jeden von den K-Lese-Schreibköpfen ob sie nach rechts, nach links oder
nicht sich bewegen.
Hier macht es übrigens schon sehr viel mehr Sinn dieses Nicht-Bewegen
zu erlauben, weil vielleicht einige von den Lese-Schreibköpfen stehen
bleiben sollen und andere sich nur bewegen sollen und so weiter.
Ja, also so würde man es vielleicht realisieren, aber auch dort ist
wieder die Frage, ist denn diese Turing-Maschine wirklich mächtiger
als eine Turing-Maschine die nur ein Band und einen Kopf hat?
Und die Antwort ist wieder nein.
Aber wir können es wieder emulieren und jetzt gibt es hier einen Satz,
der sagt, dass dieses Emulieren auch halbwegs passabel funktioniert in
Terms of Zeit und Platz.
Also sagen wir mal, wir haben jetzt eine K-Band-Turing-Maschine mit K
-Köpfen, K-Bändern und die hat eine Rechenzeit von N, wie lange sie so
höchstens braucht für Eingaben der Größe N und Platz S von N.
Ich glaube, der Platz wurde streng genommen noch nicht definiert in
der Vorlesung, ist aber wahrscheinlich selbsterklärend.
Wir haben das Band, das ist zwar unendlich, aber wir wollen sozusagen
wissen, wie viele Nicht-Blank-Symbole sind jemals auf den Bändern zu
einem festen Zeitpunkt.
Dann kann ich das emulieren durch eine Turing-Maschine einem Strich,
die eine echte Turing-Maschine ist mit einem Band, mit einem
Leseschreibkopf und die Zeit quadriert sich höchstens
Größenordnungsmäßig und der Platz bleibt linear.
Vielleicht eine kurze Zwischenfrage, wahrscheinlich ist die Antwort
ja, aber Sie können mit diesen Landau-Symbolen umgehen?
Wissen Sie, was das heißt?
O von D Quadrat, O von S Quadrat.
Gut, das ist jetzt im Prinzip, jetzt müssen wir das einmal konkret
machen, wie wir das dann emulieren würden und müssen gucken, was wir
dann für Platz und Speicher brauchen.
Das ist doch jetzt vielleicht ein bisschen interessanter.
Also ich möchte Ihnen jetzt wirklich drei Minuten Zeit geben und
danach vielleicht von irgendjemandem eine Wortmeldung haben, wie man
das dann ganz grob abschätzen kann, den Platz und den Speicher.
Warum ist es denn quadratisch in der Zeit und linear im Platz?
K ist die Anzahl der Bänder aus der gegebenen Turing-Maschine ist eine
Konstante.
Also K ist vielleicht 10.
Das ist natürlich wichtig.
Gut, drei Minuten Zeit.
Fertig?
Also, wer kann mir denn eine grobe Idee geben, warum denn wie es
gemacht wird und warum das nur linear viel Speicherplatz braucht?
Ja, sehr gut.
Okay, also ich wiederhole das einfach, weil es genau das Richtige war.
Also hier ist es jetzt noch ein bisschen im Prinzip ist es das
Gleiche, aber hier ist es ein bisschen anders umgesetzt.
Also ich gehe zurück auf die Spuren-Sache, die Turing-Maschine mit den
vielen Spuren von vorher.
Ich mache aus K-Bändern zwei K-Spuren auf einem Band und dann mache
ich dieses, hier habe ich so ein kleines Hash benutzt das ist einfach
für jede zweite Spur, da merkt es sich wo die Köpfe stehen.
Okay, gerade wurde vorgeschlagen, dass man statt sich einfach auf
einer separaten Spur zu merken, dass da ein Kopf steht, könnte man
dieses Symbol ändern in einen Einsstrich für hier ist eine Eins und da
steht gerade ein Kopf.
Oder dann hier entsprechend auch Einsstrich, hier ist eine Eins und da
steht gerade ein Kopf.
Da muss man sich ein bisschen überlegen, dass man da die Köpfe auch
noch untereinander unterscheiden kann.
Aber im Prinzip ist es das Gleiche.
Hier ist es noch ein bisschen sauberer getrennt, weil ich wirklich die
einzelnen Bänder noch identifizieren kann.
Er hatte gerade vorgeschlagen, dass man sozusagen die einzelnen Bänder
so ineinander verzahnt auf ein Band schreibt.
Also immer jede Karte-Position ist Band 1, jede Karte-Position ist
Band 2 jede Karte-Position ist Band 3.
Das funktioniert natürlich auch.
Und dann, wenn ich jetzt wissen will wie ich einen Schritt ausführe,
muss ich halt erstmal komplett einmal rüberlaufen und mir angucken, wo
sind meine Köpfe gerade.
Okay.
Habe ich hier noch was?
Ja.
Also
wird wie folgt simuliert.
Also der Kopf läuft nach rechts bis zum rechtesten unser richtiger
Kopf steht immer auf dem linkesten Hash.
Wir wissen genau wie viele Hashes es gibt.
Wir laufen durch bis zum rechtesten Hash.
Jetzt haben wir also alle Kopf-Positionen gemerkt.
Jetzt fragen wir sozusagen in Abhängigkeit davon, was unsere endliche
Kontrolle gerade für einen Zustand hat und was da steht an diesen Hash
-Stellen, was wir tun sollten.
Und dann müssen wir nochmal zurücklaufen und diese Markierungen
ändern.
Eventuell eins nach links oder eins nach rechts oder gerade gar nicht.
Und unseren Zustand entsprechend ändern und natürlich das Band
entsprechend ändern.
Okay.
Gut.
Das tut's.
Was habe ich jetzt noch?
Ja, ja.
Okay, soviel zu Turing-Maschinen.
Ich glaube, es gab noch andere Erweiterungen, die in der Vorlesung
erwähnt wurden.
Man könnte sich jetzt irgendwie wild was ausdenken.
Man könnte sagen, okay, ein Band ist im Prinzip ein eindimensionales
Ding.
Warum nicht ein zweidimensionales Ding machen, wo der eine Kopf oder
mehrere Köpfe sozusagen in X- und Y-Richtung umherwandern können.
Oder ein zehndimensionales Ding.
Man kann sich irgendwas anderes ausdenken, aber bisher alles, was sich
ausgedacht wurde, hat sich herausgestellt, dass es durch eine ganz
normale, einfache Turing-Maschine emuliert werden kann.
Also nicht mächtiger ist.
Und tatsächlich ist es diese Church-These, dass es kein
Berechnungsmodell gibt, was mächtiger ist als eine Turing-Maschine.
Kein realistisches Berechnungsmodell, was auch immer das heißt.
Und die ist im Allgemeinen anerkannt in der Informatik.
Also die Leute glauben nicht, dass es möglich sein wird, etwas
besseres zu bauen als die Turing-Maschine.
Gut.
Noch Fragen zu Turing-Maschinen und diesen Erweiterungen?
Dann gehen wir jetzt im zweiten Teil auf Entscheidbarkeit ein.
Entscheidbarkeit ist natürlich ganz eng verknüpft mit Turing
-Maschinen.
Die erste Folie ist schon die Definition der Entscheidbarkeit.
Benutzt die Definition der Turing-Maschine.
Eine Sprache ist entscheidbar, wenn es eine Turing-Maschine gibt, die
immer stoppt und genau eine Sprache ist entscheidbar, wenn es eine
Turing -Maschine gibt, die immer stoppt auf allen Eingaben und eine
Eingabe genau dann akzeptiert, wenn es aus der Sprache kommt.
Also eigentlich müssen wir wissen, wie Turing-Maschinen funktionieren,
um über Entscheidbarkeiten zu reden.
Allerdings werden wir jetzt hier wirklich von einer Größe, von einem
höheren Standpunkt aus auf Turing-Maschinen gucken und nicht mehr so
im Allgemeinen ganz speziell diese Übergänge, Pfeile setzen.
Das ist vielleicht ein bisschen abstrakt, was jetzt da mit den ganzen
Sprachen, mit den Entscheidbaren und so passiert, aber ich denke, in
einer Art ist es ein bisschen sauberer als sich diese riesigen Bilder
da anzusehen.
Also wir werden sehen.
Wir werden sehen.
Gut, also das ist die Definition von Entscheidbar.
Und hier ist der interessante Teil, vor allem dieser grüne Teil, dass
es nämlich auf allen Eingaben stoppen muss und dann natürlich noch die
Wörter aus der Sprache erkennen.
Und wir sagen dann, dass diese Turing-Maschine L entscheidet.
Ich kann der Turing-Maschine ein beliebiges Wort füttern und die
Turing -Maschine wird in endlicher Zeit mir sagen, ja, ist in der
Sprache oder nein, ist nicht in der Sprache.
Jetzt haben Turing-Maschinen allerdings auch noch die dritte
Möglichkeit, einfach unendlich lange irgendwas zu tun, ohne sich zu
entscheiden.
Und dann weiß ich nicht genau, was los ist.
Ich sage, wenn zumindest immer wenn das Wort in der Sprache ist, die
Turing -Maschine irgendwann stoppt und sagt, ja, das Wort ist in der
Sprache, dann heißt die Sprache semi-entscheidbar.
Also die Turing-Maschine erkennt die Sprache.
Es erkennt, wenn es ein Wort aus der Sprache kriegt.
Wenn es ein Wort nicht aus der Sprache kriegt, dann wissen wir nicht
genau, was passiert.
Also dann hat die Turing-Maschine zwei Möglichkeiten.
Sie kann entweder sagen, nach endlicher Zeit, nein, das Wort ist nicht
in der Sprache.
Also sie stoppt, aber nicht in einem Endzustand.
Oder sie läuft unendlich lang.
Okay.
Wir wollen nur, dass wenn es akzeptiert, dann ist das Wort in der
Sprache und jedes Wort in der Sprache wird auch irgendwann mal
akzeptiert.
Für die Worte nicht in der Sprache sagen wir nichts.
Die können dürfen nicht akzeptiert werden natürlich, aber die können
entweder abgelehnt werden oder es wird unendlich lange dauern und
keine Entscheidung Okay.
Jetzt ist klar, dass das hier eine Einschränkung ist von dem da.
Das ist ein Spezialfall.
Ich habe einfach diese grüne Zeile hier hinzugefügt in die Definition.
Das heißt, die Sprachen, die entscheidbar sind, sind spezieller als
die Sprachen, die semientscheidbar sind.
Also wenn ich jetzt versuche, hier so ein Venn-Diagramm zu malen von
dem unendlich dimensionalen Raum aller Sprachen, dann wären sozusagen
die gelbe Blase, wären die semientscheidbaren Sprachen.
Die erlauben so eine Turing-Maschine, die die Sprachen erkennt.
Und die grüne Blase soll sozusagen eine Teilmenge von der gelben Blase
sein.
Das sind die entscheidbaren Sprachen.
Die erlauben sogar eine Turing-Maschine, die die Sprache entscheidet.
Okay?
Also das ist so eine kleine Hierarchie.
Alle Sprachen semientscheidbar, entscheidbar.
Allerdings möchte ich ein bisschen noch erweitern das Bild, ein
bisschen größer machen zu diesem.
Ich möchte noch eine blaue Blase hinzufügen.
Und die blaue Blase ist das hier.
Nämlich das sind die Sprachen, deren Komplement semientscheidbar ist.
Das heißt also eine Sprache sehe ich an als Teilmenge, möglicherweise
endliche oder unendliche Teilmenge aller Wörter aus meinem Alphabet.
Und dann das Komplement sind halt genau die Wörter, die nicht in der
Sprache sind.
Und ich kann ja statt zu fragen, ich gebe dir das Wort W entscheide,
ob das in L ist, kann ich auch die Maschine fragen, ich gebe dir das
Wort W, entscheide ob es nicht in L ist.
Wäre also das gleiche wie zu fragen, ich gebe dir das Wort W, ist W im
Komplement.
Okay?
Und dann könnte es Turing-Maschinen geben, die diese Frage diese
Sprache erkennen können.
Also wenn es tatsächlich im Komplement ist, dann entscheidet die,
erkennt es auch die Turing-Maschine nach endlicher Zeit und sagt
dieses Wort ist im Komplement, es ist nicht in der Originalsprache.
Wenn es allerdings nicht im Komplement ist, könnte es unendlich lange
dauern.
Okay.
Und dann ist jetzt dieser Satz hier wichtig, dieser Satz sagt nämlich,
dass Grün genau der Schnitt von Blau und Gelb ist.
Also, Blau ist dieses Ganze und Gelb sind diese.
Also genau im Schnitt der semi-entscheidbaren Sprachen, die auch ein
semi -entscheidbares Komplement haben, das sind die Entscheidbaren.
Das macht so intuitiv Sinn.
Wenn ich Gelb bin, dann weiß ich, okay, ich kann Ja-Antworten finden.
Wenn ich Blau bin, dann kann ich Nein-Antworten finden.
Und wenn ich Grün bin, dann kann ich Ja-Antworten und Nein-Antworten
finden.
Das ist so die ganz grobe Intuition dahinter.
Und der Satz macht es halt präzise.
Also eine Sprache L ist entscheidbar genau dann, wenn L und LC semi
-entscheidbar sind.
Okay.
Gut.
Beweisen wir das?
Da sollte immer mal wieder was beweisen.
Von links nach rechts.
Das heißt, wir wissen jetzt, wir haben eine beliebige Sprache, die ist
entscheidbar.
Und wir wollen zeigen, dass sowohl L als auch das L-Komplement semi
-entscheidbar sind.
Okay.
Gut.
Gehen wir los.
Wir wissen hier, L ist entscheidbar.
Dann ist L natürlich auch semi-entscheidbar.
Wenn ich in Grün bin, bin ich auch in Gelb.
Gut.
Jetzt, wenn L entscheidbar ist, dann ist auch das Komplement von L
entscheidbar.
Das ist ziemlich einleuchtend.
Man muss die Turing-Maschine, die L entscheidet, einfach nur
dahingehend ändern, dass sie aus akzeptierenden, nicht akzeptierenden
und aus nicht akzeptierenden akzeptierenden machen.
Das ist ein bisschen subtil, weil die sich ein bisschen anders
verhalten.
Ja?
So ein akzeptierender Endzustand ist, wenn ich da das erste Mal drin
bin, ist sofort akzeptiert.
So ein nicht akzeptierender Zustand ist dieses Ding mit der
Endschleife.
Da könnte es sein, dass ich vorher schon mal durchgegangen bin.
Auch mehrmals.
Ohne zu stoppen.
Also man muss ein bisschen was machen, aber es ist echt nicht so
schwierig.
Ich glaube auch, dass es in der Vorlesung schon mal erwähnt wurde, wie
man das macht.
Also man hat eine Turing-Maschine M für L, die entscheidet L.
Und die muss man modifizieren, so dass es eine neue Turing-Maschine
wird, die das Komplement von L entscheidet.
Okay, dann weiß ich, dass das Komplement entscheidbar ist, also
insbesondere auch semi-entscheidbar.
Also aus dieser Eigenschaft kriege ich sowohl die Eigenschaft als auch
die Eigenschaft.
Das ist das, was ich wollte.
Und von links nach rechts.
Gut.
Das war die einfache Richtung.
Die andere Richtung ist aber auch nicht wirklich schwer.
Von rechts nach links.
Wir wissen jetzt, wir haben eine Sprache, die ist semi-entscheidbar
und ihr Komplement ist auch semi-entscheidbar.
Okay, was wissen wir?
Nach Definition L ist semi-entscheidbar heißt, es gibt eine Turing
-Maschine, die erkennt die Sprache.
Das heißt, sie akzeptiert bei Eingabe eines Wortes aus der Sprache.
Okay.
Wir wissen jetzt, das Komplement ist auch semi-entscheidbar.
Das heißt, es gibt eine andere Turing-Maschine, M2, die akzeptiert bei
Eingabe eines Wortes nicht aus der Sprache.
Okay, wir haben zwei Turing-Maschinen, die erkennen L und L
Komplement.
Und wir wollen eine Turing-Maschine, die entscheidet L.
Okay, und das machen wir so.
Wir können jetzt wieder diese 2-Band, also die Mehrband-Turing
-Maschine einfach nehmen.
In dem Fall wäre es eine 2-Band-Turing-Maschine.
Die Idee ist, ich schreibe W auf beide Bänder.
Wenn ich jetzt ein beliebiges Wort als Eingabe kriege, ich schreibe W
auf beide Bänder und ich führe
nicht zwei Spuren, sondern zwei Bänder.
Das sind zwei verschiedene Bänder mit jeweils verschiedenen
Kontrollen.
Ich lese Schreibköpfe mit einer Kontrolle.
Und ich führe auf Band 1 einfach M1 aus und auf Band 2 führe ich M2
auf.
Mit einer Kontrolle und je nachdem einfach nur, unabhängig davon, was
auf Band 2 passiert, macht Band 1 sein Ding und unabhängig davon, was
auf Band 1 passiert, macht Band 2 sein Ding.
Das ist eine 2-Band-Turing-Maschine, die jetzt irgendwas tut.
Jetzt muss ich noch sagen, jetzt muss ich mir erst mal überlegen, was
soll denn passieren können.
Es könnte sein, dass jetzt auf Band 1 die erste Turing-Maschine in den
Endzustand kommt und sagt, fertig.
Was soll ich denn dann machen mit der echten Turing-Maschine?
Wenn die in den Endzustand kommt und der akzeptiert, dann heißt es
also, M1 hat erkannt, dass das Wort in L ist.
Dann kann ich meiner großen Turing-Maschine sagen, akzeptiere dieses
Wort, es ist in L.
M1 könnte auch sagen, auf Band 1 es stoppt, nicht akzeptierend.
Mit so einer N-Schneife.
Ich weiß dann, dass mein Wort nicht in L ist.
Dann kann ich meiner großen Turing-Maschine sagen, stoppe mit Nein.
Oder M1 macht unendlich lange irgendwas und wir kriegen nie irgendwas
raus.
Dafür ist M2 gut.
M2 kann jetzt nicht auch unendlich lange irgendwas tun.
Schließlich ist das eingegebene Wort ja entweder aus der Sprache oder
nicht aus der Sprache.
Das heißt, eine von meinen Maschinen wird nach endlicher Zeit fertig.
Wiederum, wenn M2 sagt
akzeptiere, dann weiß ich, das Wort ist nicht in der Sprache.
Das heißt, ich halte, akzeptiere aber nicht.
Wenn M2 hält, aber nicht akzeptiert, dann kann ich auch akzeptieren.
Ja, das ist so die Hobby-Idee.
Das ist vielleicht ein bisschen eine komische Herangehensweise, aber
wenn Sie mal eine Turing-Maschine konstruieren müssen, die in der
Sprache entscheidet, es würde theoretisch reichen, zwei Turing
-Maschinen zu machen, die eine erkennt L und die andere erkennt L
-Kompliment.
Das ist auch so grob die Philosophie, die wiederkehren wird.
Wenn es einfach ist, Ja zu sagen und einfach ist, Nein zu sagen, dann
kann man das Problem lösen.
So, also dieses M entscheidet dann L.
So, jetzt haben wir das, diesen Satz uns gerade überlegt.
Aus diesem Satz können wir ganz leicht folgern, dass wenn eine Sprache
entscheidbar ist, dann ist auch ihr Kompliment entscheidbar und das
passiert genau dann selbst.
Das ist im Prinzip einfach nur, wenn die Sprache ist entscheidbar, das
heißt, sie selber ist in Gelb und ihr Kompliment ist in Blau, dann ist
aber auch ihr Kompliment in Gelb und sie selber in Blau und das ist
dann wiederum die gleiche Bedingung.
Also entscheidbare Sprachen sind abgeschlossen unter
Komplimentbildung.
Jetzt kann man sich noch andere Fragen stellen, zum Beispiel wenn ich
weiß, zwei Sprachen sind entscheidbar, ist es denn ihre Vereinigung
oder ihr Durchschnitt auch entscheidbar?
Und der Frage, wo wir jetzt nachgehen, und zwar werden wir diesen
folgenden Satz zeigen, der ist ein bisschen anders als das, was ich
gerade sagen wollte, aber daraus folgt der Rest.
Ich habe zwei Sprachen, die sind entscheidbar und jetzt möchte ich nur
eine Implikation diesmal, da möchte ich zeigen, dass auch L1 ohne L2
entscheidbar ist.
Das ist also die Sprache all der Wörter, die in L1 liegen, aber nicht
in L2.
Und der Beweis ist wieder relativ ähnlich.
Ich habe entscheidbare Sprachen, das heißt ich habe Turing-Maschinen,
die die Sprachen erkennen.
M1 und M2 entscheiden L1 bzw.
L2.
Und jetzt kann ich wieder eine 2-Band-Turing-Maschine machen, die auf
beide Bänder das Wort schreibt, auf beiden Bändern die entsprechenden
Maschinen durchführen.
Und ich muss mich nur entscheiden, wie ich damit umgehen soll, dass M1
akzeptiert oder nicht akzeptiert und M2 akzeptiert oder nicht
akzeptiert und wie das dann auf mein Akzeptanzverhalten für die große
Maschine sich auswirkt.
Und hier ist es relativ klar, ich sollte akzeptieren, genau dann, wenn
M1 akzeptiert und M2 nicht akzeptiert.
Und beides passiert nach endlicher Zeit, wenn es echte, entscheidbare
Sprachen sind.
Gut, und dann bringt die Turing-Maschine die entscheidende Sprache.
L ist diese Präferenz.
So, jetzt habe ich diesen Satz hier.
Daraus folgt als Korolla schon, dass Schnitt und Vereinigung auch
entscheidbar sind.
Ich glaube, wir haben das vor ein paar Wochen in der Übung irgendwo
erwähnt, dass man Schnitt und Vereinigung darstellen kann als
Komplementbildung von den ganzen Dingern.
Das Einzige, was man da noch reinstecken muss, ist, dass die Sprache,
die alle Wörter enthält, dass die entscheidbar ist.
Das ist klar.
Einfach die Turing-Maschine, die diese Sprache entscheidet, oder eine
Turing -Maschine, die diese Sprache entscheidet, sagt, egal, ignoriere
meine Eingabe und sag einfach akzeptieren.
Dann entschließe ich alles.
Gut.
Jetzt gibt es noch die folgenden offensichtlichen Fragen.
Wenn ich weiß, dass die wenigstens semi-entscheidbar sind, kann ich
dann folgern, dass die Differenz semi-entscheidbar ist, sozusagen das
Analogon zu diesem Satz gilt es, wenn ich entscheidbar durch semi
-entscheidbar ersetze.
Und wenn das so wäre, könnte ich daraus vielleicht wieder folgern,
dass wenn zwei Sprachen semi-entscheidbar sind, dann ist ihre
Vereinigung und ihr Komplement auch semi-entscheidbar.
Diese Fragen werde ich heute nicht beantworten.
Naja, ich werde sie beantworten.
Nämlich, das erste ist falsch und das zweite ist trotzdem richtig.
Aber ich werde nicht vormachen, wie man das einsieht, weil das auf dem
Übungsblatt liegt.
Das erste ist ziemlich leicht.
Zu sehen, dass semi-entscheidbare Sprachen nicht abgeschlossen unter
Differenzen sind.
Wiederum einfach weil zum Beispiel, wenn wir uns irgendeine Sprache
hier aus diesem gelben Bereich hernehmen, die echt in dem gelben ist,
aber nicht in dem grünen.
Und dann die andere Sprache hernehmen, die alle Wörter sind.
Die ist semi-entscheidbar, die ist sogar entscheidbar.
Dann ist die Differenz von den beiden genau das Komplement.
Aber wenn das Komplement semi-entscheidbar wäre, dann wäre das auch
noch blau und damit auch entscheidbar.
Also, dass das hier nicht gilt im Allgemeinen, ist ziemlich leicht zu
sehen.
Dass das hier trotzdem gilt, braucht jetzt sozusagen einen anderen
Ansatz.
Aber wieder ähnlich, ich muss einfach nur Turing-Maschinen finden, die
das Richtige tun.
Okay.
Jetzt haben wir ganz grob über irgendwelche entscheidbaren und semi
-entscheidbaren und vielleicht nichts davon Sprachen geredet.
Jetzt wollen wir uns nochmal die Beispiele angucken, die aus der
Vorlesung alles schon dran kamen und die ein bisschen ergänzen durch
ein, zwei andere Beispiele.
Um das ein bisschen so in den Überblick zu behalten.
Ich habe das Gefühl, dass da vielleicht ganz schön viele Definitionen
auf einmal kamen und das ist jetzt so ein Versuch, mal ein bisschen
die Draufsicht zu kriegen.
Das Erste, womit man angefangen hat, war diese Diagonalsprache.
Die Diagonalsprache braucht ganz stark diese Gödel-Nummer.
Und die Gödel-Nummer, eigentlich egal, wie die exakt funktioniert,
Hauptsache ist, dass es eine sinnvolle Abbildung ist von den Turing
-Maschinen auf die Wörter mit Alphabet 01.
In der Vorlesung haben Sie kennengelernt, wie genau das gemacht wird,
wie man da binär kodiert und alles mögliche.
Wie genau das funktioniert, ist eigentlich nicht so wichtig.
Wichtig ist, wenn ich die Maschine habe, kann ich die Gödel-Nummer
einfach berechnen, also einfach auch durch die Turing-Maschine
berechnen lassen.
Oder andersherum, wenn ich so eine kodierte Zahl kriege, dann kann ich
auch die Turing-Maschine rekonstruieren.
Das ist die Notation.
Das ist die Turing-Maschine, dann ist ihr Wort mit diesen eckigen
Klammern.
Und andersherum, wenn ich von dem Wort zurück zu der Maschine gehe,
dann ist das Wort CW die Turing-Maschine.
Das ist eine injektive Abbildung.
Das heißt, zwei verschiedene Turing-Maschinen werden auf verschiedene
Kodierungen abgebildet, aber nicht jedes Wort wird getroffen.
Nicht alles kodiert eine Turing-Maschine.
Da gibt es noch diese kleine Subtilität, dass wenn das Wort gar nicht
zu einer Turing-Maschine gehört, dann sagen wir, das ist eine Turing
-Maschine, die nichts akzeptiert.
Jetzt die Diagonalsprache.
Das sind also alle die Wörter, sodass die Turing-Maschine ihre eigene
Gödelzahl nicht akzeptiert.
Wir fragen uns, wir haben eine beliebige Turing-Maschine, daraus
kriegen wir eine Gödelnummer.
Die Turing-Maschine, das OBDA, eine, die 0,1 Wörter liest.
Die schmeißen wir da rein in sich selber und fragen, ob sie akzeptiert
oder nicht.
Und die Wörter, wo die Turing-Maschine ihre eigene Gödelzahl
akzeptiert, das sind die Wörter aus der Diagonalsprache.
Nicht akzeptiert.
Und dann haben Sie in der Vorlesung gesehen, dass diese
Diagonalsprache nicht entscheidbar ist.
Und das war die erste Sprache, von der Sie gesehen haben, dass es
nicht entscheidbare Sprachen gibt.
Auf dem Übungsblatt werden Sie sehen, da sollen Sie zeigen, dass Ihr
Kompliment von der Diagonalsprache semi-entscheidbar ist.
Das Kompliment ist ja auch nicht entscheidbar, weil Entscheidbarkeit
unter Komplementbildung abgeschlossen ist.
Das Komplement könnte jetzt semi-entscheidbar sein oder nicht.
Sie werden zeigen, dass das Komplement semi-entscheidbar ist.
Das impliziert mit dem Satz davor, dass die Diagonalsprache selber
nicht semi-entscheidbar sein kann.
Wenn die jetzt auch noch semi-entscheidbar wäre, wären Sie und Ihr
Komplement semi-entscheidbar, was heißt, dass die ganze Sprache
eigentlich einfach ist.
Das heißt, irgendwo in meinem großen Venn-Diagramm gibt es so einen
Punkt, dort in dem blauen Bereich, das ist die Diagonalsprache.
Das ist also dort.
Ja.
Gut.
Zweites Beispiel.
Das Halteproblem.
Das Halteproblem fragt gegebenen WV, ob die Turing-Maschine mit
Götezahl W bei Eingabe V hält.
Das sind alles die Wörter W, V, so das und so weiter.
Und Sie haben dann auch in der Vorlesung gezeigt, dass dieses
Halteproblem oder die Sprache dazu nicht entscheidbar ist.
Sie werden zeigen wieder auf dem Übungsblatt, dass das Komplement
dieser Sprache nicht semi-entscheidbar ist.
Okay.
Es ist relativ einfach zu sehen, dass H selber semi-entscheidbar ist.
Und zwar kann man das machen mit der universellen Turing-Maschine.
Also was ist erstmal die Aufgabe?
Wir wollen zeigen, dass H semi-entscheidbar ist.
Das heißt, wir wollen zu gegebenen Eingabe Turing-Maschine, Eingabe,
das ist die Eingabe, wollen wir wissen, ob die Turing-Maschine auf
dieser Eingabe hält.
Und wir können dann die universelle, sogenannte universelle Turing
-Maschine nehmen.
Dass die existiert, muss man sich überlegen.
Die universelle Turing-Maschine kriegt gerade als Eingaben die
Gödezahl einer Turing-Maschine und eine Eingabe.
Und was sie tut ist, sie wendet diese Eingabe auf diese Turing
-Maschine an und was immer dann passiert, gibt sie aus.
Das ist sozusagen, wenn eine Turing-Maschine ein Programm ist, dann
ist die universelle Turing-Maschine ein Computer.
Der kann jedes beliebige Programm, was ich ihm gebe, ausführen mit
jedem beliebigen Eingabe.
Okay?
So ganz grob.
Und diese universelle Turing-Maschine, die erkennt die Sprache A.
Sie entscheidet sie nicht, sie erkennt die Sprache H.
Ich möchte jetzt wissen, ob ein Wort WV in H ist.
Mein Vorgehensweise ist, ich packe dieses WV-Dings in die universelle
Turing -Maschine und jetzt ist die Sache, wenn WV in H ist, dann heißt
es, dass die Turing-Maschine TW hält bei Eingabe V.
Das heißt, die universelle Turing-Maschine, die genau das simuliert,
wird auch halten bei dieser Eingabe und kann dann einfach Ja sagen.
Also wenn sie hält, erkennt es die Turing-Maschine.
Wenn sie nicht hält, dann wird auch die universelle Turing-Maschine
unendlich lange gehen und wird es nicht ablehnen, die Eingabe, aber es
wird halt auch nicht akzeptiert.
Also so kann ich sehen, dass H semi-entscheidbar ist.
Das heißt, wenn ich all das zusammennehme, dann weiß ich, H liegt
hier, irgendwo in diesem gelben Bereich.
Dann gibt es noch die universelle Sprache, die ist wieder ganz ähnlich
wie die Sprache von dem Halteproblem.
Das soll aber diesmal sagen, all die Wörter, wo die Turing-Maschine
hält und akzeptiert.
Vorher war es nur, wo sie hält.
Und dann haben sie auch in der Vorlesung gesehen, dass das nicht
entscheidbar ist, aber dass es semi-entscheidbar ist.
Das heißt, auch diese universelle Sprache liegt da irgendwo rechts.
Dann gab es noch dieses Postchess Postchess.
Amerikaner gewesen, Post.
Postchess-Korrespondenzproblem.
Ich glaube, ich mag es lieber, mit diesem Dominostein sich das
anzugucken.
Statt einfach nur mit dieser Tupelschreibweise.
Also das Problem ist, wir haben gegeben eine Menge von Dominosteinen
und wir müssen uns vorstellen, wir haben von jedem Dominostein
unendlich viele zur Verfügung.
Wir haben einen oben und einen unten.
Ich darf die nicht drehen.
Ich muss die wirklich so oben und unten lassen.
Vielleicht hätte ich die oben weiß und unten schwarz färben sollen.
Mein Ziel ist es, aus diesem unendlichen Vorrat von Dominosteinen, von
diesen drei Sorten, so eine Kette zu bilden, die nebeneinander zu
legen, sodass, wenn ich mir jetzt angucke, was denn da drauf steht,
auf den Dominosteinen, auf beiden, oben und unten, das gleiche Wort
kommt.
Also hier zum Beispiel, da sehe ich oben 1 0 1 1 1 0 0 1 1.
Wenn Sie ein Kurzzeitgedächtnis haben, dann ist das das gleiche wie 1
0 1 1 1 0 0 1 1.
Oben und unten ist das gleiche.
Das ist eine Lösung.
Das heißt, diese Probleminstanz aus diesen drei Dominosteinen ist
lösbar.
Stellen Sie sich das als Spiel vor.
Ich bin der Bestseller.
Man zieht aus dem Säckchen diese Dominosteine und man soll jetzt
entscheiden, kann man so eine endliche Folge bilden oder nicht.
Und zu diesem Trippel ist die Antwort ja.
Es ist möglich, nämlich so.
Und zu manchen Trippeln ist es aber auch nicht möglich.
Oder zu manchen.
Es müssen auch nicht drei sein, es können auch 17 Dominosteine sein.
Und die entsprechende Sprache ist dann halt...
Wir kodieren dieses Problem mit einer bestimmten Kodierung S und dann
ist die Frage, ob diese Kodierung ein Ja-Beispiel von dem Problem ist.
Und von dieser Sprache haben Sie auch in der Vorlesung gesehen, dass
sie nicht entscheidbar ist, aber semi-entscheidbar ist.
Und semi-entscheidbar ist jetzt wirklich...
Wir sind ziemlich weit weg von Turing-Maschinen, aber eigentlich reden
wir über Turing-Maschinen.
Semi-entscheidbar ist, ich probiere einfach alles aus.
Alle Folgen aus, die Dominosteine hintereinander und gucke, ob das
eine Lösung ist.
Und wenn ich das jetzt in einer schlauen Reihenfolge mache, dann muss
ich nur noch sicherstellen, es sind ja unendlich viele Möglichkeiten,
die ich da durchprobieren muss, dass ich egal, wo die gute Lösung sich
versteckt, ich sie nach endlicher Zeit finde.
Und es hängt damit zusammen im Prinzip, dass die Menge dieser
möglichen Reihen, die ich bilden kann, abzählbar ist.
Und dann habe ich also einen Algorithmus, eine Methode, wie ich, wenn
ich eine Ja-Instanz habe, wie ich das in endlicher Zeit herausfinde.
Ich fange wirklich an, erstmal alle einzelnen Steine, dann alle Paare
von Steinen, dann alle Drittel von Steinen, alle Viertel und so
weiter.
Gut, aber wenn es eine Nein-Instanz ist, werde ich niemals den Grund
sehen, warum es nicht passiert.
So, jetzt kommt mal was Neues.
Hilbert, kennen Sie vielleicht, das ist jetzt ein Deutscher gewesen,
hat 1900 sehr berühmt die Millenniumsprobleme auf so einer Konferenz
vorgetragen.
Probleme, die die Mathematik oder die Informatik oder auch andere
Gebiete lösen sollten innerhalb von 100 Jahren.
Das war so der Milestone, den man sich so gesetzt hat.
Und da das zehnte, Hilberts zehntes Problem war das folgende.
Sind die folgenden Sprachen entscheidbar?
Die Sprache N ist die Menge aller Polynome ganzzahliger Polynome
endlichen Gerades.
Also ich bedarf nur sowas wie 6x2 y3 plus 7x2 4 minus 3 oder sowas.
Also keine irrationalen Zahlen verwenden, nur ganze Zahlen verwenden
und endlichen Gerades.
Kann ich dem Polynom ansehen, ob es eine ganzzahlige Nullstelle hat?
Also kann ich dann für x und y und z und die ganzen Variablen, die da
auftauchen, ganze Zahlen finden, sodass das ganze Ding sich auswertet
zu 0.
Diophantische Gleichung heißen die im Algebra.
Also ich möchte jetzt entscheiden, ich möchte gar nicht so richtig
wissen, eine Lösung finden, ich möchte nur wissen, gibt es eine
Lösung?
Würde mir reichen.
Die Antwort ja oder nein.
Und dann der Spezialfall N1, okay, was ist denn, wenn es nur in einer
Variable ist?
Nur ein Polynom in x.
Gibt es ein ganzzahliges x, sodass dieses Polynom zu 0 evaluiert?
So, jetzt können wir ein paar Beobachtungen machen.
Nämlich das erste ist, N und N1 sind semi-entscheidbar.
Wir können also, sagen wir mal, für N1 ist es relativ einfach, wir
gehen los und probieren einfach aus, in x alles mögliche
reinzustecken.
Wir müssen alle jede ganze Zahl einmal durchprobieren.
Dann evaluieren das Polynom an der Stelle und gucken, ob es 0 ist.
Wenn ja, wir haben eine 0-Stelle gefunden.
Jetzt ist es ein bisschen tricky, wie wir diese Zahlen, die ganzen
Zahlen durchgehen.
Wir können nicht einfach von 0 starten und dann 1 und dann 2 und dann
3 und dann 4 und so weiter probieren.
Und wenn wir fertig sind mit Minus 1, Minus 2, das geht natürlich
nicht.
Aber wir werden ja nicht fertig werden.
Das heißt, die Minus 1 wird nie überprüft werden.
Das heißt, wir müssen ein cleveres Abzählen machen.
Nämlich wir müssen machen 0, 1, Minus 1, 2, Minus 2, 3, Minus 3, 4,
Minus 4.
Und dann jede Zahl, egal welche, wird nach endlicher Zeit dran sein.
Und dann so kann ich das also finden.
Das ist also semientscheidbar.
Und wenn ich jetzt ein höherdimensionales Ding habe, dann geht das
auch.
Also die sind auch noch abzählbar.
Die Tupel von ganzen Zahlen.
Das Verfahren terminiert.
Wenn eine ganzzahlige 0-Stelle da ist, dann wird es das auch finden.
Jetzt ist die Frage, ich würde aber auch gerne einen Grund wissen,
warum es mal eine Nein-Antwort ist.
Ich will das Komplement erkennen.
Ich will erkennen, dass ich das Polynom nicht mehr weiter suchen
brauche.
Eine grobe Idee wäre, wenn ich dann weiß, mein Polynom ist ziemlich
klein, hat vielleicht 4 Terme und die ganzen Variablen, die da drin
vorkommen, die ganzen Koeffizienten sind vielleicht höchstens 100.
Wenn ich jetzt irgendwie schon Zahlen der Größe 40 Trilliarden
probiert habe, kann denn da hinten überhaupt noch was kommen?
Oder kann ich sagen, wenn es 0-Stellen gibt, dann gibt es auch eine
kleine 0-Stelle.
Ja, tatsächlich, das ist so.
Für den eindimensionalen Fall ist das so, man kann zeigen, dass es ein
kleines Intervall gibt, das ohne 0-Stelle drin sein muss, und wenn es
in dem Intervall schon keine 0-Stelle gibt, dann brauchst du auch
nicht weitersuchen.
Daraus folgt, dass es entscheidend ist.
Das wusste Hilbert natürlich schon.
Das Problem ist, wenn es mehr dimensional wird, dann wissen wir, okay,
dieses Intervall existiert nicht mehr.
Aber das heißt ja nichts.
Vielleicht gibt es ein anderes, tolles Zertifikat.
Das ist eines von den gelösten Millenniums-Problemen.
Dann hat es 70 Jahre gebraucht, bis ein Tscheche den letzten Schritt
gemacht hat.
Matthias Lewitsch hat dann letztendlich gezeigt, dass die Sprache
nicht entscheidbar ist.
Und letztendlich, wenn man so will, hat das reduziert das
Halteproblem.
Aber dazwischen sind ganz viele abgefahrene Schritte, die ich jetzt
nicht erkläre.
Zusammenfassend wäre N1 hier zu verorten, ist entscheidbar.
Und N wäre hier zu verorten, nicht entscheidbar, aber
semientscheidbar.
Jetzt noch die Frage, die sich alle so stellen.
Das Blaue habe ich mal getroffen, das Grüne und das Gelbe habe ich
getroffen.
Kann ich auch das Graue treffen?
Dann gibt es Sprachen, die nicht semientscheidbar sind, aber ihr
Kompliment auch nicht semientscheidbar ist.
Wobei es völlig schwer ist, Ja zu sagen und Nein zu sagen.
Und ja, sowas gibt es.
Ich weiß nicht, ob das mal irgendwann diskutiert werden wird, aber das
ist so das kanonische Beispiel, was man da bringt.
Das ist die Äquivalenz von Turing-Maschinen.
Also man fragt sich gegeben, zwei Goethe-Zahlen von Turing-Maschinen.
Die Frage ist, beschreiben sie die gleiche Sprache?
Das ist ein Problem, da kann ich weder für Ja das Leicht bezeugen, in
endlicher Zeit, noch für Nein kann ich das in endlicher Zeit leicht
bezeugen.
Genau, also das wäre, diese Sprache wäre da draußen.
Gut.
Ich hoffe, das gibt ein bisschen einen kleinen Überblick, wovon wir
sprechen und wie die Methoden sind.
Das Letzte, was ich noch will, ist, ich möchte Ihnen so einen kleinen
Werkzeugkasten zur Entscheidbarkeit mitgeben.
Also Sie haben jetzt irgendwie eine Vermutung, irgendeine Sprache ist
entscheidbar oder Ihr Kompliment ist vielleicht semientscheidbar und
jetzt ist die Frage, wie kann man das nachweisen?
Und einfach einmal zusammenführen, was gibt es da für Möglichkeiten?
Und eine Möglichkeit gibt es noch, die ich noch gar nicht erwähnt habe
und damit fange ich an, das ist der Satz von Reisz.
Der Satz von Reisz ist ein Mittel, um zu zeigen, dass etwas nicht
entscheidbar ist.
Den kennen Sie aus der Vorlesung, aber hier steht einfach genau so
nochmal da.
S ist eine nicht-triviale Teilmenge von berechenbaren Funktionen.
Zwei Begriffserklärungen.
Berechenbar heißt, es ist eine Funktion, die von Input nach Output
abbildet, wobei Output eventuell undefiniert ist, Input hält nicht.
Das ist eine berechenbare Funktion, die kommt von einer Turing
-Maschine.
Es ist eine Funktion, sodass es eine Turing-Maschine gibt, die genau
das tut, was die Funktion sagt.
Bei diesem Input wird dieser Output produziert, eventuell undefiniert.
S ist eine nicht-triviale Teilmenge.
Nicht-trivial heißt,
es muss mindestens eine berechenbare Funktion enthalten und es muss
mindestens eine berechenbare Funktion nicht enthalten.
Das heißt nicht-trivial.
Das soll nicht die ganze Menge sein, das soll nicht die leere Menge
sein.
Also dass da wirklich was zu entscheiden ist.
Für die leere Menge wäre das einfach und für die ganze Menge auch.
Und die Frage ist jetzt, gegeben eine Turing-Maschine, codiert durch
ihre Gödelzahl, realisiert diese eine Funktion aus S?
Und das zu entscheiden, welche Turing-Maschinen realisieren Funktionen
aus S?
Diese Frage ist nicht entscheidbar, egal wie S aussieht.
Die Beweisidee, ich hatte kurz überlegt, die hier zu bringen, mache
ich aber nicht.
Man reduziert vom Haltepunkt.
Zwei Beispiele vielleicht, um das nochmal klar zu machen.
Zum Beispiel, die folgende Sprache, alle Turing-Maschinen, die, wenn
sie Eingabe 42 kriegen, Ausgabe 17 produzieren.
Diese Menge von Turing-Maschinen definiert eine Sprache über diese
Gödel -Nummer-Abbildung und diese Sprache ist nicht entscheidbar.
Nach dem Satz von Reis.
Ich rufe den Satz von Reis auf, der beinhaltet alle Funktionen S, die
einfach an der Stelle 42 auf 17 abbilden.
Und der Rest, egal.
Das sind nicht alle berechenbaren Funktionen und das ist auch
mindestens eine berechenbare.
Dann ist es nicht entscheidbar.
Ich kann nicht testen, ob mein Programm bei Eingabe 42 17 berechnet.
Ein zweites Beispiel ist ein Negativbeispiel.
Das ist nicht anwendbar für den Satz von Reis.
Das sind alle Turing-Maschinen, die bei Eingabe 42 17 Schritte machen.
Das ist nicht beschreibbar als Realisierung einer Funktion, weil die
Funktion sagt nur, was wird worauf abgebildet.
Es sagt eventuell als undefiniert, was heißt unendlich lange.
Aber wenn es endlich lange ist, sagt es nicht, wie viele Schritte es
braucht.
Das ist etwas, das kann ich nicht da oben in dem Satz von Reis
modellieren.
Das heißt, ich kann den einfach nicht benutzen.
Für die Entscheidbarkeit der Sprache sagt es jetzt erstmal nichts,
aber es ist irgendwie eine kleine Hausaufgabe für Sie, zu sehen, was
denn da los ist.
So, das ist jetzt das letzte Werkzeug in unserem Werkzeugkasten und
hier ist die Übersicht.
Sagen wir, Sie haben eine Sprache L und Sie wollen zeigen, dass diese
entscheidbar ist, vielleicht auf einem Übungsblatt oder so.
Dann haben Sie folgende Möglichkeiten, unter anderem Konstruieren Sie
eine Turing-Maschine oder nicht-deteministische Turing-Maschine, die L
entscheidet.
Das ist einfach.
Oder Sie zeigen, das hatte ich am Anfang mal erwähnt, dass L und das
Komplement von L semi-entscheidbar sind.
Jetzt fragen Sie sich, wie zeige ich denn, dass etwas semi
-entscheidbar ist?
Wenn L semi-entscheidbar zu zeigen ist, dann müssten Sie zum Beispiel
eine Turing-Maschine oder nicht-deteministische Turing-Maschine
konstruieren, die die Sprache erkennt.
Die muss nicht immer halten, aber wenn die Eingabe aus der Sprache
ist, soll sie halten und akzeptieren.
Und wenn sie akzeptiert, dann auch nur für Elemente der Sprache.
Also können Sie diese zwei Turing-Maschinen, eine für L und eine für
C, hier hin machen, um Entscheidbarkeit zu machen.
Wenn Sie jetzt Negativresultate haben, Sie haben eine Sprache und Sie
sind davon überzeugt, dass sie nicht-entscheidbar sind, wie zeigen Sie
das?
Normal.
Eine Möglichkeit ist, den Satz von Rice zu benutzen.
Ist jetzt erfahrungsgemäß nicht so häufig möglich, aber manchmal
schon.
Eine andere Möglichkeit ist, diese Reduktion zu machen.
Also Sie nehmen sich eine Sprache N, von der Sie schon wissen, dass
sie nicht-entscheidbar ist.
Nach Vorlesung, zum Beispiel das Halteproblem.
Und dann reduzieren Sie N auf L.
Was heißt das?
Das heißt, Sie zeigen, dass Sie, wenn Sie L lösen könnten, könnten Sie
N lösen.
Das heißt, wenn Sie eine Turing-Maschine hätten, die
L entscheidet, erkennt, entscheidet.
Eine Turing-Maschine oder nicht-deterministrische Turing-Maschine, die
L entscheidet, dann könnten Sie daraus die als Building-Block nehmen
und daraus eine andere Turing-Maschine bauen, die N erkennt,
entscheidet.
Wir zeigen also, dass die ganze Problematik des Problems steckt schon
in L, wenn Sie das hier bauen.
Und der Rest, wie oft Sie da L aufrufen usw., das ist alles einfach.
Und dann wissen Sie, so etwas kann es überhaupt nicht geben, weil N
ist ja bewiesenermaßen nicht-entscheidbar, also war L am Anfang auch
nicht entscheidend.
Gut.
Letzter Punkt, wenn Sie jetzt zeigen wollen, okay, sagen wir mal, Sie
haben schon gezeigt, dass es nicht-entscheidbar ist, jetzt wollen Sie
auch noch zeigen, dass es noch nicht mal semi-entscheidbar ist.
Wie könnten Sie dann vorgehen?
Naja, Sie könnten z.B.
zeigen, dass L erstmal nicht-entscheidbar ist, und dann könnten Sie
zeigen, dass das Komplement aber semi-entscheidbar ist.
Weil wir diesen Satz haben, den einzigen Satz, den wir hier bewiesen
haben.
Also wenn das Komplement semi-entscheidbar ist, dann bin ich in der
blauen Blase.
Wenn ich jetzt auch noch semi-entscheidbar wäre, wäre ich auch in der
gelben Blase.
Das heißt, ich wäre in der grünen Blase, aber Sie haben ja gezeigt,
ich bin nicht in der grünen Blase.
Also in diesen Worten würden Sie dann, das hier würde zeigen, ich bin
in blau, aber nicht grün.
Und daraus, es zeigt, ich bin nicht in gelb.
Oder, man macht wieder so eine Reduktion auf eine nicht-semi
-entscheidbare Sprache, die Sie jetzt auch kennengelernt haben.
Und die Reduktion muss dann halt die Sprache nicht entscheiden,
sondern nur erkennen.
Gut.
So.
Das war's für heute.
Ich entschuldige mich für das etwas verzerrte Bild, aber ansonsten
wäre ich noch fünf Minuten für Fragen da.