So, schönen guten Morgen.
Ich begrüße Sie zur Vorlesung Grundlagen der Informatik II.
Wir wollen heute... Das ist noch etwas zu laut, denke ich.
Wir wollen uns weiter beschäftigen mit dem Kapitel hier
Kontextsensitive Sprachen, allgemeine Sprachen und Turing-Maschinen.
Haben wir uns letztes Mal genauer angeschaut.
Wir hatten hier eine ganze Reihe Dinge gemacht letztes Mal.
Wir hatten festgestellt, dass man zu jeder kontextsensitiven Grammatik
bzw.
zu jeder monotonen Grammatik...
Wir hatten gesehen, dass man kontextsensitive Grammatiken machen kann
mit diesen Regeln, dass ein Nicht-Terminalsymbol in einem bestimmten
Kontext ersetzt werden kann.
Wir hatten monotone Grammatiken gesehen, gesehen, dass die äquivalent
sind.
Wir haben uns das Ganze dann noch weiter angeschaut.
Ich habe Ihnen gezeigt, dass die kontextfreien Sprachen tatsächlich
alle kontextsensitiv sind, weil man auf die Lambda-Regeln ja
verzichten kann.
Und dann kam als weiteres, dass es natürlich ein echtes Enthalten sein
ist.
Das war klar wegen der Sprache A hoch N, B hoch N, C hoch N.
Wir hatten uns weitere Dinge angeschaut.
Genau, die Typ-0-Sprachen, Typ-0-Grammatiken, die also die
allgemeinsten Grammatiken sind, hatten dann überlegt, dass diese Typ-0
-Grammatiken tatsächlich mehr enthalten, bzw.
ich habe das nur erwähnt, das Genaue dazu kommt noch, und dass es auch
außerhalb dieser durch endliche Systeme beschreibbaren Sprachen noch
viele andere gibt, nämlich unendlich viele, wenn es nur abzählbar
unendlich viele Sprachen gibt, die man durch endliche Systeme
beschreiben kann.
Ich habe Ihnen dann etwas erzählt über Turing-Maschinen, also ein
einfaches Modell, das sich nur dadurch vom endlichen Automaten
unterscheidet, dass man vom Band nicht nur lesen kann, sondern dort
auch schreiben kann und es in beide Richtungen bewegen kann.
Wesentliche Erweiterungen.
Wir hatten dann gesehen, wie man die tatsächlich aufschreibt, also
über Turing-Tafeln oder Zustandstafeln, die Sie ja eigentlich von den
endlichen Automaten kennen.
Es muss eben nur ein bisschen mehr drinstehen in diesen Feldern.
Wir hatten dann Beispiele angesehen.
Das eine war diese einfache Löschmaschine.
Wir hatten dann noch ein paar weitere Beispiele betrachtet.
Ich hatte Ihnen gezeigt, wie man, das war hier erstmal verbal
formuliert, wie man die Sprache A auch N, B auch NC auch N mit einer
Turing -Maschine akzeptieren kann, indem man halt das kräftig
ausnutzt, dass man Zeichen verändern kann, dadurch sich merken kann,
dass man sie bearbeitet hat und dadurch eben das wiederholte
Auftauchen von solchen Zeichen wie A, B oder C in entsprechenden
Anzahlen überprüfen kann und dann halt auf relativ einfache Art diese
Sprache erkennen kann.
Und wir hatten dann entsprechend den Automaten dazu gebaut.
Das war hier diese Turing-Maschine mit den Einträgen, die man braucht
für diese sechs Zustände, S0 bis S5, die ausreichen, um halt immer hin
und her zu laufen von den A's zu den B's zu den C's, die ersetzt durch
0, 1, 2 und dann wieder zurückläuft, um zu sehen, ob man noch weitere
ersetzen muss.
Das waren diese Überlegungen zu der Sprache A auch N, B auch NC auch
N.
Und dann kam schließlich noch ein Satz hier dazu.
Wir hatten gesehen, dass man die Automaten, die Turing-Maschinen auch
nicht deterministisch formulieren kann, wie auch bei den anderen
Automatenmodellen.
Und dass man tatsächlich in der Lage ist, jede nicht deterministische
Turing -Maschine zu simulieren, durch eine deterministische Turing
-Maschine nur mit einem deutlich höheren Zeitaufwand.
Also anders als bei den Kellerautomaten ist es hier tatsächlich so,
dass der Nicht-Determinismus keine prinzipielle Erweiterung der
Berechnungsmöglichkeiten bringt, abgesehen von dem Zeitaufwand, den
man hat.
Wir werden darauf nochmal intensiv zurückkommen.
Und das waren dann die Überlegungen, die wir hatten, dass also
natürlich die endlichen Automaten, Kellerautomaten-Sprachen, dass das
alles eine schöne Hierarchie bildet, also die einfachste Sprachklasse,
die durch endliche Automaten erkennbar sind, die allgemeinste, die
durch Turing-Maschinen erkennbar sind.
Und das war...nein, das ist neu.
Das heißt, die nächste neue FOI, da muss ich jetzt wieder neu
einsteigen.
Was man also einfach sehen kann, ist, dass jeder endliche Automat
natürlich eine äquivalente Turing-Maschine hat, die gleiche Sprache
erkennt.
Ich brauche ja nur die Möglichkeiten, dass ich schreiben kann und dass
ich das Band nach links und rechts bewegen kann, gar nicht
auszunutzen.
Dann habe ich einen endlichen Automaten.
Das ist klar, jeden Kellerautomaten kann ich als Turing-Maschine
auffassen.
Ich benutze den Teil, wenn ich hier meine Turing-Maschine habe und
hier meinen Lesekopf und die Zustandsmenge, also unsere
Kontrolleinheit.
Und hier steht zu Anfang unser Wort W drauf.
Da kann ich einfach als Keller den Teil hier rechts von dem Wort
betrachten, kann hier immer schön Sachen reinschreiben und sukzessive
wieder weglöschen und auf diese Art und Weise das Kellerprinzip
einfach auf diesem Band selber machen.
Also ausnutzen, schreibe hier im Prinzip mein K0 rein, dann kann ich
immer feststellen, dass ich da an der Grenze bin und insofern kann ich
einen Keller auf dem einen Band simulieren.
Ich brauche dafür nicht einen extra Kellerspeicher, das kann ich alles
auf dem Schreib-Leseband machen, einer Turing-Maschine.
Also dieses zu simulieren ist einfach, das sieht man sofort ein.
Und daraus folgt dann natürlich, dass die Sprache oder die Klasse der
Sprachen, die von endlichen Automaten erkennbar sind, echte Teilmenge
ist.
Das wissen wir von den Sprachen, die durch Kellerautomaten erkennbar
sind und dass das wiederum eine echte Teilmenge ist von den Sprachen,
die durch Turing-Maschinen erkennbar sind.
Wir hatten die schönen Sprachen A0nB0n und A0nB0nC0n als Beispiele für
Sprachen, die jeweils das Echte enthalten seien, das dort jeweils
steht, das gerade begründen.
Und es ist auch so, dass man jede Grammatik, jede Typ-0-Grammatik
simulieren kann durch eine Turing-Maschine, das müssen wir uns noch
überlegen.
Also, die eine Richtung, wenn ich eine Typ-0-Grammatik habe, muss ich
dazu eine äquivalente Turing-Maschine finden, die genau diese Sprache,
die ich durch die Typ-0-Grammatik erzeugen kann, die die gerade
erkennen kann oder akzeptieren kann.
Und das überlegen wir uns jetzt wie folgt.
Wir haben also hier eine Regelmenge gegeben, Regelmenge P einer Typ-0
-Grammatik.
Das müssen wir uns überlegen, wie können wir für ein Wort, das auf dem
Eingabeband steht, überprüfen, ob dieses Wort aus dem Startsymbol
ableitbar ist, entsprechend den Regeln dieser Typ-0-Grammatik.
Und das wird ein sehr nicht deterministischer Automat.
Im Prinzip ist es ganz ähnlich wie das, was wir gemacht haben bei der
Simulation der Typ-2-Grammatiken, der kontextfreien Grammatiken durch
einen Kellerautomaten.
So ähnlich macht man das hier auch, dass man einfach auf dem Band eine
Ableitung simuliert, beziehungsweise wenn ich von dem Startsymbol aus
sukzessive hier W1, W2 usw.
bis mein Wn gleich W ableiten kann, dann kann ich das Ganze auch
rückwärts simulieren, indem ich einfach mein Wort betrachte und dann
einfach nachschaue, ob es eine rechte Seite einer Regel gibt, die in
diesem Wort auftaucht, die ich im Prinzip rückwärts verwenden könnte.
Also irgend so ein Vieh auf Psi, wenn das eine Regel ist.
Wenn ich das Psi finde in dem Wort, irgendwo als Teilwort da drin,
wenn das hier mein Psi ist, würde ich das einfach, dieses Teilwort
ersetzen durch ein Vieh.
Dann habe ich entsprechend hier ein mögliches Wort Wn-1 erzeugt.
Ich kann das auf jeden Fall, da das abgeleitet wurde durch eine solche
Regel, kann ich eine solche Rückwärtstransformation machen.
Es gibt viele Möglichkeiten, solche Rückwärtstransformationen zu
machen und eine Folge von solchen Reduktionen meines Wortes führt dann
tatsächlich zu dem Startsymbol.
Also wenn das Wort ableitbar ist aus dem Startsymbol, dann gibt es ja
jeweils Regeln.
Hier also irgendein S auf, das wäre tatsächlich ein S auf V1 und hier
wäre das dann irgendein V1 auf V2 und entsprechend das hier, die
letzte wäre im Prinzip ein V1 V2, dann wäre das ein Vn-1 auf Vn.
Vn-1 wäre V, Vn wäre Psi, das wäre also die Folge der Regeln, die ich
verwendet habe, um dieses Wort abzuleiten.
Das muss ich nur rückwärts machen, das Ganze.
Und es gibt diese Möglichkeit, das zu finden, also ich habe hier die
Menge der Regeln meiner Grammatik und ich simuliere einfach jetzt
dieses Wort von rechts nach links, rückwärts, wie ich gerade
angedeutet habe.
Und das heißt, wenn wir uns das jetzt genauer anschauen, ich habe also
meine aktuelle Bandinschrift und da steht also mein Wort W drin und
jetzt suche ich einfach hier ein Teilwort Ci und ich habe ja meine
Regeln der Grammatik, für jede dieser Regeln gibt es eine rechte
Seite.
Wenn eine solche rechte Seite auftaucht in dem Wort, das kann ich eben
sukzessive überprüfen.
Dann muss ich nur dieses Psii ersetzen durch das Phii und das heißt,
das hier wird dann einfach irgendwie ersetzt.
Das sieht jetzt hier, da habe ich jetzt zu viel weggestrichen, auch
die Ränder vom Band, das wird also jetzt zu einem Phii und
entsprechend kann ich das dann weiter, kann ich eine andere rechte
Seite suchen und die wieder ersetzen.
Und ich habe dann irgendwann hoffentlich diese Bandinschrift S dort
stehen, wo nur noch das Startsymbol steht.
Wenn das Wort ableitbar war, gibt es eine solche Rücktransformation
und dann ist das Wort akzeptiert.
Wenn das Wort nicht in der Sprache ist, werde ich dabei nicht in einen
Endzustand kommen und dann wird es halt nicht akzeptiert.
Also für jedes Wort aus der Sprache gibt es dann mindestens eine
akzeptierende Konfigurationenfolge und damit kann ich jedes Wort der
Sprache, das durch die Grammatik ableitbar gewesen wäre, auch
akzeptieren.
Das ist also eine relativ naheliegende Art, diese Ableitung zu
simulieren.
Das haben wir genauso gemacht bei den kontextfreien Sprachen, die wir
durch Kellerautomaten akzeptiert haben.
Sie erinnern sich an diese Standardkonstruktion.
So, andersrum müsste ich zu einer Turing-Maschine eine Grammatik
definieren.
Auch das kann man machen.
Genau wie bei den Kellerautomaten erspare ich mir auch hier, Ihnen das
genau zu zeigen.
Da muss ich halt jeden Übergang der Turing-Maschine durch eine
entsprechende Regel meiner Grammatik, die das simulierte Äquivalent
sein soll, dann simulieren.
Das kann man auch alles machen, will ich aber hier nicht weiter
ausführen, das dauert mir hier zu lange.
Und Sie können das nachlesen.
Man muss halt nur wissen, das ist Äquivalent.
Also Typ Null Grammatiken und Turing-Maschinen.
Was uns jetzt fehlt, ist noch die eine Sprachklasse, die ich jetzt
gerade übersprungen habe.
Wir hatten jetzt nur von Endlichen Automaten, Kellerautomaten und
Turing -Maschinen geschrieben.
Die erwähnt, was ist mit den kontextsensitiven Sprachen.
Die haben wir jetzt gar nicht erwähnt.
Und da kommen wir zu einer Spezialisierung der Turing-Maschinen,
nämlich Turing-Maschinen mit linearer Bandbeschränkung.
Lineare Bandbeschränkung heißt, ich habe mein Speicherband, also mein
Lese - und Lese-Arbeitsspeicherband, wie immer Sie das nennen wollen,
und ich schreibe irgendwo rechts auf dieses Band ein
Begrenzungssymbol, hier Dollarzeichen, kann irgendein Zeichen sein.
Ich möchte nur markieren einen bestimmten Bereich, den ich nicht
überschreiten darf, während der Bearbeitung meines Wortes.
Und diese Länge, die ich hier habe, das was hier steht, das ist diese
Länge des Bandabschnittes LBW,
diese Länge ist linear beschränkt in der Länge des Wortes.
Also hier habe ich irgendwo mein Wort stehen, mein Wort W, und dann
kann es sein, dass ich dort ein gewisses Vielfaches von der Länge des
Wortes noch als Speicher irgendwie brauche, aber es ist eine lineare
Abhängigkeit zwischen der Länge des Wortes und der Länge dieses
Bandes.
Ein linear beschränkter Automat.
Was heißt denn das, wenn das linear beschränkt ist?
Was kann ich mit einem solchen Automaten alles machen?
Mit einer solchen Turing-Maschine?
Wir wissen, wenn wir ein endliches System haben, dann gibt es gewisse
Eigenschaften, die wir schon mehrfach angeschaut haben.
Wenn ich ein gewisses System habe, dessen Situation ich beschreiben
kann, dann kann ich mir anschauen, wie lange eigentlich die
Ereignisfolgen sind, die ich betrachten muss, bevor ich mindestens
eine Wiederholung habe, bis ich also alles Relevante betrachtet habe.
Und wenn ich hier eine Bandbeschränkung habe, linear in der Länge des
Wortes, dann brauche ich mir nur anzugucken, wie viele verschiedene
Situationen kann diese Turing-Maschine tatsächlich haben.
In jedes Feld dieses Bandes kann ich irgendein Zeichen reinschreiben.
Da kann irgendein C stehen oder hier kann irgendein X oder 0 oder 3
oder was immer.
Je nachdem, was ich für ein Bandalphabet habe, kann ich also jede
Beschriftung dieses linear beschränkten Arbeitsbandes mir anschauen.
Und das ist dann, wie viele Möglichkeiten gibt es dafür, das zu
unterscheiden, oder wie viele solche Möglichkeiten kann ich
unterscheiden.
Das sind, nehmen wir mal an, das Bandalphabet, das war beschrieben mit
B.
Das heißt, ich habe Anzahl der Elemente von B hoch, Länge meines
Arbeitsbandes, das ich zur Verfügung habe.
Das ist die Länge des verfügbaren Bandabschnittes.
Und das heißt, dass das Ganze exponentiell ist in der Länge dieses
Bandes.
Ich habe exponentiell viele Möglichkeiten, die ich unterscheiden kann.
Danach muss ich mindestens etwas wiederholen.
Das heißt, wenn ich die Möglichkeiten alle durchgeguckt habe, noch
dazu mal Anzahl unserer Zustände, Betrag von S, das sind die möglichen
verschiedenen Zustände, die ich haben kann, dann habe ich alle
Möglichkeiten betrachtet.
Und das bedeutet, ich kann auf jeden Fall für jedes Wort, das hier
eingegeben wird, feststellen, was die Maschine irgendwann einmal tun
wird.
Das heißt, ich kann auf jeden Fall für jedes Wort entscheiden, das
hier zu Anfang draufgelegt wird, ob es akzeptiert wird oder nicht.
Weil ich ja weiß, was die Maschine tun wird in maximal dieser Zeit,
die hier angegeben ist.
Das kann eine exponentielle Zeit sein, das hatte ich Ihnen neulich
schon erzählt bei den kontextsensitiven Grammatiken, dass wir dort im
schlechtesten Fall exponentielle Zeit brauchen, um zu überprüfen, ob
das Wort erzeugt werden kann oder nicht.
Und genau das haben wir hier auch wieder drin.
Das heißt, wir haben auf jeden Fall eine exponentielle
Zeitbeschränkung für solche linear bandbeschränkten Maschinen.
Und das ist eine wichtige Eigenschaft.
Natürlich ist das eine wahnsinnig lange Zeit.
Und die Kellerautomaten, hatten wir gesehen, die arbeiten maximal
kubische Zeit in der Länge des eingegebenen Wortes.
Hier haben wir exponentielle Zeit, also von polynomial auf
exponentiell ein deutlicher Sprung, aber immerhin eine
Bandbeschränkung.
Wie kann ich jetzt überlegen, dass ich tatsächlich zu jeder Typ-1
-Grammatik, zu jeder kontextsensitiven oder auch monotonen Grammatik
einen linear beschränkten Automaten finden kann, der die gleiche
Sprache akzeptiert.
Da muss ich halt genau das, was wir uns vorüberlegt haben, mit einem
linear beschränkten Automaten machen.
Das Simulieren einer Ableitung rückwärts.
Also ich muss eine Reduktion machen.
Und hier steht, das kommt auf der nächsten Folie, wie das geht.
Aber das kann ich hier eigentlich gleich hinschreiben.
Wenn wir uns diese Ableitungsfolge für eine kontextsensitive Grammatik
anschauen, dann wissen wir ja, dass die Länge von W1 kleiner gleich
Länge von W2 ist usw.
kleiner gleich Länge von Wn.
Das heißt, wenn wir uns hier ein Band betrachten, auf dem wir arbeiten
wollen, und da steht zu Anfang unser W, dann war diese kanonische Art,
wie wir überprüfen wollen, ob das Wort aus der Grammatik erzeugt wird,
dass wir uns hier irgendwo, ich mache das W mal jetzt hier weg, und
suche mir eben hier eine rechte Seite einer Regel, die ich dann
ersetzen möchte durch ein Vieh.
Und dieses Suchen eines Psi und Ersetzen durch ein Vieh kann bedeuten,
dass ich rechts von meinem Wort W, das hier stand, noch irgendwas
machen muss als Extra-Arbeitsbereich.
Da muss ich mir vielleicht irgendwas merken, muss mir vielleicht
irgendeinen Teil hier merken, den ich erst mal lösche und dann wieder
hinschreiben muss.
Und dieses Merken kann aber nicht allzu lang werden.
Ich brauche maximal den gleichen Platz, den ich vorher für das Wort
hatte.
Also das reicht aus bei einer kontextsensitiven Grammatik.
Wenn ich mir die Regeln anschaue, was ich da so kanonisch konstruieren
würde als Turing-Maschine, wenn ich das simuliere, da reicht mir auf
jeden Fall so ein linear beschränkter Platz aus.
Die Wörter werden immer kürzer, wenn ich hier rückwärts gehe.
Und damit habe ich sofort gezeigt, dass man eben mit einem linear
beschränkten Platz, also auf einfache Art zu überlegen, da reicht es,
wenn ich den doppelten Platz zur Verfügung habe.
Man kann das sogar noch weiter reduzieren.
Da brauche ich einfach nicht viel Platz, um die kontextsensitiv
abgeleiteten Wörter zu überprüfen, ob sie tatsächlich zur Sprache
gehören.
Hier ist nochmal das dargestellt.
Jede kontextsensitive Grammatik ist monoton, das habe ich gerade eben
Ihnen aufgemalt.
Alle bei diesen Zwischenschritten auftretenden Wörter sind maximal so
lang wie das generierte Wort.
Hier ist also eine rechte Seite einer Regel.
Das wäre eine Regel, die wir hier verwenden.
V1a, V2 wird ersetzt durch V1b.
V2 ist eine schöne kontextsensitive Regel.
Dann passiert genau das, was ich Ihnen gerade eben vorgestellt habe,
dass man immer kürzere Wörter kriegt.
Und entsprechend reicht der linear beschränkte Platz aus.
Das ist kein Problem, die Bandentschrift wird nie länger.
Abgesehen davon, dass ich vielleicht ein bisschen Platz brauche, um
noch etwas hinzuschreiben.
Aber mehr ist es nicht.
Nur mal kurz zurück auf die Foreo-Folie, da stand nämlich noch eine
Konsequenz.
Wenn wir uns das jetzt überlegt haben, dass man auf die Art und Weise
die kontextsensitiven Sprachen auch durch linear beschränkte Turing
-Maschinen charakterisieren kann, dann haben wir für jede Sprachklasse
der Chomsky-Hierarchie eine äquivalente Klasse von Automaten gefunden,
mit denen wir genau die Sprachen charakterisieren können.
Also jetzt haben wir das formal alles von den einfachsten, den Typ-3
-Grammatiken bis zu den Typ-0-Grammatiken hinbekommen, dass wir
jeweils äquivalente Automaten-Modelle haben zu den Grammatiken.
Das dazu, das fassen wir alles nochmal zusammen.
Dann sehen wir, dass wir hier vieles uns schon überlegt haben für die
L3 -Sprachen, für die Typ-3-Sprachen oder auch regulären Sprachen,
hatten wir gesehen, wir können sie durch rechts- beziehungsweise
linkslineare Grammatiken erzeugen.
Wir können sie erkennen durch deterministische oder nicht
-deterministische endliche Automaten.
Wenn Sie wollen, können Sie auch Lambda-Automaten nehmen, die habe ich
Ihnen gar nicht vorgestellt, aber Sie können nachschauen, was das ist.
Da sind einfach Lambda-Übergänge noch mit drin, sind nicht relevant.
Dann haben wir die operationelle Methode, die Charakterisierung durch
Operationen, durch Vereinigung, durch Produkt und durch Iteration,
hatten wir die regulären Sprachen bekommen.
Wir hatten das Pumping Lemma definiert, also diese Möglichkeit, dann
für Sprachen zu zeigen, dass sie nicht erkennbar sind durch endliche
Automaten.
Erkennungsaufwand linear, aber eben leider nicht ausdrucksfähig genug.
Und dann kamen wir zu den kontextfreien Sprachen, die auch wieder
durch Grammatiken erkennbar oder erzeugbar sind.
Da hatten wir unterschieden, einerseits die normalen kontextfreien
Grammatiken, dann aber auch die sogenannten LRK-Grammatiken, hatte ich
Ihnen ganz kurz dargestellt, nicht in allen Einzelheiten, aber eben
gezeigt, dass man diese deterministische Arbeit eines Kellerautomaten
bei einer kontextfreien Grammatik auch nachbilden kann mit bestimmten
Eigenschaften, die sich darauf beziehen, wie man im Prinzip aus einem
Wort die nächsten ableiten kann, beziehungsweise erkennen kann, welche
Regel angewendet sein muss.
Das sind Anforderungen an die Regeln der Grammatik, damit das dann
eine LRK-Grammatik sein kann.
LRK stand hier für von links nach rechts lesen, eine Rechtsableitung
erzeugen und dabei jeweils K-Zeichen nach rechts noch schauen können.
Die Automaten waren deterministisch für LRK-Grammatiken, nicht
deterministisch für beliebige kontextfreie Grammatiken.
Da war die Sprache, die entscheidend war, war die Sprache für diese
Unterscheidung zwischen den deterministischen und nicht
deterministischen, die Sprache der Palindrome, die wir genommen hatten
als Beispiel, die man nicht durch einen deterministischen
Kellerautomaten erkennen konnte und die Sprache, die man nicht durch
einen endlichen Automaten erkennen kann, war das a-hoch-n-b-hoch-n.
Damit hatten wir diese Struktureigenschaft, dass wir hier also
beliebige Klammerausdrücke im Prinzip erkennen können mit den
kontextfreien Grammatiken oder erzeugen können kontextfreien
Grammatiken erkennen mit Kellerautomaten.
Das ist hier bei kontextfreien Sprachen gegeben, aber möglichst wollen
wir den Erkennungsaufwand nicht über linear wachsen lassen.
Deswegen sind die deterministischen kontextfreien Sprachen diejenigen,
die wir brauchen.
Das waren die kontextfreien, die kontextsensitiven Sprachen, auch
wieder durch Grammatiken beschrieben, wie wir gerade gesehen haben,
durch die nicht deterministischen, die müssen natürlich auch nicht
deterministisch sein, so hatten wir das ja simuliert, linear
beschränkten Automaten.
Dann hatten wir hier für die kontextsensitiven Sprachen keine weiteren
Strukturaussagen gemacht, wir hatten aber eine Sprache gesucht, die
halt kontextsensitiv ist, aber nicht kontextfrei.
Das war das a-hoch-n-b-hoch-n-c-hoch-n.
Und hier ist der Aufwand eben exponentiell im schlechtesten Fall in
der Länge des Wortes, das wir überprüfen wollen.
Deswegen nicht geeignet für unser Ziel, die Programmiersprachen
sinnvoll zu beschreiben.
Wir hatten gesehen, das, was uns eigentlich interessiert, ist das, was
hier in dieser Zeile steht.
Das andere ist alles wichtig, um zu erkennen, wie diese ganzen
Sprachklassen zusammenhängen.
Das, was hier noch offen ist, das folgt im nächsten Kapitel.
Das, was wir hier gesehen haben, ist einerseits etwas zur
Ausdrucksfähigkeit, das war die eine wesentliche Frage, was ist das
formale Modell, das mir genau die notwendige Ausdrucksfähigkeit gibt,
die ich brauche, um Programme einer sinnvollen Programmiersprache
beschreiben zu können.
Die zwei Sprachen sind ausreichend, insbesondere die deterministischen
Kellerautomaten erkennbaren beziehungsweise die LRK-Grammatiken.
Dann gibt es zwar auch noch in Programmiersprachen kontextsensitive
Dinge, wie dass man eine Variable, die man verwendet, vorher
deklariert haben muss und ähnliche Dinge.
Das sind weitere Abhängigkeiten, die man aber als semantische
Anforderung ansieht, die man getrennt von der Syntaxprüfung dann
abhandelt.
Die wesentlichen Syntax-Eigenschaften sind diejenigen, die wir uns
betrachtet haben, die sind kontextfrei.
Und dann haben wir den Erkennungsaufwand betrachtet und haben gesehen,
da sind es die deterministischen kontextfreien Sprachen,
beziehungsweise LRK-Grammatiken oder deterministische
Kellerakzeptoren.
Und die nächsten, noch vernünftig algorithmisch handhabbaren, sind die
kontextsensitiven, aber vom Aufwand her deutlich jenseits dessen, was
wir in der Regel machen würden.
So, kurze Hinweise zwischendurch, bevor ich ins nächste Kapitel gehe.
Am Montag hatte ich gesagt, nächsten Montag am 1.12.
keine Vorlesung, sondern eine große Saalübung.
Das heißt, da werden meine Mitarbeiterinnen und Mitarbeiter Ihnen
etwas erzählen, nochmal zur Vertiefung der Dinge, die wir in den
Übungen vermitteln wollen, als Ergänzung zu dem oder Vertiefung
dessen, was wir hier in der Vorlesung machen.
Die Saalübung wird nicht aufgezeichnet.
Da kam letztes Mal eine Frage.
Das heißt, wenn Sie davon profitieren wollen, müssen Sie zur Vorlesung
kommen.
Insofern haben Sie dann die Möglichkeit, etwas mehr intensiver zu
hören.
Dann noch eine weitere Ankündigung.
Sie wissen, dass im Januar eine Bonusklausur fällig wird.
Und für diese Bonusklausur müssen Sie sich anmelden.
Das geht ab Montag bis zum 31.12., also der ganze Monat Dezember steht
dafür zur Verfügung.
Und das ist eine Ausschlussfrist.
Das heißt, wer die sich nicht bis zum 31.12.
angemeldet hat, der wird an der Bonusklausur nicht teilnehmen.
Das werden wir noch mehrfach wiederholen.
Also Sie haben genügend Zeit, sich da anzumelden.
Die Anmeldeprozedur, wo Sie sich da anmelden müssen, steht alles auf
den Webseiten der Vorlesung.
Schauen Sie sich das bitte an.
Gut, das war der Teil über die Grammatiken, über die formalen
Sprachen.
Und jetzt müssen wir zum nächsten Kapitel kommen, in dem wir uns jetzt
beschäftigen mit der nächsten Frage.
Nämlich, was hat es eigentlich mit den Algorithmen auf sich, die wir
als Informatiker formulieren können?
Was können wir berechnen?
Was können wir mit solchen Maschinen wie einem normalen Rechner, was
können wir mit einem Taschenrechner eigentlich machen?
Die können doch jede Funktion berechnen.
Das war das, was man lange Zeit geglaubt hat, so Anfang des vorigen
Jahrhunderts, auch davor, haben die Wissenschaftler festgestellt, was
sie alles für tolle Erkenntnisse gewinnen können, waren der Meinung,
eigentlich kann man doch alles berechnen.
Sie werden sehen, das geht leider nicht.
Wir können zeigen, dass es bestimmte Fragestellungen gibt, auf die Sie
nicht in endlicher Zeit eine Antwort geben können.
Und dann ist die Frage für diejenigen Funktionen oder Probleme, die
man in endlicher Zeit berechnen oder lösen kann, wie aufwendig ist es
denn eigentlich?
Das ist das, was uns als Informatiker interessiert.
Wie ist eigentlich der Aufwand, auch für Wirtschaftsingenieure ist das
besonders wichtig, Kostenminimierung etwas effizient zu machen,
Ressourcen bestmöglich ausnutzen.
Wie sieht das aus mit der Komplexität der Funktionen, der
Berechnungen?
Wie groß ist der Aufwand?
Was kann man darüber aussagen?
Das wird uns jetzt beschäftigen.
Sie erinnern sich, dass in Informatik 1 Ihnen schon mal erzählt wurde,
was ein Algorithmus ist.
Im Wesentlichen ist das ein endlich beschriebenes Verfahren mit Ein-
und Ausgabe.
Also ich habe eine Eingabe, ich habe eine Eingabe, ich habe eine
Ausgabe und zwischendrin passiert irgendetwas.
Verarbeitung.
Das IFA-Prinzip.
Eingabe, Verarbeitung, Ausgabe.
Das für alle zulässigen Eingaben, also nur zulässige Eingaben, nach
endlich vielen Schritten anhält und ein Ergebnis produziert.
Ich kann es rechnerbezogen formulieren, ein Algorithmus ist ein für
alle zulässigen Eingaben terminierendes Programm endlicher Länge auf
einem abstrakten Rechner.
Abstrakter Rechner heißt, ich sage nur, welche Operationen ausführbar
sind.
Ich muss den Rechner nicht weiter beschreiben, wie er das macht.
Das kommt dann in der technischen Informatik.
Ich muss nur wissen, er hat bestimmte Operationen, die er machen kann.
Und ich kann auch sagen, das ist eine Turing-Maschine.
Das ist aber dann eine andere Art der Spezifikation eines Algorithmus,
aus jeden Fall ein endlich beschriebenes Verfahren.
Also das haben Sie schon in der Grundlageninformatik 1 gelernt.
Und die wesentlichen Eigenschaften sind, dass wir nicht nur eine
spezielle Probleminstanz lösen wollen.
Wir wollen nicht eine spezielle Folge, meinetwegen hier, wenn wir
irgendeine Folge haben, so nur diese eine Folge wollen wir sortieren
können.
3 0 1 2 wollen wir in diese Reihenfolge 0 1 2 3 oder in 3 2 1 0
bringen können.
Das wäre kein Algorithmus, der nur eine einzelne Instanz bearbeitet,
sondern ich möchte eine gewisse Anzahl von Problemausprägungen damit
bearbeiten können.
Beim Sortieren sage ich, ich möchte eine beliebige Folge von Zahlen,
bei denen ich die einzelnen Elemente vergleichen kann in Bezug auf
ihre Größe, also ich sage da auch Zahlen, also Elemente, die ich in
Bezug auf ihre Größe vergleichen kann, die möchte ich in eine
aufsteigende oder absteigende Reihenfolge bringen können.
Das ist eine allgemeine Anforderung.
Viele Instanzen gibt es dafür.
Also eine Instanz ist eine Ausprägung eines Problems.
3 0 1 2 ist eine spezielle, sortierende Folge.
Das nächste ist die Determiniertheit.
Wenn ich ein Verfahren wiederholt ausführe, dann soll bei gleicher
Eingabe die gleiche Ausgabe rauskommen.
Das ist eine klassische Anforderung an einen Algorithmus.
Wir haben Ausnahmen davon, wir haben randomisierte Algorithmen.
Ich gebe Ihnen gleich noch Beispiele dafür.
Das nächste, klassische, ist die Endlichkeit.
Und zwar die Beschreibung des Verfahrens ist von endlicher Länge.
Ich kann ein Stück Papier oder mehrere Papiere Ihnen geben, aber es
ist ein Stapel endlicher Höhe, wo die ganzen Anforderungen draufstehen
für einen Algorithmus.
Eine finite Beschreibung.
Kann sehr lang sein, 10.000 Seiten Spezifikation für das Mautsystem in
Deutschland.
Das ist eine endliche Beschreibung.
Sehr, sehr, sehr lang, trotzdem noch endlich.
Besser ist es, wenn Sie das kurz beschreiben können.
Effektivität heißt, jeder einzelne Schritt muss ausführbar sein in
endlicher Zeit.
Das ist effektiv.
Terminiertheit nochmal, für jede zulässige Eingabe habe ich endlich
viele Schritte, um zu einem Ergebnis zu kommen.
Also mehrfache Endlichkeitsanforderungen dabei.
Und jetzt kommen die ganzen Beispiele.
Sortierverfahren hatte ich Ihnen schon genannt.
Sortieren beliebiger Folgen.
Berechnung kürzester Wege.
Sie haben irgendwelche Orte, die Sie befahren wollen.
Sie wollen wissen, wie ist der kürzeste Weg hier von A nach B.
Sie nutzen alle Navigationssysteme.
Da sind Verfahren zur Berechnung kürzester Wege drin, die hoffentlich
gut sind.
Und nicht nur den einfachen Dijkstra verwenden, sondern die Verfahren,
die hier am KIT entwickelt wurden, die guten Verfahren haben das drin.
Also das sind die Berechnungen kürzester Wege.
Dijkstra-Verfahren ist ein typisches Beispiel, das man an vielen
Stellen tatsächlich verwendet.
Dann haben wir die Verfahren zur Reduktion endlicher Automaten.
Auch ein Beispiel für deterministische Algorithmen, haben Sie
kennengelernt.
Der Ansatz über dynamisches Programmieren, wie man einen beliebigen
endlichen Automaten reduzieren kann auf einen Automaten, in dem es
keine äquivalenten Zustände mehr gibt, sondern die sind alle
wesentlich für das Verhalten des Automaten.
Oder auch kontextfreie Grammatik in Kellerautomaten zu überführen.
Sie haben also schon eine Reihe Algorithmen kennengelernt.
Sie wissen, was ein Algorithmus ist.
Syntaxanalyse bezüglich einer kontextfreien Grammatik, also die
Überprüfung der Zugehörigkeit eines Wortes zu der Sprache.
Da haben wir allgemein einen Algorithmus angegeben.
Den Algorithmus von Koki Janga Kasami habe ich Ihnen nicht mehr
angegeben, aber das ist auch ein Beispiel für Überprüfung, ob ein Wort
zur Sprache gehört oder nicht.
Und das hatte ich gesagt, ich werde Ihnen auch die randomisierten
Algorithmen beschreiben oder kurz dafür Beispiele geben.
Klassischer Algorithmus, der randomisiert ist, ist der Primzahltest.
Wir prüfen, ob eine Zahl eine Primzahl ist oder nicht.
Würden Sie sagen, ja, wen interessiert das schon?
Wenn Sie sicher kommunizieren wollen, also in der Kryptografie,
brauchen Sie Verfahren, mit denen Sie verschlüsseln können.
Wenn Sie sicher, also vertraulich kommunizieren wollen, brauchen Sie
für die Verfahren mit öffentlichem Schlüssel, also die Public-Key
-Krypto -Verfahren, brauchen Sie Primzahlen, zwar große Primzahlen mit
etwa 1000 bis 2000 Stellen.
Wenn Sie solche großen Zahlen haben, ist es sehr aufwendig, mit
einfachen Verfahren Primzahl-Tests zu machen.
Und wenn Sie das randomisiert machen, geht das ganz schnell.
Das war ein tolles Ergebnis, hat man so Ende der 70er, Anfang der 80er
Jahre, hat man diesen randomisierten Primzahl-Test sich überlegt.
Das heißt aber auch, dass das Ergebnis, das man bekommt, nicht mit 100
%iger Sicherheit richtig ist.
Das heißt, wenn Ihnen dieser Primzahl-Test sagt, ich habe hier
festgestellt, dass es keine Primzahl, dann ist es keine Primzahl.
Wenn der Test aber nicht festgestellt hat, dass es keine Primzahl ist,
dann kann es trotzdem sein, dass es keine Primzahl ist, man hat es nur
nicht festgestellt.
Man kann diese Wahrscheinlichkeit aber beliebig klein machen.
Anderes gutes Beispiel für randomisierte Algorithmen sind evolutionäre
Algorithmen, bei denen Sie Zufallsentscheidungen treffen.
Wenn Sie zum Beispiel eine, ich hatte gesagt, bestmögliche Wege
finden, wenn Sie eine Reihe von Städten besuchen wollen, Sie wollen da
eine bestmögliche Tour finden, das ist ein schwieriges Problem, Sie
machen das mit einem evolutionären Algorithmus, bei dem Sie zufällig
sich irgendwelche Wege durch eine Menge von Städten suchen, also ein
Problem einfach mit Zufallsentscheidungen bearbeiten, dann bekommen
Sie für jede Ausführung des Algorithmus, abhängig von Ihrem
Zufallszahlengenerator, unterschiedliche Lösungen.
Also die Eigenschaft, die wir da hatten, der Determiniertheit ist da
nicht vorhanden, aber wir wollen ja nur Lösungen haben, die möglichst
gut sind.
Und da ist es gar nicht so schlimm, wenn die Lösungen am Ende sich
leicht unterscheiden, Hauptsache die Qualität der Lösungen stimmt.
Und insofern gibt es da halt verschiedene Möglichkeiten, die auch
wichtig sind.
Anderes Beispiel sind Ameisen-Algorithmen.
Was sind Ameisen-Algorithmen?
Wenn Sie sich anschauen, wie Ameisen laufen, die laufen normalerweise
über irgendwelche Straßen.
Die Eigenschaft der Ameisenstraße ist, dass wenn Sie hier irgendeinen
Widerstand reinlegen oder irgendein Hindernis reinlegen, dann finden
die relativ schnell den kürzesten Weg um dieses Hindernis herum.
Dieses einfache Finden eines Weges um ein Hindernis herum ist eine
Eigenschaft, dass man einen kürzesten Weg finden kann.
Also eine bestmögliche Lösung für ein neues Problem, für ein sich
dynamisch verändertes Problem.
Und diese Möglichkeiten der Ameisen-Kolonien, tatsächlich solche
kürzesten Wege zu finden, kann man sehr einfach nachbilden.
Das ist ein Prinzip von Pheromonen, da hat man Wahrscheinlichkeiten
bestimmte Wege zu gehen oder nicht zu gehen.
Und kann dadurch ein Optimierungsprinzip ableiten, das wir dann als
Ameisen -Algorithmus bezeichnen.
Wichtige Heuristiken oder Meta-Heuristiken, also das hier sind
sogenannte Meta-Heuristiken, weil sie nicht nur für ein Problem
beschrieben sind, also nicht nur eine Heuristik für ein spezielles
Problem, sondern Heuristiken, die Sie für ein nicht beliebiges
Problemklassen einsetzen können.
Also das sind interessante Arten von Algorithmen, ähnlich Particles
-Form -Optimization.
Schöne Themen, die wir z.B.
in der Vorlesung Naturenspirit-Optimierungsverfahren von Herrn Schukla
im Sommersemester Ihnen präsentieren.
Gut, das kurz nochmal zu den deterministischen und randomisierten
Algorithmen.
Das sind so die Arten, wie wir über Algorithmen geredet haben, wie Sie
über Algorithmen geredet haben in der Grundlage der Informatik 1.
Jetzt müssen wir das Ganze irgendwie, eigentlich auch irgendwann mal
formalisieren.
Zunächst mal machen wir das intuitiv.
Wir sagen, wir haben eine gewisse Problemklasse, z.B.
Sortierprobleme.
Wir betrachten eine Menge von Problemausprägungen, also Listen z.B.,
die sortiert werden sollen.
Also jeweils Datensätze, die eine konkrete Probleminstanz beschreiben,
die Eingabe für Ihr Programm, das jetzt sortieren soll.
Dann schauen Sie sich die Menge der Lösungen an.
Sie haben hier Ihre Problemklasse.
Sie haben ein Problem A, das Sie hier bearbeiten können.
Also, wir sind bei dem Algorithmus, den wir irgendwie charakterisieren
wollen.
Wir haben die Problemklasse, wir haben die Instanzen A.
Wir haben zu jeder Instanz eine Lösung, ich nenne die mal LA, die
Lösung zu einer konkreten Instanz.
Und die bekommen wir über einen Algorithmus AP.
Ein Algorithmus zu der Klasse P liefert uns eine Lösung zu unserem
Problem.
Also, wir haben die Menge der konkreten Problemausprägungen.
Wir haben die Menge von Lösungen und unser Algorithmus soll jede
einzelne Lösung hier beschreiben.
Also dieses A ist die Menge der konkreten Problemausprägungen, alle
Sortierinstanzen.
Das Problem ist das Sortierproblem in diesem Beispiel.
A ist die Menge aller Instanzen, also alle zu sortierenden Folgen.
Und ein Sortierverfahren liefert dann eine sortierte Folge zu einer
nicht sortierten Folge.
Also ein Algorithmus ist dann ein allgemeines Verfahren, welches auf
richtige Anfangsdaten A aus A angewendet, nach endlich vielen
elementaren Schritten hält und die Lösung LA liefert.
Also, das ist hier unsere Problemklasse, ich habe die Menge der
Instanzen und ich habe für jede konkrete Probleminstanz, klein A aus
A, mit meinem Algorithmus AP, eine konkrete Lösung, klein, also LA zu
diesem Problem gefunden.
Jetzt hat jemand eine Frage.
Welche Verfahren wurden beispielsweise am KIT entwickelt?
Richtig, am KIT wurde Folgendes entwickelt, das hatte ich gerade
erwähnt, bei den Verfahren für kürzeste Wege.
Wenn Sie kürzeste Wege haben wollen und Sie betrachten das
Navigationsproblem, dann wollen Sie zum Beispiel von Karlsruhe nach
Hamburg fahren.
Und dann gibt es viele mögliche Straßen, die Sie fahren können.
Zu jeder nächsten Stadt, viele mögliche Verzweigungen.
So, das können Sie mit dem Dijkstra-Verfahren machen.
Das ist ein Graph, da können Sie kürzesten Weg bestimmen.
Dann finden Sie von jedem Ort zu jedem anderen, können Sie den
kürzesten Weg bestimmen.
Das geht mit dem Dijkstra-Verfahren in quadratischer Zeit, gar kein
Problem.
Aber wenn Sie einen Graphen haben, der Größe eines Straßennetzes in
Deutschland, ist das wahnsinnig lang.
Und wenn Sie das jetzt verbessern wollen, dann müssen Sie in der Lage
sein festzustellen, was kann ich hier reduzieren, wie kann ich den
Aufwand kleiner machen.
Und das sieht so aus, dass man dann auf eine geschickte Art und Weise
einen Ausschnitt definieren kann, der relevanten Straßenzüge.
Und über solche Verfahren kriegt man also eine Reduktion des Aufwandes
in solchen großen Graphen um den Faktor 10 hoch 6.
Also eine Million mal schneller für konkrete solche Aufgaben als das,
was Sie mit dem Dijkstra-Verfahren machen würden.
Also konkrete Verbesserungen.
Können Sie nachlesen bei Veröffentlichungen von Frau Wagner und Herrn
Sanders.
Die haben das gemacht, hier vor allen Dingen am KIT, haben dafür auch
viele Preise gekriegt.
Ist von Google auch eingebaut worden in deren Software.
Also das sind schon sehr schöne Sachen, dass man den Aufwand deutlich
reduzieren kann, indem man halt guckt, was ist eigentlich relevant in
solchen riesigen Graphen, die in der Realität tatsächlich auftauchen.
Geht aber an dem vorbei, was wir eigentlich hier machen müssen.
Wir müssen uns erstmal allgemein mit dem Problem der Charakterisierung
von Algorithmen beschäftigen, damit wir das dann konkret auch besser
machen können, wie zum Beispiel bei diesen Verfahren für kürzeste
Wege.
Also, schreibweise unser Algorithmus AP transformiert jede Instanz aus
einer Klasse von Problemen A in eine Menge von Lösungen, oder in eine
Lösung jeweils.
Und für determinierte Algorithmen ist das eine Funktion, wenn wir
einen randomisierten Algorithmus haben, kann es sein, dass das ihnen
eine Menge von möglichen Lösungen gibt.
Also wenn sie zum Beispiel ein multikriterielles Problem haben, kann
es sein, dass sie hier eine Menge von Lösungen kriegen.
Wir haben zwei Kriterien, F1 und F2.
Dann sind sie an der Pareto-optimalen Front interessiert.
Und das ist eine Menge von potenziellen Lösungen, die ihren
Anforderungen bestmöglich entsprechen.
Und der Entscheider muss dann auswählen, welche Lösung er wählen will.
Also das sind typische Probleme, mit denen sie es auch zu tun haben in
ihrer späteren beruflichen Praxis.
Das ist aber natürlich keine mathematische Definition.
Hier steht etwas, ein allgemeines Verfahren nach endlich vielen
elementaren Schritten.
Wie beschreibt man das denn formal?
Und das müssen wir jetzt anschauen, wie kann man das ganz konkret
aufschreiben?
Was ist ein Algorithmus und was nicht?
Wie muss man entscheiden können, das ist ein Algorithmus, das ist
keiner?
Und da hat man viele verschiedene Möglichkeiten zu überlegen, wie man
das machen kann.
Und das gleiche gilt also für das Problem der berechenbaren
Funktionen.
Das eine sind die Probleme, die ich lösen möchte, das andere sind
Funktionen, die ich berechnen möchte.
Also ein Sortieren ist ja zunächst mal keine Funktion.
Ich könnte sagen, ich bilde eine nicht-sortierte Folge auf eine
sortierte Folge ab.
Eine Funktion berechnen ist sowas wie, wir hatten gesehen, wir wollen
eine 1 addieren können auf eine Zahl, konnten wir offensichtlich mit
einer Turing-Maschine machen.
Ich möchte etwas berechnen, ich möchte einen Primzahltest machen.
Das sind Funktionen, die wir berechnen wollen, für die wir aber auch
Algorithmen brauchen, um diese Funktion tatsächlich zu berechnen.
Aber das ist eine andere Art, Probleme zu beschreiben.
Bei berechenbaren Funktionen schreiben wir folgendes, wir haben
irgendein Alphabet, wir haben irgendwelche beliebigen Teilmengen von E
-Stern, also irgendwelche Mengen von Wörtern und wir haben eine
Funktion, die eine gewisse Teilmenge von Wörtern auf eine gewisse
andere Teilmenge abbildet.
Also eigentlich haben wir unser E-Stern und E-Stern nochmal
hingeschrieben und wir haben hier eine Teilmenge M1, hier eine
Teilmenge M2 und eine Funktion, die jedes Element aus M1 auf irgendwas
in M2 abbildet.
Wir hatten gesagt, beim Algorithmus habe ich eine Menge zulässiger
Eingaben und daraus kommen irgendwann irgendwelche Ausgaben raus.
Diese Einschränkung zulässiger Eingaben ist das, was wir hier
schreiben als eine Teilmenge M1.
Gewisse Elemente von M1 werden auf Elemente von M2 abgebildet.
Es kann sein, dass es ganz einfach ist, dass wir irgendwelche Zahlen
addieren wollen oder potenzieren oder was immer.
Und diese Funktion F, die heißt berechenbar, wenn es einen Algorithmus
gibt, der uns für jedes Argument der Funktion ein Ergebnis liefert.
Also für jedes Argument der Funktion W nach endlich vielen Schritten
ein Ergebnis liefert.
Algorithmus hätte ja die ganzen Endlichkeitsanforderungen.
Da sehen Sie die Beziehung zwischen Berechenbarkeit und Algorithmus.
Ich brauche einen Algorithmus, um eine Funktion zu berechnen.
Beispiel hier nochmal.
Es kann sein, dass E die Menge aller Dezimalziffern ist.
Dann ist die Menge E-Stern die Menge aller Dezimalzahlen, die ich
aufschreiben kann.
Ich kann es noch ein bisschen genauer spezifizieren.
Ich kann sagen, die Zahlen, die sollen wir bitte nicht mit einer Null
anfangen, sondern mit einer Ziffer, die nicht Null ist.
Danach können irgendwelche weiteren Ziffern folgen.
Das wäre genau diese Sprache hier, die Null, vereinigt mit einer
beliebigen Ziffernfolge, beginnend mit einer nicht Null.
Das ist genau die Menge der natürlichen Zahlen.
Das war eine Interpretation der Folgen von Dezimalziffern als
natürliche Zahlen.
Natürliche Zahlen sind ja zunächst mal nur irgendein abstakter
Begriff.
Ich kann etwas haben, was dem Wert Null entspricht.
Ich kann etwas haben, was dem Wert Eins entspricht.
Das kann ich verdoppeln.
Dann kann ich daraus etwas haben, was dem Wert Zwei entspricht.
Dann kann ich noch etwas dazu fügen.
Das sind natürliche Zahlen.
Und die beschreiben wir dann durch irgendwelche Ziffernfolgen.
Das heißt, wir haben durch diese Ziffernfolgen, die in L drinstehen,
das können wir sagen, die repräsentieren gerade die natürlichen
Zahlen.
Da kommen wir später noch drauf, auf die Zahlendarstellungen.
Genauer ist es so, dass es eine bijektive Abbildung gibt.
Bijektiv, das wissen Sie aus der Mathematik.
Injektiv und sujektiv, das heißt, injektiv heißt, Sie haben niemals,
also wenn Sie sich hier irgendein Element anschauen, also wenn f von
x1 gleich f von x2 ist, dann folgt daraus x1 gleich x2.
Das ist die Injektivität.
Es werden nicht zwei Elemente auf das gleiche Ergebnis abgebildet.
Und die Sujektivität heißt, dass jedes Element aus dem Bildbereich
tatsächlich auch getroffen wird.
Das heißt, ich kann ja so hinschreiben, für alle x aus dem Beispiel M2
gibt es irgendein y aus M1, sodass f von y gleich x ist.
Das ist die übliche Art, wie wir Sujektivität beschreiben.
Wenn wir eine Funktion haben von M1 nach M2, wie da oben angedeutet.
Beziehungsweise in diesem Fall ist es so, dass wir eben jede
Ziffernfolge injektiv auf eine Zahl abbilden können, eine eindeutige
Zahl.
Es sind nicht zwei Ziffernfolgen, die die gleiche Zahl beschreiben.
Und jede Zahl kann durch eine Ziffernfolge beschrieben werden.
Ich kann auch sagen, dass phi und phi hoch minus 1, die
Umkehrfunktion, beide berechenbar sind.
Ich kann zu jeder Ziffernfolge sagen, welche Zahl das ist.
Und ich kann zu jeder Zahl sagen, wie ich sie durch eine Ziffernfolge
beschreiben möchte.
Wir werden später sehen, dass man das durchaus für unterschiedliche
Alphabete machen kann.
Also nicht nur für Dezimalziffern, sondern auch für Dualziffern oder
was immer Sie haben wollen.
Weitere Beispiele für solche berechenbaren Funktionen, die eine hatte
ich Ihnen schon gezeigt, da hatten wir sogar gesehen, da gibt es einen
Algorithmus, den ich als Turing-Maschine beschreiben kann, der mir
erlaubt, eine Zahl um 1 zu erhöhen.
Dann gibt es ein Algorithmus, der für jede Zahl mir eine Antwort
liefert, ja oder nein.
Und zwar sagt die Funktion ja, falls das N eine Primzahl ist und nein
sonst.
Das wäre ein Primzahltest, das hatte ich auch schon kurz erwähnt.
Oder Sie wollen für zwei Zahlen feststellen, was der größte gemeinsame
Teiler ist.
Sicherlich Funktionen, von denen wir wissen, wie man sie berechnet.
Hier in dem Fall der Euclidische Algorithmus, also einfache
Funktionen, das kennen Sie alles.
Berechenbare Funktionen.
Jetzt brauche ich noch etwas, ein paar formale Grundlagen, um dann
tatsächlich zu diesen Formalisierungen von Algorithmen zu kommen.
Ich muss Ihnen etwas erzählen über abzählbare und überabzählbare
Mengen.
Wir hatten das neulich schon mal kurz erwähnt, als ich sagte, es gibt
Sprachen, die sind nicht durch endliche Systeme beschreibbar.
Ich hatte damit begründet, dass die Menge der Teilmengen, der Menge
aller Wörter, dass die überabzählbar ist.
Was ist das überhaupt?
Und ich kann Ihnen das hier beschreiben.
Also es ist offensichtlich, dass man jede berechenbare Funktion durch
viele verschiedene Algorithmen berechnen kann.
Sie können Algorithmen beliebig verändern, irgendwelche Schleifen
einbauen und haben immer noch die gleiche Funktion berechnet.
Sie können Unsinnige machen, Sachen oder unnötige Dinge machen
zwischendrin.
Sie können viele Algorithmen definieren.
Die Frage ist, ist jede Funktion von N nach N berechenbar?
Ich habe eine beliebige Funktion von N nach N, kann ich jede solche
Funktion berechnen?
Und dazu brauche ich diese Begriffe Abzählbarkeit und
Überabzählbarkeit.
Und diese eine Menge heißt abzählbar, genau dann, wenn diese Menge M
injektiv in die Menge der natürlichen Zahlen abbildbar ist.
Das heißt, ich kann im Prinzip jedem Element aus der Menge M eine
natürliche Zahl zuordnen, kann sie also in dieser Weise abzählen.
Wenn ich das nicht kann, wenn es also keine Funktion gibt, die es mir
erlaubt, injektiv meine Menge M in das N abzubilden, das heißt,
beordne nicht zwei Elementen von M die gleiche Zahl zu, sondern alle
müssen verschieden sein, dann reicht also offensichtlich diese Menge
der natürlichen Zahlen nicht aus, um alle Elemente von M tatsächlich
injektiv abzubilden, dann ist das überabzählbar.
Alles, was natürliche Zahlen sind, verbinden wir intuitiv mit dem
Begriff der Abzählbarkeit.
Typische Beispiele für abzählbare Mengen ist natürlich so, dass jede
endliche Menge problemlos auf, wenn ich also sage, ich habe eine
endliche Menge, wenn das hier irgendwie Anzahl der Elemente gleich N
ist, dann kann ich das M problemlos abbilden, also injektiv abbilden,
auf die Menge der Zahlen 1 bis N.
Kein Problem, kann ich injektiv da rein abbilden.
Es gibt viele verschiedene Arten solcher Abbildungen, je nachdem, wie
Sie die anordnen wollen, aber das ist sicherlich möglich.
A-Stern kann ich auch abzählen.
Wie kann ich A-Stern abzählen?
Wie mache ich das denn?
Das sind doch schon mal sehr viele Wörter.
Wieso ist das abzählbar?
Welche Wörter sind da denn drin?
Nehmen wir mal ein ganz einfaches Alphabet, nämlich das Alphabet A
gleich 0 und 1.
Noch einfacher wäre, nur das Alphabet 0 zu nehmen, nur ein Zeichen.
Nehmen wir mal zwei Zeichen.
Die Wörter, die da drin sind, kann ich nach ihrer Größe anordnen.
Das leere Wort, die Wörter der Länge 1, die Wörter der Länge 2, die
Wörter der Länge 3 und so weiter.
Ich kann also alle Wörter über dem Alphabet 0, 1 anordnen, in einer
lexikografischen Ordnung und habe dann jeweils entsprechend der
Position eine injektive Abbildung von jedem Wort auf eine
entsprechende Zahl.
Also Lambda bekommt die Position 0, 0 bekommt die Position 1, 1
bekommt die Position 2 und so weiter.
So kann ich die alle abzählen.
Und damit habe ich sofort ein Verfahren, wie ich zu irgendeinem
beliebigen Wort feststelle, welche Zahl ich diesem Wort zuordnen muss.
Ich brauche nur diese Reihenfolge dieser einfachen Anordnung mir
anzuschauen, welche Zahl ich zuordnen muss.
Also ich kann sagen, ich mache es lexikografisch, ich kann es auch
anders anordnen, das ist völlig beliebt.
Überabzählbare Mengen.
Das reelle Intervall, die Menge aller reellen Zahlen zwischen 0 und 1
ist eine nicht abzählbare Menge.
Und dafür gibt es einen Beweis durch Diagonalisierung.
Was Diagonalisierung ist, werden wir gleich noch sehen.
Das ist ein sehr schönes mathematisches Verfahren, ein
Widerspruchsverfahren.
Auch die Potenzmenge von Astern ist überabzählbar.
Und da kommen wir gleich drauf, was also Diagonalisierung ist.
Da nimmt man an, dass man etwas sagen kann, dass es abzählbar wäre und
kann zeigen, dann fehlt da was drin.
Und jetzt kommen wir zu dem Satz, den wir entsprechend zeigen wollen.
Wir wollen zeigen, dass die Menge aller Funktionen von E-Stern nach E
-Stern überabzählbar ist.
Und, dass die Menge aller berechenbaren Funktionen aber abzählbar ist.
Hatte ich Ihnen im Prinzip alles schon erzählt, als ich Ihnen kurz
andeutete, die Menge der Sprachen, die wir formal beschreiben können
durch endliche Systeme, ist abzählbar, während die Menge aller
Sprachen überabzählbar ist.
Das steht hier nochmal für die berechenbaren Funktionen, das wollen
wir uns jetzt gleich auch formal nochmal anschauen.
Wenn der Satz stimmt, dann ist es offensichtlich so, dass nicht jede
Funktion berechenbar ist, dass die berechenbaren Funktionen nur einen
kleinen Anteil aller möglichen aufschreibbaren oder aller möglichen
vorstellbaren Funktionen tatsächlich darstellen.
Wobei schon, wenn ich sage, vorstellbare Funktionen, wenn ich mir
etwas vorstellen kann, muss es endlich beschreibbar sein.
Also ich kann mir die im Prinzip nicht vorstellen, aber sie
existieren.
Der Beweis funktioniert folgendermaßen.
Warum ist die Menge aller Funktionen überabzählbar?
Wir nehmen an, diese Menge aller Funktionen, die wäre abzählbar.
Wenn sie abzählbar sind, dann kann ich natürlich die Funktionen alle
so aufschreiben.
Ich schreibe die Funktion f1 auf, die Funktion f2, die Funktion f3 und
so weiter, die schreibe ich alle schön nacheinander.
Das sind also meine Funktionen und ich will jetzt hier praktisch die
Funktionen f1, f2, f3 einfach anordnen.
Und meine Wörter, die kann ich auch alle anordnen, das wissen wir, das
haben wir uns schon überlegt.
Ich kann die Wörter über einem Alphabet E alle anordnen, auf
irgendeine Art und Weise.
Sie können die Art und Weise nehmen, die ich gerade eben angedeutet
habe, mit einer lexikografischen Anordnung.
So, dann haben wir eine Tabelle und die Tabelle steht auf der nächsten
Folie.
Wir betrachten diese Tabelle, wo wir jetzt unsere Funktionen alle so
schön hier von oben nach unten angeordnet haben und hier sind alle
Wörter über dem Alphabet E angeordnet.
Und jetzt betrachte ich die Diagonale dieser Tabelle.
Ich betrachte mir diese Felder, die hier in der Diagonale stehen.
Also für jede Funktion f, beziehungsweise eine Funktion, die an der i
-ten Position steht, betrachte ich mir das entsprechend i-te Wort und
den Funktionswert, der dort steht.
Und jetzt definiere ich mir eine Funktion von E-Stern nach E-Stern auf
folgende Art und Weise.
Ich nehme mal an, ich habe mindestens zwei verschiedene Elemente in
meiner Menge aller Wörter E-Stern.
Also wenn dieses Alphabet nicht leer ist, habe ich unendlich viele
Wörter.
Ich nehme also einfach zwei verschiedene Wörter her, U und V.
Und ich definiere jetzt einfach folgendes.
Diese Funktion g auf dem i-ten Wort, ich gehe also hier an meine
Tabelle, schaue mir an, was dort drin steht in der i-ten Spalte.
Und ich sage, diese Funktion g, die bekommt den Wert u, falls die i-te
Funktion, also das Element in der Diagonalen, gerade nicht gleich u
ist.
Und ich sage, diese Funktion g bekommt den Wert v für das Argument wi,
wenn an der Position auf der Diagonalen, also für die i-te Funktion,
für das i-te Wort, genau das u als Ergebnis hatte.
Das heißt, diese Funktion g ist an jeder Diagonalen unterschiedlich
von dem Wort, was an einer jeweiligen Diagonal-Element steht.
Und das heißt, was wir gleich sehen werden, es wird zu einem
Widerspruch kommen können, zunächst einmal ist es so, wir hatten
angenommen, dass f, die Menge aller Funktionen von e-Stern nach e
-Stern, sei abzählbar.
Wenn die Menge abzählbar ist, muss ja das g auch irgendeine Funktion
sein in dieser Menge der abzählbaren Funktionen, muss also auch
irgendeine Zahl haben, die dieser Funktion zugeordnet wurde.
Das war der Begriff von Abzählbarkeit.
Ich kann die Menge injektiv abbilden in die Menge der natürlichen
Zahlen.
Dann gibt es ein solches k, das ich als Index habe für diese Funktion
g, das ist also irgendein fk.
Also ist insbesondere für das k-te Wort in meiner Reihenfolge der
Wörter g von wk gleich fk von wk.
Nach Definition hier ist aber g von wk ungleich fk von wk, weil ja,
wenn das fk von wk gleich u ist, ist das g von wk gleich v.
Und andersrum, wenn es gleich u ist, ist es v, wenn es ungleich u ist,
ist es u.
Also sofern immer ungleich zu dem fk von wk.
Das heißt, irgendwas war hier falsch.
Unsere Annahme, dass diese Funktion, die wir über die Diagonalelemente
definiert haben, und zwar so, dass diese Funktion sich von allen
Einträgen in der Diagonale gerade unterscheidet, heißt, diese Funktion
kann nicht in der Liste aller Funktionen drinstehen.
Das heißt, die Annahme, dass die Menge der Funktionen abzählbar ist,
ist falsch gewesen.
Kommt also nicht in f vor, das ist ein Widerspruch.
Die Menge aller Funktionen kann nicht abzählbar sein.
Der andere Teil, dass die berechenbaren Funktionen gerade eine
abzählbare Menge von Funktionen beschreiben, ist klar.
Jeder berechenbare Funktion ist durch einen Algorithmus beschrieben,
der ist durch einen endlichen Text beschrieben.
Ich kann diese endlichen Texte entsprechend ihrer Länge anordnen und
habe damit eine Abbildung auf natürliche Zahlen.
Je zwei verschiedene Texte haben auch unterschiedliche Zahlen, denen
ich die dann zuordnen kann.
Das heißt, die Menge aller Texte, die berechenbare Funktionen
beschreiben, sind abzählbar.
Damit sind die berechenbaren Funktionen abzählbar.
Indjektiv abbildbar in die Menge der natürlichen Zahlen.
Also berechenbare Funktionen kann ich abzählen, sind abzählbar.
Und die beliebigen Funktionen sind es eben leider nicht, das sind
überabzählbar viele.
Und damit kommen wir jetzt noch zu einem weiteren Begriff.
Das eine ist, dass wir überhaupt Funktionen haben, die wir, oder dass
wir sagen, wir können etwas prinzipiell abbilden.
Wir wollen aber eigentlich etwas algorithmisch machen können.
Jetzt kommt der nächste Begriff der Entscheidbarkeit.
Also, wir haben wieder zwei Mengen, in diesem Fall haben wir also
unser E, E-Stern, Menge aller Wörter.
Da drin eine Menge M1 und da drin eine Menge M2.
Eine Teilmenge von M1.
Und jetzt sagen wir, dass das M1 entscheidbar ist, relativ zu M2, wenn
ich einen Algorithmus angeben kann, der mir für jedes Element von M2
feststellt, ob W aus M1 ist oder nicht.
Sie erinnern sich, wir hatten das Wortproblem, das ist so ein
typisches Problem.
Wir wollen feststellen, gehört ein bestimmtes Wort zu einer Sprache
oder gehört eine bestimmte endliche Menge von Wörtern zu einer
bestimmten Sprache.
Das ist genau so ein Problem und da wollen wir ein endliches Verfahren
für haben.
So ein Verfahren, das genau das liefert, ist ein
Entscheidungsverfahren.
Es liefert uns die Antwort, ist das Element drin oder ist es nicht
drin.
Entschuldigung, ich habe mich gerade in den beiden Indizierungen
vertan.
M1 ist enthalten in M2.
Das hier ist M1, das ist M2, das andere wäre ja Unsinn.
Also M1, diese Menge hier, ist entscheidbar relativ zu M2, wenn ich
für jedes Element W feststellen kann, ob es in M1 liegt, in dieser
Teilmenge, oder ob es nicht in der Teilmenge liegt.
Und für das Wortproblem, bei dem Wortproblem, das wir betrachtet
hatten, da war M1, das ist die kleinere Menge, immer irgendeine
Sprache und das M2, die größere Menge, das war immer das ganze E
-Stern.
So hatten wir dort das Wortproblem formuliert, ob ein Wort zu der
Sprache L gehört oder nicht.
Also M1 ist enthalten in M2 und das Ganze in E-Stern.
Und das Ganze, wenn also das M relativ zu E-Stern entscheidbar ist,
dann sagt man, das ist absolut entscheidbar.
Okay, das ist also dann Entscheidbarkeit.
Ich kann eine Antwort Ja oder Nein geben.
Wenn man das so macht, können Sie sich vorstellen, es wird auch Fälle
geben, wo man etwas nicht entscheiden kann.
Und es gibt noch einen weiteren Begriff, nämlich den Begriff der
charakteristischen Funktion, den kennen Sie auch aus der Mathematik.
Die charakteristische Funktion, hier als Chi, Chi für Charakteristik,
M1, M2, soll also gerade eine Menge M2, für jedes Element aus M2
feststellen, gehört ein Element von M2 zu der Menge M1?
Liegt das da drin oder liegt es außerhalb von M2?
Also dieses Chi M1 M2 von einem Wort aus M2 ist wahr, falls das Wort
aus M1 ist in dieser Teilmenge, oder ist falsch, wenn das Wort nicht
da drin ist.
Das ist die charakteristische Funktion.
Man kann jetzt sagen, eine Menge ist entscheidbar, relativ zu einer
anderen, wenn die entsprechende charakteristische Funktion berechenbar
ist.
Bei der Entscheidbarkeit reden wir von einem Algorithmus, bei der
charakteristischen Funktion reden wir von einer berechenbaren
Funktion.
Sie haben sehr viel mit, das ist einfach nur eine äquivalente
Formulierung des gleichen prinzipiellen Begriffs.
Entscheidbarkeit, Berechenbarkeit hat was zu tun mit Algorithmus und
berechenbarer Funktion.
So, jetzt haben wir also diese Entscheidbarkeit in Bezug gesetzt zu
der Berechenbarkeit einer Funktion.
Beispiel, die Menge aller Primzahlen ist entscheidbar relativ zur
Menge aller natürlichen Zahlen.
Ich kann für jede natürliche Zahl feststellen, ob sie eine Primzahl
ist oder nicht.
Ich muss nur testen, ob es einen Teiler gibt, denn Ungleich 1 ist.
Jede endliche Menge ist entscheidbar.
Wenn ich eine endliche Teilmenge betrachte, die ist entscheidbar.
Ich muss nur eine endliche Menge durchsuchen.
Wenn ich mir irgendein Wort hernehme aus der Obermenge, brauche ich
nur zu sehen, ist dieses Wort oder dieses Element in der endlichen
Menge drin oder nicht.
Das ist endliche Zeit, gar kein Problem.
Wenn ich feststellen möchte, ob jede endliche Sprache durch eine
kontextfreie Grammatik erzeugt werden kann.
Also alle endlichen Sprachen, wissen wir, alle endlichen Mengen, sind
sogar reguläre Sprachen.
Sprachen, die durch Typ-3-Grammatiken erzeugt werden können.
Also sicherlich ist das M1 entscheidbar bis zu M2.
Ich kann für eine Sprache feststellen, die sind sehr ähnlich wie das,
was hier oben steht.
Jede endliche Menge ist entscheidbar, jede endliche Sprache natürlich
auch.
Das waren kurze Beispiele dazu.
Jetzt kommen wir zum nächsten Begriff.
Wir hatten abzählbar, wir hatten entscheidbar, überabzählbar, noch
nicht entscheidbar, ist klar, das ist eine Funktion, mit der das nicht
so geht.
Jetzt kommt noch ein nächster Begriff, das ist die Aufzählbarkeit.
Was ist das denn?
Aufzählbar ist eine Menge, wenn ich zu jeder natürlichen Zahl ein
Element, also angeben kann, ein Element dieser Menge M.
Und wenn ich dabei alle Elemente der Menge M tatsächlich erwische.
Das heißt, ich kann alle diese Elemente aufzählen.
Ich kann also F von 0 angeben, F von 1, F von 2.
Das heißt, ich habe die Zahlen 0, 1, 2, 3, 4 und so weiter.
Wenn ich die Menge der Wörter über dem Alphabet aufzählen möchte,
schreibe ich hier Lambda hin, da schreibe ich jetzt alle über einem
Alphabet, mit nur 0 und 1 drin, dann schreibe ich hier 0 hin, da
schreibe ich 1 hin, da schreibe ich 00 hin, da schreibe ich 01 hin, da
schreibe ich dann 10 hin, da schreibe ich 11 hin und so weiter.
Ich kann sie tatsächlich aufzählen.
Ich kann zu jeder Position in dieser Aufzählung sagen, da gehört
dieses Wort hin.
Und wenn ich mir dann anschaue, welche Wörter oder welche Elemente ich
aufgezählt habe, ist das genau die ganze Menge M, die ich aufzählen
wollte.
Also, das ist aufzählbar und zwar durch eine berechenbare Funktion.
Das ist wichtig.
Ich brauche nur endliche Zeit, um für jede Position zu sagen, welches
Wort oder welches Element gehört an diese Position.
Es gibt ein paar sofortige Begriffe, die man sich dann überlegt.
Wenn das M aufzählbar ist, dann ist das M auch abzählbar.
Also, aufzählbar heißt ja nur, dass es berechenbar ist und dass ich
von den natürlichen Zahlen eine sujektive Abbildung auf das M finde.
Dann gibt es eine Umkehrung dieser Funktion, die dann injektiv ist.
Also, das ist einfach zu machen.
Umgekehrt muss es natürlich nicht gelten.
Denn es kann abzählbare Mengen geben, die nicht rekursiv aufzählbar
sind, bei denen ich also diese Abbildung nicht berechnen kann.
Und das M ist entscheidbar.
Entscheidbar hieß, in endlicher Zeit kann ich angeben, ob ein Element
drin ist in der Sprache oder nicht drin ist.
Wieso ist das bei B der Fall, dass ich sagen kann, die Menge ist
entscheidbar, wenn die Mengen M und E-Stern minus M aufzählbar sind?
Also, ich habe hier meinen E-Stern.
Ich habe hier meine Menge M da drin.
Wenn die beide aufzählbar sind, was mache ich dann?
Aufzählbar heißt das hier.
So, M kann ich aufzählen, steht ja da oben.
Und das E-Stern minus M kann ich also auch aufzählen, das steht hier.
M und E-Stern minus M aufzählbar.
Dann heißt das, ich kann auch das, da habe ich irgendeine Funktion G
und ich kann hier hinschreiben, G von 0, G von 1, G von 2 und so
weiter.
Wenn ich jetzt irgendein Element aus M mir hernehme, also irgendein W
aus M und ich möchte wissen, ne Quatsch, W aus E-Stern, und ich möchte
wissen, gehört dieses W zu M oder nicht, dann brauche ich ja nur zu
schauen, ich habe die Aufzählung von E-Stern minus M und die
Aufzählung von M.
Ich gehe die einfach der Reihe nach durch, und zwar beide parallel.
Ich schaue mir G von 0 an, F von 0, G von 1, F von 1, G von 2, F von
2.
Und wenn das W, da das beides aufgezählt wird, das W ist aus E-Stern,
das ist also entweder in M oder in E-Stern minus M, das taucht
irgendwann auf.
Das heißt, wenn W aus M ist, dann folgt, es gibt ein K, sodass F von K
gleich W ist.
Ist W nicht aus M, dann folgt, es gibt ein R, sodass G von R gleich W
ist.
Das heißt, ich habe genau die Möglichkeit, die beiden Aufzählungen mir
anzuschauen.
Das ist ein abbrechendes Verfahren.
Bei einer der beiden Aufzählungen wird das W vorkommen, und damit habe
ich dann die Möglichkeit zu entscheiden, ob das Wort zu M gehört oder
nicht zu M gehört.
Wenn das nur in einer Richtung möglich wäre, die Aufzählung zu machen,
wenn das Element aus M ist, würde ich es in der Aufzählung von M
entdecken.
Wenn aber nur M aufzählbar wäre und E-Stern minus M nicht, hätte ich
keine Möglichkeit festzustellen, dass es nicht vorkommt in dieser
Aufzählung von M.
Damit habe ich diese Struktur meiner Potenzmenge von E-Stern.
Ich habe die entscheidbaren Mengen.
Ich habe die aufzählbaren Mengen.
Also entscheidbar hatten wir gerade gesehen, ist äquivalent dazu, dass
ich die Menge und ihr Komplement aufzählen kann.
Mengen, die nur aufzählbar sind, das sind mehr.
Und dann gibt es diejenigen, bei denen ich diese Funktion nicht
berechnen kann, das sind die abzählbaren Mengen.
Noch eine allgemeinere Sache.
Sie finden für diese Begriffe manchmal auch äquivalent die Begriffe
entscheidbar und rekursiv.
Oder Sie finden die Aufzählbarkeit und die rekursive Aufzählbarkeit
oder auch die Semi-Entscheidbarkeit.
Der Begriff Semi-Entscheidbar ist sofort klar, warum man den wählt.
Das hatten wir gerade gesehen.
Entscheidbarkeit heißt, Menge und Komplement sind aufzählbar.
Deswegen ist allein die Aufzählbarkeit einer Menge die Hälfte des
Entscheidungsproblems.
Deswegen sagt man, das ist die Semi-Entscheidbarkeit.
Wenn das Element drin ist in der Menge, kann ich es feststellen.
Wenn es nicht drin ist, habe ich keine Gewähr, dass ich das
feststellen kann.
Also das ist die Struktur der Potenzmenge von E-STERN.
Und jetzt kommen wir als nächstes endlich mal zu einem formalen Modell
für eine Berechenbarkeit.
Wir können nämlich sagen, welche Funktionen lassen sich denn durch ein
formales Modell berechnen, das wir schon kennengelernt haben, nämlich
durch die Turing-Maschinen.
Das heißt, wir wollen sehen, unsere Turing-Maschine, die einen Zustand
haben kann, irgendeinen Zustand, irgendwas auf dem Band macht, welche
Funktionen sind dadurch in endlicher Zeit berechenbar.
Turing-Maschinen sind ein formales Modell, kann ich auf endlichem Text
aufschreiben, offensichtlich ist das eine Präzisierung des Begriffs
der Berechenbarkeit, wenn wir von Turing-Berechenbarkeit reden.
Da muss man sich aber überlegen, ob das tatsächlich alle berechenbaren
Funktionen einschließt.
Und das werden wir uns dann nächstes Mal genauer anschauen.
Also der Begriff formal definiert ist so, dass wir eine Turing
-Maschine beschreiben oder gegeben haben, zwei Mengen, M1 und M2.
Und wir sagen, dass die Turing-Maschine die Funktion f berechnet, die
Funktion f von M1 nach M2, wenn wir für jedes eingegebene Wort w aus
M1 nach endlich vielen Schritten auf eine Konfiguration kommen, bei
der wir in einem Endzustand landen und die Bandinschrift in dem Fall
ist gerade das Ergebnis v.
Also v ist f von w, der Funktionswert für das Argument w.
Und wir können von dieser Konfiguration kommen zu einer Situation, wo
auf dem Band anschließend das Wort v steht.
Und irgendwo ist unser Schreiblesekopf.
Wenn das möglich ist, sagen wir, die Turing-Maschine berechnet genau
die Funktion.
Wir hatten ein einfaches Beispiel bereits gesehen, wo wir aus einer
Zahl eine um 1 höhere Zahl gemacht hatten.
Also diese Funktion war offensichtlich berechenbar durch eine Turing
-Maschine.
Es stand anschließend eine um 1 größere Zahl drauf.
Dann berechnet die Turing-Maschine eine Funktion f.
Und eine Funktion heißt also dann Turing berechenbar, wenn es eine
Turing -Maschine gibt, die genau diese Funktion berechnet.
Und damit sind wir am Ende dieser formalen Definition.
Nächstes Mal haben wir dann hier nochmal ein Beispiel zur Erinnerung
für bestimmte berechenbare Funktionen.
Und dann kommt dann die Anwendung aller dieser Begriffe, die ich Ihnen
heute eingeführt habe.
Nächstes Mal Vorlesung, also erst am nächsten Mittwoch.
Nächste Veranstaltung am nächsten Montag.
Und zwar ist dann die Saalübung am gleichen Ort wie sonst auch immer.
Vielen Dank für die Aufmerksamkeit, das war es für heute.