So, schönen guten Tag.
Ich begrüße Sie zu einer weiteren Veranstaltung im Bereich Grundlage
der Informatik.
Wir sind im Teil Formale Modelle der Informatik.
Kapitel 4 haben wir letztes Mal angeschaut.
Wir hatten den Abschnitt über kontextfreie Sprachen beendet.
Ich hatte Ihnen nochmal kurz erzählt, wie das mit dem Tokayanga-Kazami
-Algorithmus ging.
Wir waren dann hier eingestiegen in den Bereich kontextsensitive
Sprachen.
Ich hatte Ihnen hier nochmal kurz wiederholt, dass die
kontextsensitiven Sprachen und die monotonen Grammatiken sehr eng
miteinander zu tun haben.
Wir können also alles, was kontextsensitiv ist, auch monoton machen
und umgekehrt.
Man kann dann noch viel mehr darüber erzählen.
Man könnte dann noch Normalformen von kontextsensitiven Grammatiken
betrachten, bei denen rechts immer maximal zwei Zeichen auftreten.
Aber das ist jetzt nicht so relevant.
Wir hatten gesehen, dass die Sprache A auch in B auch in C gerade
durch eine kontextsensitive Grammatik erzeugt werden kann.
Wir hatten dann natürlich gesehen, dass L2 dadurch explizit eine echte
Teilmenge von L1 ist, weil A auch in B und C konnte ja nicht von
kontextfreien Grammatiken erzeugt werden.
Wir waren dann weitergegangen.
Ich hatte nochmal kurz bemerkt, dass wir jetzt also diese Hierarchie
von Sprachen relativ weit getrieben haben und dass es hier durchaus
noch mehr gibt als nur L3, L2, L1.
Und wir sind deswegen gekommen auf die Turing-Maschinen, ein
Maschinenmodell, das sehr wichtig ist, das allgemeinste
Maschinenmodell, das sich eben von den anderen dadurch unterscheidet,
dass wir hier nochmal ein Band haben, bei dem wir nicht nur lesen
können, sondern auch schreiben und dass wir in beide Richtungen
bewegen können.
Das heißt, wir können beliebig auf Informationen zugreifen, die wir
vorher dort gelesen oder geschrieben haben.
Dadurch deutlich mehr Möglichkeiten, etwas auszudrücken.
Ich hatte gesagt, dass man über Turing-Tafeln diese Turing-Maschinen
definiert.
Im Prinzip ist das ein Überführungsdiagramm, also das, was wir vorher
als Zustandstafel verzeichnet haben bei den endlichen Automaten, ist
eigentlich genau das gleiche.
Aber man nennt es hier halt einfach eine Turing-Tafel nach dem
Erfinder dieses Modells.
Wir hatten dann Beispiele angesehen.
Hier war noch ein Beispiel, wo wir dann auch die
Konfigurationsübergänge betrachtet haben.
Also wir hatten Konfigurationen definiert, bei denen man im
Wesentlichen eben sich merkt, was links vom Schreiblesekopf steht, was
ab dem Schreiblesekopf steht auf dem Band und welchen Zustand man ist.
Diese drei Informationen immer ausgedrückt durch einen Band in Schrift
links, den Zustand und das Wort ab dem Lesekopf.
Dann waren wir entsprechend weitergegangen.
Ich hatte Ihnen noch ein paar mehr Dinge erzählt.
Zum Beispiel hier über die Sprache einer Turing-Maschine.
Wir hatten gesagt, dass eine Turing-Maschine irgendwann vielleicht mal
anhält.
Wenn sie anhält, schauen wir nach, in welchem Zustand ist sie.
Wenn das ein akzeptierender Zustand ist, also ein Endzustand, dann
sagen wir, das zu Anfang eingegebene Wort wurde akzeptiert.
Kann also sein, dass eine Maschine nicht hält, dass sie anhält oder
nicht im Endzustand ist, oder sie kann das Wort gerne nur teilweise
lesen, sie muss überhaupt nicht lesen, kann sofort sagen, sie
akzeptiert einfach alles und das Wort darf natürlich verändert werden.
Das muss man sich einfach überlegen.
Ich darf auf dem Band tatsächlich arbeiten.
Ich habe Ihnen ein paar Beispiele vorgeführt, wo wir hier ein
Beispiel, das war das für A hoch N, B hoch N, C hoch N, also eine
Turing -Maschine, mit der wir tatsächlich die Sprache akzeptieren
können, für die wir eine Grammatik kennen, nämlich kontextsensitive
Grammatik.
Das heißt, mit Turing-Maschinen können wir das machen, was wir mit
Kellerautomaten nicht können.
Wir können halt mehr als nur einfach einmal zählen.
Wir können mehrfach zählen, zum Beispiel.
Dann war die Frage, was passiert, wenn wir eine nichtterministische
Turing -Maschine definieren, bei der wir Mengen von möglichen
Folgezuständen, Bandentschriften und so weiter angeben, für jeden
Zustand und aktuellen Symbol.
Und da hatten wir gesehen, man kann im Prinzip wegen der beliebigen
Länge des Eingabebandes jeweils den Baum der möglichen Konfigurationen
einfach schichtweise nachbilden, einfach alle möglichen Nachfolger für
jede Konfiguration, die auf dem Band steht, dann immer wieder
erzeugen.
Und dabei kommt man halt irgendwann auf eine akzeptierende
Konfiguration, sofern sie da ist.
Wenn es keine solche akzeptierenden Konfigurationen gibt, dann wird
entsprechend dieser Baum immer weiter ausgeführt, sofern er nicht
endlich ist.
Wenn er endlich ist, hört es halt irgendwann auf.
Man kann auf diese Art und Weise das nachbilden, was eine
nichtterministische Turing-Maschine macht, mit einer
deterministischen.
Und deswegen sind die im Prinzip her gleich mächtig, aber sie
unterscheiden sich in ihrer Ausführungszeit.
Diese Simulation heißt natürlich, dass wir diese alle Ebenen
nacheinander simulieren müssen.
Das ist ein exponentieller Aufwand in der Pfadlänge.
Die Pfadlänge gibt ja gerade die Zeit an für die Ausführung einer
Berechnung unter diesen vielen nichtterministischen.
Das heißt, wenn die Pfadlänge n ist, haben wir hier irgendwas 2 hoch n
oder c hoch n, wobei c dann der Verzweigungsgrad wäre, sofern wir
einen vollständigen Baum hätten.
Also im schlechtesten Fall exponentiell höhere Laufzeit.
Das ist ein wesentlicher Punkt, auf den wir noch wieder zurückkommen
werden.
Ich hatte dann noch mal kurz darauf hingewiesen, wie die Automaten
oder die Sprachenhierarchien aussehen im Bezug auf die Automaten.
Und die letzte Folie beim letzten Mal war dann diese hier, auf die ich
jetzt wieder explizit zurückkomme.
Und hier haben wir also erstmal eine Frage.
Schauen wir mal, wer hier eine Frage gestellt hat.
Etwas lauter bitte, aber gerne etwas lauter.
Haben Sie sich gemeldet?
Dürfen Sie sich gerne etwas lauter machen.
Ist es jetzt besser?
Dort hinten vielleicht zu laut sogar.
Sie müssen sich die Ohren zuhalten, wenn Ihnen das zu laut ist.
Ich mache es etwas leiser.
Vielleicht ist es so besser.
Also, wenn es noch nicht laut genug ist, müssen Sie sich melden.
Vielleicht habe ich nicht ordentlich hingeguckt, dass Sie sich
gemeldet hatten.
Aber das kriegen wir schon alles hin.
Okay, dann ist die Frage erledigt.
Und jetzt kommen wir also wieder auf diese Folie zurück.
Eine Turingmaschine mit linearer Bandbeschränkung.
Ich hatte gerade eben erzählt, diese Turingmaschinen sind beliebig
groß im Bezug auf die Länge ihres Eingabebandes.
Und jetzt sage ich eine Turingmaschine mit linearer Bandbeschränkung.
Also, wir haben hier unser Band und sagen auf einmal, ich betrachte
nur eine gewisse Länge dieses Bandes und mehr habe ich nicht zur
Verfügung.
Das ist ja eine gravierende Einschränkung.
Da kann ich ja sowas wie vorher dieses nicht deterministische
simulieren.
Durch Determinismus kann ich ja damit gar nichts machen.
Aber das ist auch ein anderes Problem.
Wir schauen uns jetzt an, eine Turingmaschine, bei der nur ein
beschränkter Teil des Bandes benutzt werden darf.
Linear in der Länge des Eingabewortes.
Und man modelliert das so, dass man irgendwo ein Begrenzungssymbol
darauf schreibt und man geht davon aus, dass man links nicht über das
Anfangszeichen hinausgehen darf.
Also nur von dem ersten Symbol des eingegebenen Wortes an bis zu
diesem Symbol Dollarzeichen, das ist der zur Verfügung stehende Platz.
Das heißt, unser Wort, das wir bearbeiten, zu Anfang steht irgendwo
hier drauf, vielleicht ist da noch ein bisschen mehr Platz und dann
geht es darum, was können wir mit dem Inhalt machen.
Also, man nennt dann an solch einer Turingmaschine einen linear
beschränkten Automat, der also ein linear beschränktes Eingabe- und
Arbeitsband hat.
Diese Eigenschaften des linear beschränkten Automaten liegen zwischen
den Turingmaschinen und den Kellerautomaten.
Man kann sich aber Folgendes vorstellen.
Ich hatte Ihnen, als ich Ihnen etwas erzählt hatte über
kontextsensitive Sprachen und Grammatiken, hatte ich gesagt, bei den
kontextsensitiven Sprachen oder Grammatiken ist es so, dass wir ja,
sofern wir sehen wollen, ist ein Wort in der Sprache, da hatten wir
gesagt, wir gucken uns einfach alle Wörter ab, die wir ableiten können
aus unserem Startsymbol.
Und natürlich ist das nicht nur eine einfache Folge, sondern es sind
viele Folgen und irgendwann hat man hier irgendein Wort WN.
Und ich schaue mir einfach alle Wörter an bis zu der Länge meines
Wortes W.
Ich habe also ein Wort W, über das ich feststellen will, liegt das in
der Sprache oder nicht.
Und da gucke ich mir einfach alle Wörter an bis zur Länge W.
Und das Ganze kann ich sehr gut machen, weil ich ja weiß, bei
kontextsensitiven Grammatiken, da habe ich niemals rechts kürzere
Wörter als links.
Das heißt, die Länge der Wörter, die ist nicht fallend.
Wenn das so ist, dann heißt das, wenn ich rückwärts gehe, wenn ich
also von dem Wort WN hier anfange oder von dem Wort W anfange und mich
jetzt nach hinten bewege, wieder in Richtung auf den Anfang zu der
Ableitung, dann werden die Wörter, die ich erzeugen müsste, niemals
länger.
Einfach gedacht, könnte ich also einfach mein Wort W, da steht er zu
Anfang auf dem Band, jetzt könnte ich ja einfach, nicht
deterministisch, alle möglichen Ersetzungen, wenn ich also
irgendwelche Regeln habe, V kann auf C abgeleitet werden, die einfach
rückwärts durchführen.
Ich suche mir irgendeine rechte Seite, die in meiner Grammatik
auftaucht.
Ich darf die durch eine linke Seite ersetzen auf dem Rückwärtsweg.
Wenn das Wort in der Sprache ist, gibt es eine solche Folge von
Rückwärtsersetzungen, die zum Startsymbol irgendwann führt.
Und wir wissen, auf dem Weg dahin wird mein Wort, das auf dem Band
steht, niemals länger werden.
Aber das heißt doch, wenn ich ein Wort einer kontextsensitiven Sprache
hier drauf stehen habe, dann kann ich ja genau auf der Fläche oder auf
dem Platz, den ich für die Eingabe des Wortes brauchte, all das
nachbilden, was ich brauche, um rückwärts zu gehen von dem Wort W
wieder zurück, ob ich zu dem Wort S oder zum Startsymbol S kommen
kann.
Das heißt, mir reicht der Platz aus, den ich habe, um tatsächlich zu
überprüfen, ob das Wort aus der Sprache ist oder nicht.
Mir reicht sogar genau die Länge des Wortes.
Und damit sehen wir eigentlich sofort ein, da ich auf dem Arbeitsband
genau rückwärts die Reduktion seines Wortes bis hin zum Startsymbol
simulieren kann und das Wort niemals länger wird, reicht auf jeden
Fall eine Turing-Maschine mit linearer Bandbeschränkung aus, um alle
Wörter einer kontextsensitiven Sprache zu erkennen.
Das heißt, diese Maschinen sind offensichtlich geeignet als
Automatenmodell für die kontextsensitiven Sprachen.
Und das steht jetzt hier auch genau drin.
Zu jeder Typ-1-Grammatik gibt es einen linearbeschränkten Automaten T
mit L von T gleich L von G und umgekehrt.
Das heißt, die Menge der kontextsensitiven Sprachen ist gleich der
Menge der Sprachen, die durch linearbeschränkte Automaten erzeugt
werden.
Die eine Richtung habe ich gerade eben erklärt, diese Richtung.
Die andere Richtung ist nicht ganz so einfach, denn linearbeschränkter
Automat heißt ja mehr als nur genau das Wort oder der Platz für dieses
Wort steht zur Verfügung.
Bei linearbeschränkten Automaten darf ich sogar einen
linearbeschränkten Anteil nehmen.
Ich darf also auch den doppelten, dreifachen oder fünffachen Platz
nehmen für ein Wort, aber es muss linearbeschränkt bleiben.
Das heißt, ich darf sogar noch mehr.
Und selbst wenn ich also nicht nur genau die Fläche oder den Platz zur
Verfügung habe, für das Wort, das zu Anfang auf dem Band steht, für
meine ganzen Zwischenberechnungen, selbst dann kann ich das durch eine
kontextsensitive Grammatik nachbilden.
Und das, was ich Ihnen gerade eben sagte, war ja auch so, das war sehr
nicht deterministisch und man kann eben auch gucken, geht das alles
deterministisch.
Das ist noch eine andere Frage, auf die ich jetzt nicht weiter
eingehen will.
Also, das ist die Menge aller Sprachen, die durch nicht
deterministische, linearbeschränkte Automaten erkannt werden können.
So hatte ich das gerade eben erklärt.
Ich glaube, diese eine Richtung war deutlich, die andere Richtung, die
habe ich jetzt nicht genauer erläutert.
Wir haben auf jeden Fall damit für alle Sprachklassen der Chomsky
-Hierarchie äquivalente Beschreibungen durch Automaten.
Das heißt, wir haben sowohl erzeugende Beschreibungen, das waren die
Grammatiken, wir haben analysierende Beschreibungen, das sind die
Automaten und für eine Sprachklasse, nämlich die Typ-3-Sprachen, haben
wir auch noch die operationelle Charakterisierung durch die regulären
Ausdrücke.
Das ist also unsere Charakterisierung dieser Sprachen.
Und, achso, hier ist nochmal kurz angegeben, wie man das genau machen
kann.
Das habe ich Ihnen ja schon erläutert.
Deswegen kann ich über diese Folie sehr schnell weitergehen.
Das ist genau der Algorithmus.
Wir reduzieren einfach so lange unser Wort auf dem aktuellen Band, bis
wir tatsächlich irgendwann die Band in Schrift S wieder haben.
Rechts daneben natürlich dieses Symbol Dollar.
Das war die Begrenzung für unsere Länge des Bandes.
Und damit sind wir also in der Lage zu zeigen, wie man aus
kontextsensitiven Grammatiken linear beschränkte Automaten macht.
Das hatte ich Ihnen schon erläutert.
Wir haben damit jetzt zusammenfassend Folgendes gesehen.
Sehr vieles, steht ja alles Mögliche schon mal drin.
Das Einfachste war hier unten die Charakterisierung der Typ-3-Sprachen
durch diese drei verschiedenen Methoden.
Wir haben gesehen, dass es hier bei den Kontextfreien eine wichtige
Teilklasse gibt, die LRK-Grammatiken beziehungsweise deterministischen
Kellerautomaten, mit denen wir darüber zunächst charakterisiert haben.
Die LRK-Grammatiken habe ich nur ganz kurz angedeutet.
Und das Wesentliche war, dass wir bis hierhin in dem Bereich einen
linearen Erkennungsaufwand haben.
Wenn wir rübergehen, haben wir hier noch mal immerhin was
Polynomielles.
Und dann sind wir im exponentiellen Bereich.
Und was dann darüber hinaus passiert bei allgemeinen Grammatiken, das
ist hier noch mal offen gelassen worden.
Wir haben andere Charakterisierungen gefunden.
Wir haben uns die Pumping-Lemmata überlegt, zur Struktur der Sprache,
oder zur Struktur der Wörter.
Wir wissen, dass wir eben bei...
Wenn wir uns das Pumping-Lemma für die regulären Sprachen anschauen,
da hatten wir gesagt, da gibt es immer eine Pumpstelle in solchen
Wörtern.
Wenn wir also eine Sprache haben, bei der wir über solche Pumpstellen,
eine einfache Pumpstelle, immer Wörter erzeugen, die nicht in der
Sprache sind, dann ist es keine L3-Sprache.
Ähnlich war es mit dem Pumping-Lemma für kontextfreie Sprachen.
Da hatten wir aufgrund der Baumstruktur zwei Pumpstellen gefunden und
hatten gesehen, dass wir eben damit auch Sprachen charakterisieren
können, die nicht in L2 sind, sondern in L1 oder oben drüber.
Und wir haben die Automaten-Charakterisierung...
Also wir haben einiges herausgefunden inzwischen.
Wir haben spezielle Sprachen immer gefunden, die genau die
Unterscheidung herstellen zwischen den verschiedenen Bereichen.
Auch in B hoch N die Sprache, die in L2 und nicht in L3 liegt.
Die Sprache der Palindrome, die halt nicht deterministisch erkannt
werden kann, von Kellerautomaten, aber nicht deterministisch.
Wir hatten auch in B hoch NC gesehen als Sprache, die in L1 ist, also
kontextsensitiv, aber eben nicht kontextfrei.
Und jetzt müssen wir sehen, was noch alles folgt.
Wir hatten einige wesentliche Fragen gestellt zu Anfang, in Bezug auf
die Ausdrucksfähigkeit.
Und da haben wir eigentlich die wesentlichen Antworten schon gefunden.
Nämlich, dass Typ 3 nicht reicht, dass Typ 2 reicht, aber dass wir
eben dort die deterministischen Sprachen nehmen müssen, die
deterministischen kontextfreien Sprachen, wegen des
Erkennungsaufwands.
Und alles, was wir ausdrücken müssen, die ganzen Strukturen, die
auftreten in Sprachen, sind in den Typ-2-Sprachen darstellbar, in den
kontextfreien Sprachen.
Ich habe nicht alle möglichen Features angeguckt oder durchdiskutiert.
Ich habe im Wesentlichen diese Klammerstrukturen genommen und habe
gezeigt, dass sobald man solche Dreifachzählungen hat, wie A-Hoch-N, B
-Hoch -N, C-Hoch-N, dass man dann nicht mehr mit Kontextfreien
auskommt.
Das taucht aber so in den Programmiersprachen eigentlich nicht auf.
Also, das war klar, dass die kontextsensitiven Grammatiken auch nicht
infrage kommen, wegen des exponentiellen Erkennungsaufwands.
Es wäre Wahnsinn, wenn man große Programme mit einem solchen Aufwand
überprüfen müsste auf ihre syntaktische Korrektheit.
Das ist also alles, was wir jetzt im Prinzip zu den Sprachen soweit
machen wollten.
Oder was ich Ihnen dazu präsentieren wollte.
Man hätte noch viel mehr tun können, aber dazu ist hier keine Zeit.
Wir kommen damit zu einem wesentlichen anderen oder weiteren Kapitel,
das wir auch noch uns genauer angucken müssen, das mich eigentlich
noch mehr interessiert.
Aber es interessiert mich auf jeden Fall sehr stark, weil dieses Thema
Berechenbarkeit und Komplexität ein Thema ist, das sehr stark meine
Forschung charakterisiert.
Nicht so sehr im Bereich der theoretischen Untersuchungen zu
Berechenbarkeit und Komplexität, sondern mehr im Bezug auf die
konkreten Dinge, die wir mit Rechnern machen können.
Also in diesem Kapitel wollen wir uns fragen, was können wir
prinzipiell mit Rechenanlagen eigentlich bewirken?
Welche Funktionen können wir berechnen?
Und das heißt, was wir uns anschauen müssen ist, womit arbeiten wir
eigentlich im Rechner?
Wir arbeiten mit Algorithmen.
Kennen Sie alles aus Grundlagen der Informatik 1.
Sie wissen, was ein Algorithmus ist.
Nämlich ein endlich beschriebenes Verfahren mit Ein- und Ausgabe, das
für alle zulässigen Eingaben nach endlich vielen Schritten hält.
Es gibt viele Charakterisierungen von Algorithmen.
Man kann auch sagen, ein für alle zulässigen Eingaben terminierendes
Programm endlicher Länge auf einem abstrakten Rechner.
Man könnte auch sagen, eine beliebige Turing-Maschine ist ein
Algorithmus.
Und genau in die Richtung werden wir jetzt weiter vorgehen.
Wir werden uns erstmal anschauen, was die wesentlichen Eigenschaften
nochmal waren.
Wenn wir davon reden, allgemein etwas zu sagen über Algorithmen,
müssen wir etwas wissen, worum es eigentlich geht.
Es darf also insbesondere nicht nur um einen Spezialfall gehen.
Ein Algorithmus, der mir nur Folgen der Länge 27 sortiert mit
bestimmten Inhalten, der ist wertlos.
Ein Algorithmus, ein Verfahren muss immer für eine ganze Problemklasse
anwendbar sein.
Also ein Sortieralgorithmus muss beliebige Folgen sortieren können.
Oder zumindest bei Folgen gleicher Länge beliebige Inhalte solcher
Werte, die dort stehen können.
Also eine größere Klasse von Problemausprägungen, es muss etwas
Allgemeinerbares sein, die generell Wissenschaft nur einen Wert hat,
wenn daraus generalisierbare Erkenntnisse gewonnen werden können.
Dann kommt eine weitere Anforderung, die aber etwas kritisch ist.
Determiniertheit.
Determiniertheit wacht, wenn ich den Algorithmus anwende, meinen
Algorithmus A, den wende ich an auf X, dann kommt da irgendeine Lösung
L raus.
Und wenn ich den Algorithmus A nochmal anwende auf X, dann kommt da
wieder L raus.
Selbstverständlich werden Sie sagen, natürlich, muss ja so sein.
Das ist auch die übliche Forderung.
Also wiederholte Ausführungen des Verfahrens mit gleicher Eingabe
führen zu gleicher Ausgabe.
Es gibt aber Algorithmen, bei denen das nicht so ist.
Wenn Sie würfeln und Sie wollen das Ergebnis haben eines Würfel
-Experiments, das ist ein Algorithmus.
Und Sie wissen, Sie können bei jedem Würfel-Ereignis eine Zahl
zwischen 1 und 6 rausbekommen.
Aber wenn Sie mehrfach den gleichen Würfel werfen, werden Sie
hoffentlich unterschiedliche Ergebnisse kriegen, damit es wirklich ein
idealer Würfel ist, der mit gleicher Wahrscheinlichkeit Ihnen alle
Ergebnisse liefert.
Das heißt, manchmal sind wir daran interessiert, etwas randomisiert zu
machen.
Zufällig.
Manchmal nur innerhalb von Algorithmen, manchmal aber ist es so, dass
wir tatsächlich bei randomisierten Algorithmen auch unterschiedliche
Ergebnisse haben wollen.
Das ganze Gebiet der Metaheuristiken mit Tabu-Search oder mit
evolutionären Algorithmen oder diese ganzen naturspirierten
Algorithmen, simulated annealing und so weiter, da wäre es fatal, wenn
jede Ausführung des Algorithmus immer das gleiche Ergebnis liefern
würde.
Da wollen Sie gerade durch Randomisierung erreichen, dass Sie
möglichst den Suchraum weit ausschöpfen.
Das heißt, es gibt Algorithmen, wo Determiniertheit Unsinn wäre.
Trotzdem in einem gewissen Sinne wollen wir sicher sein, dass wir
immer ein vernünftiges Ergebnis bekommen.
Man muss nur wissen, worüber man an den entsprechenden Stellen redet.
Also wenn ich hier, ich schreibe mir nur das Stichwort auf, EA oder
simulated annealing, das sind so Bereiche, Algorithmen, bei denen man
randomisiert vorgeht und wo halt die Ergebnisse unterschiedlich sein
sollen sogar.
Dann, es gibt übrigens auch Algorithmen, bei denen man nur intern
etwas randomisiert macht, aber das Ergebnis immer determiniert sein
soll, das sind noch wieder andere Dinge.
Auch darüber kann man also eine eigene Vorlesung halten, über
Randomisierung in Algorithmen.
Sehr interessante Dinge, hat man viel erreicht in den letzten Jahren,
hat dadurch sehr effiziente Dinge erreichen können.
Ein typisches Beispiel, wo man sehr viel hat erreichen können, durch
Randomisierung ist der Primzahltest.
Randomisierte Algorithmen sind da wahnsinnig schnell, wenn sie das
deterministisch machen, dauert es sehr lange.
Auch da könnte man einiges zu erzählen, passt aber leider nicht in
diese Vorlesung.
Dann kommt der nächste Begriff, die Endlichkeit.
Wir wollen alles, was wir dort machen, was wir ein Verfahren formal
beschreiben, natürlich auch wirklich hinschreiben können.
Das heißt, die Beschreibung des Verfahrens muss von endlicher Länge
sein.
Ich muss ihnen ein Blatt Papier geben oder ein Stück Stapel Papier
geben können oder ein ganz langes Band und darauf muss der gesamte
Algorithmus stehen.
Dann werde ich eine Folge von Schritten ausführen, das müssen alles
effektive Schritte sein, müssen endlicher Zeit ausführbar sein.
Und der Algorithmus sollte für jede zulässige Eingabe nur endlich
viele Schritte brauchen.
Auch hier muss man ein bisschen genauer hinschauen, es gibt bestimmte
Anwendungen, meinetwegen Betriebssysteme, oder dort tauchen solche
Dinge auf, da erwarten sie, dass das Verfahren nicht endet.
Wenn ihr Algorithmus oder ihr Rechner immer nach endlich vielen
Schritten aufhören würde zu laufen, wären sie nicht zufrieden.
Trotzdem sind die einzelnen Operationen, die dort gemacht werden, alle
in endlich vielen Schritten durchführbar.
Das heißt, man muss genau gucken, worüber man redet.
Also einen Algorithmus brauche ich, um irgendeinen Teilabschnitt in
solch einem Verfahren zu machen.
Terminiertheit ist ein wichtiger Punkt.
War auch bei dem Kapitel über formale Sprachen jetzt genau der Punkt,
dass wir immer sagten, wir wollen nach endlich vielen Schritten
schauen können, was ist das Ergebnis unserer Frage, kann ich ein Wort
erzeugen oder ist ein Wort in der Sprache, kann ich das entsprechend
analysieren, um herauszufinden, ob das Wort entsprechend von der
Grammatik erzeugt werden kann.
Also, das sind diese drei Dinge.
Und jetzt machen wir dazu nochmal ein paar Beispiele.
Hier angegeben, Sortierverfahren, das ist selbstverständlich ein
allgemeines Verfahren, das terminiert immer.
Die sind auch normalerweise determiniert.
Ich habe immer das gleiche sortierte Ergebnis am Ende.
Bei Berechnung kürzester Wege ist es ebenso für beliebige Graphen.
Aber wenn Sie sich anschauen, die realen Algorithmen, Ihre
Navigationssysteme im Fahrzeug, wenn Sie verschiedene
Navigationssysteme haben, da werden die Ergebnisse bezüglich der
kürzesten Wege unterschiedlich aussehen, weil die mit Approximationen
arbeiten.
Die nehmen nicht das gesamte Straßennetz dort mit rein, machen
bestimmte heuristische Annahmen.
Und so hat man auf einmal hier, wenn man in der Realität guckt,
manchmal unterschiedliche Ergebnisse.
Wenn ich aber sage, ich möchte auf jeden Fall kürzeste Wege berechnen,
kann ich das machen.
Für einen beliebigen Graphen auch im Straßennetz und kriegt den
kürzesten Weg raus.
Reduktion endlicher Automaten, wissen Sie auch, ist ein schönes
Verfahren.
Die Transformation kontextfreier Grammatik, Kellerautomaten, haben wir
auch gesehen, wie das funktioniert.
Oder die Syntaxanalyse einer kontextfreien Grammatik, der Kokeyanga
-Kasami -Algorithmus, auch den kennen Sie.
Das war alles kein Problem, das sind schöne Algorithmen.
Randomisierte Algorithmen, hatte ich Ihnen schon gerade eben kurz
angesprochen.
Primzahltest brauchen Sie, wann immer Sie ein Schlüsselpaar erzeugen
wollen für die typischen Public Key Verfahren, also bei denen mit
öffentlichem Schlüssel.
Da brauchen Sie ein paar von öffentlichem und geheimen Schlüssel.
Und das Wesentliche dabei ist eine große Zahl, die das Produkt von
zwei Primzahlen ist, von zwei sehr großen Primzahlen.
Das heißt, Sie müssen hierfür sehr sehr große Zahlen, Zahlen mit
irgendwie mehreren tausend Bit, müssen Sie überprüfen können,
inwieweit solch eine Zahl N irgendwie das Produkt ist von zwei Zahlen
P und Q, das ist ein Faktorisierungsproblem.
Das können Sie deterministisch zum Glück nur in sehr sehr sehr sehr
langer Zeit herausfinden, sehr aufwendig.
Sie könnten es natürlich raten, da könnten Sie Glück haben, aber so
eine Zahl faktorisieren ist sehr aufwendig.
Und Sie müssen, um also solche Zahlen zu erzeugen, wie diese Zahl N,
solche Primzahlen erstmal haben.
Sie suchen sich eine beliebige Zahl und müssen feststellen, ist das
eigentlich eine Primzahl?
Also eine Zahl mit 500 Bit, wollen Sie feststellen, ist das eine
Primzahl?
Und das können Sie halt randomisiert sehr effizient machen.
Das war ein ganz wichtiger Algorithmus und der ist also ganz wichtige
Grundlage dafür, dass man effizient tatsächlich sich die Schlüssel für
Public Key Verfahren erzeugen kann.
Wenn Sie also mit PGP oder so sich selbst einen Schlüssel erzeugen,
dann laufen genau solche Verfahren dort ab.
Evolutionäre Algorithmen, Ameisenalgorithmen, Particles Form
Optimization, alles Themen, die wir in unserer Vorlesung Nature
Inspired Optimization machen.
Eine Vorlesung, die im Augenblick angeboten wird von Frau Mostergiem
und Herrn Schukler.
Da tauchen solche Verfahren auf, aber auch in anderen Bereichen, auch
im Operations Research, werden solche Verfahren behandelt.
In Liegeling natürlich auch, das kennen Sie vielleicht aus dem
Operations Research.
Also nochmal zu den Algorithmen, das waren alles bisher
Beschreibungen, die waren nicht formal.
Ich habe gesagt, naja, man beschreibt das so, endliches Verfahren und
so weiter.
Hier steht also nur eine Problemklasse ist uns gegeben, das ist die
Menge aller Problemausprägungen, Probleminstanzen.
L, die Menge der Lösungen zu den Problemen aus dieser allgemeinen
Klasse, also A soll hier stehen für allgemeine Problemklasse.
Und jetzt brauchen wir einen Algorithmus AP zu der Klasse.
Das ist ein allgemeines Verfahren, welches auf richtige Anfangsdaten A
aus A angewendet, also A aus A.
Was ist denn ein kleiner A aus Groß A?
Die Menge konkreter Problemausprägungen, das heißt, das ist jeweils
ein kleines A.
Jede Problemausprägung beim Sortierproblem, jede zu sortierende Liste
ist eine solche Problemausprägung.
Und das allgemeine Problem ist halt das Sortierproblem.
Nach endlich vielen elementaren Schritten hält und die Lösung L aus L
liefert.
Sehr intuitiv aufgeschrieben.
Und das heißt, wir sagen jetzt einfach AP bildet jedes Element aus
dieser Problemklasse A ab auf die entsprechende Lösung.
Insofern ist das eine Art Funktion.
Sofern das determiniert ist, ist es eine Funktion, ansonsten wird das
nur eine Relation.
Ist aber keine präzise Definition.
Wie kann ich das präzisieren?
Das war die Frage, die sich Church und Turing zum Beispiel gestellt
haben in den 30er Jahren.
Eine Möglichkeit ist halt, genau das mit einem Modell zu machen.
Nämlich mit der Turing-Maschine, darauf kommen wir noch etwas später
wieder zurück.
Was uns interessiert ist also, was kann ich...
Das eine waren die Probleme, die ich lösen möchte.
Und jetzt sage ich, ich möchte im Rechner ja auch etwas rechnen, ich
möchte Funktionen ausführen.
Ich möchte, wenn ich hier mein Anfangsband anschaue bei einer Turing
-Maschine, irgendein Wort, das hier gegeben ist, überführen irgendwie
in eine Inschrift, die etwas anders aussieht.
Meinetwegen V.
Und das soll das Ergebnis sein, die Anwendung einer Funktion F.
Das heißt, ich möchte im Prinzip für irgendeine Teilmenge von Wörtern
über meinem Eingabealphabet irgendeine Funktion berechnen, die mir
also angesetzt auf ein Wort W, ein Wort V liefert.
Das ist also jetzt die Frage, kann ich das machen mit einem
Algorithmus.
Also so eine Funktion wäre berechenbar.
Wenn es einen Algorithmus gibt, der jedes Element aus der
Problemklasse M1 geeignet zu einer Lösung führt.
Die Lösung wäre das entsprechende Element aus M2.
Also AF von W gleich F von W für alle W aus M1.
Das wäre dann eine berechenbare Funktion.
Das heißt, eine Funktion ist dann berechenbar, wenn ich zu F einen
Algorithmus AF finden kann.
Beispiel.
Ich habe die Menge der Dezimalziffern 0 bis 9 und eine Sprache, die
folgendermaßen aussieht.
Da ist die 0 drin und alle Wörter, die mit Ziffern 1 bis 9 anfangen
und danach irgendwelche weiteren Ziffern haben.
Das hier ist eine Abbildung.
Das sind beliebige Teilmengen von Estern.
Hier ist es so, dass ich diese Wörter natürlich schreiben kann auf das
Band.
Ich kann sogar eine objektive Abbildung angeben, die mir jedes Wort
dieser Sprache abbildet auf N0.
N0 ist nun eine andere.
Ich kann also jedes Wort auf diese Art und Weise mit natürlichen
Zahlen identifizieren.
Kann ich objektiv abbilden und es ist klar, wie man das macht.
Man interpretiert halt einfach irgend so eine Folge 1, 0, 3, 7.
Eine Folge von Digitalziffern als eine natürliche Zahl.
Wie man das macht, wissen Sie.
Stellenwert, Geschichten und ähnliches.
7 plus 3 mal 10 plus 0 mal 100 plus 1 mal 1000.
Das ist dann genau die Zahl 1037.
Auf die Art und Weise kann man also daraus Zahlen machen.
Und berechenbare Funktionen jetzt auf der Menge natürlicher Zahlen,
die ich jetzt jeweils, hier steht jetzt jeweils N0.
Ich stelle also die Zahlen aus N0 dar durch solche Folgen von Ziffern.
Und jetzt kann ich mir anschauen, welche Funktionen berechenbar sind.
Zum Beispiel die Funktion, die mir gerade die nächstgrößere Zahl
liefert.
Von N auf N plus 1.
Da hatten wir uns sogar einen Algorithmus angeschaut, das war der
Algorithmus mit einer Turing-Maschine, um eine Zahl um 1 zu erhöhen.
Den hatte ich Ihnen schon gezeigt.
Und zwar auf einer Binärdarstellung.
Da hatten wir nicht die Darstellung über Nullen bis beliebige
Dezimalziffern, da hatten wir nur Binärziffern genommen.
Dann kann ich mir einen Algorithmus überlegen, der irgendeine
beliebige natürliche Zahl als Eingabe bekommt und der soll mir
liefern, ja oder nein.
Und zwar ja, wenn das N eine Primzahl ist und nein, wenn es keine
Primzahl ist.
Da hatte ich gerade eben etwas darüber erwähnt, dass man das
unterschiedlich machen kann.
Offensichtlich kann man das berechnen.
Man braucht ja nur zu sehen, ob irgendeine kleinere Zahl ein Teiler
dieser Zahl ist.
Oder ich möchte gerne für zwei Zahlen feststellen, was der größte
gemeinsame Teiler ist.
Also, die GT-Funktion, auch das wäre eine Funktion, bei der wir
wissen, wie das geht, können wir also problemlos machen.
Gibt es einfache Verfahren für, der Algorithmus ist Ihnen lange
bekannt.
Wie ich also den größten gemeinsamen Teiler von zwei Zahlen finde,
über den Euclidischen Algorithmus.
Dann weiß ich etwas über Berechenbarkeit.
Ich möchte darauf kommen, dass wir irgendwann zu einem formalen Modell
kommen für berechenbare Funktionen.
Zunächst mal mache ich aber noch ein bisschen auf diesem intuitiven
Begriff weiter.
Und wir stellen uns ein paar Fragen.
Eine Frage ist, ob jede Funktion von N nach N berechenbar ist.
Also jede Funktion auf natürlichen Zahlen, die wieder eine natürliche
Zahl liefert, ist die berechenbar?
Und das schauen wir uns gleich an.
Dazu muss ich Ihnen aber noch einen Begriff formulieren, den Sie noch
nicht kennen.
Vielleicht nicht kennen, vielleicht haben Sie den in der Mathematik
schon mal kennengelernt.
Ich möchte mir anschauen einen Begriff, der etwas zu tun hat mit
abzählbar und überabzählbar.
Ich nenne eine Menge M abzählbar, wenn M injektiv in N abbildbar ist.
Also ich habe hier meine Menge M und hier habe ich meine natürlichen
Zahlen.
1, 2, 3, 4, 5, 6 und so weiter.
Ich möchte mir irgendein Element hier hernehmen und das abbilden auf
irgendeine Zahl.
Anderes Element, auch abbilden auf irgendeine Zahl.
Noch ein Element, auch abbilden auf irgendeine Zahl.
Die Anforderung ist, ich kann M injektiv in N abbilden.
Sodass also keine zwei Elemente von M auf die gleiche Zahl abgebildet
werden.
Also, nehmen wir jetzt folgende Menge her, zum Beispiel diese Menge.
Die Menge, die nur ein Element enthält.
Da werden Sie mir sofort viele Abbildungen nennen können, mit denen
ich dieses Element abbilden kann.
Zum Beispiel A auf 1.
Fertig.
Abzählbar.
Ich nehme die Menge 1, 2, 3 bis 10.
Auch die kann ich problemlos abbilden, die Menge natürlich in Zahlen.
Für eine identische Abbildung.
Injektiv ganz leicht zu machen.
Ich nehme die Menge E-Stern.
Die Menge aller Wörter über dem Alphabet E.
Dann nehme ich das leere Wort Lambda.
Nehmen wir mal an, dass E ist 0,1.
Nehmen wir an, dass wäre die Menge 0,1.
Dann würden wir hier 0 hinschreiben, wir würden 1 hinschreiben, wir
würden 0,0 hinschreiben, wir würden 0,1 hinschreiben, 1,0, 1,1 und so
weiter.
Dann vielleicht 0,0,0.
Das können wir ja daran gehen, einfach in der Folge.
Sie sehen, ich habe das ganz systematisch aufgeschrieben.
Immer Wörter wachsender Länge und innerhalb der Wörter gleicher Länge,
so eine lexikografische Ordnung.
Das kann ich ja ganz systematisch aufschreiben.
Da habe ich eine Folge von Wörtern.
Und jetzt kann ich natürlich einfach sagen, das ist die erste
Position, die zweite, die dritte, die vierte, die fünfte, die sechste
und so weiter.
Ich kann doch jedem Wort hier drin, entsprechend der Position in
dieser Folge, eine Zahl zuordnen.
Also das geht offensichtlich.
Es muss ja nur injektiv sein.
Wenn das nicht geht, dann ist das M überabzählbar.
Wenn ich also nicht eine solche Abbildung angeben kann, sodass ich
jedem Element der Menge eine andere natürliche Zahl zuordne, dann ist
das überabzählbar.
Ich habe doch unendlich viele Zahlen.
Da kann ich auch jede Menge reinschreiben, gar kein Problem.
Sie werden sehen, das ist nicht so einfach.
Abzählbare Mengen.
Jede endliche Menge habe ich Ihnen gerade eben angedeutet.
Oder A-Stern für ein endliches Alphabet habe ich Ihnen auch gerade
angedeutet.
Und überabzählbare Mengen.
Zum Beispiel die Menge aller reellen Zahlen zwischen 0 und 1.
Nicht abzählbar.
Kann man beweisen über Diagonalisierung.
Jetzt wissen Sie gar nicht, was Diagonalisierung ist.
Ich werde Ihnen gleich einen Diagonalisierungsbeweis vorführen.
Bei dem Sie sehen, was man da macht.
Potenzmenge von A-Stern.
Also wenn ich alle Sprachen betrachte, über einem Alphabet, dann bin
ich überabzählbar.
Ebenfalls durch Diagonalisierung.
Auch das könnte ich Ihnen explizit vorführen.
Ich will aber diese Frage hier genau anschauen gleich.
Ich will dazu kommen, dass nicht jede Funktion berechenbar sein kann.
Und das geht genau darüber, werden Sie gleich sehen, dass wir einsehen
werden, die berechenbaren Funktionen sind eine abzählbare Menge,
während die Funktionen insgesamt von N nach N eine überabzählbare
Menge sind.
Also, der Satz, den ich Ihnen jetzt zeigen möchte, oder Ihnen
darstellen möchte, oder erläutern möchte, oder verständlich machen
möchte, ist, dass für ein Alphabet E die Menge aller Funktionen F von
E -Stern nach E-Stern überabzählbar ist.
Und das zweite, die Menge aller berechenbaren Funktionen nur abzählbar
sein kann.
Das heißt, nur eine kleine Teilmenge, klein in Anführungszeichen,
immer noch unendlich groß, von Funktionen über E-Stern ist
berechenbar.
Insbesondere heißt das, nicht jede Funktion ist berechenbar.
Es gibt sehr, sehr viele nicht berechenbare Funktionen.
Das heißt, wir müssen genauer gucken, wenn ich Ihnen eine Aufgabe
gebe, dann sollten Sie schon wissen, naja, das werden alles
berechenbare Probleme sein, oder entscheidbare Probleme, bei denen man
tatsächlich eine Lösung in endlicher Zeit erzeugen kann.
Deswegen ist das wichtig.
Oder wenn Sie ein Problem bekommen und Sie wissen, Sie bewerben sich
um irgendeine Ausschreibung, tolle Aufgabe ist ausgeschrieben, gibt es
viel Geld für, wenn Sie da feststellen, da ist aber ein Problem drin,
das ist gar nicht in der Form berechenbar, dann sollten Sie kein
Angebot abgeben.
Weil Sie dann die Aufgabe gar nicht erfüllen können.
Also Sie müssen schon wissen, wie man sowas charakterisieren kann.
Und das ist nicht etwas, was nur irgendwo esoterisch ein Problem ist,
was nie in der Praxis auftaucht.
Schauen wir uns das Beispiel an, das wir betrachten wollen.
Wir betrachten diese Tabelle, wir wollen zeigen, die Menge der
Funktionen von E-Stern nach E-Stern ist überabzählbar.
Dann nehmen wir einfach an, das Ganze wäre abzählbar.
Das heißt, wir betrachten diese Tabelle, bei der wir, das kommt jetzt
gleich, also erst mal folgendes machen, wir schreiben einfach alle
Wörter hin über dem Alphabet E.
Also das ist hier unser gesamtes E-Stern.
Ich schreibe alle Wörter hin, ich habe Ihnen gerade erläutert, wie das
funktioniert.
Ich kann die ja einfach der Reihe nach aufschreiben und wenn ich
irgendein Wort habe, von dem ich wissen will, welche Nummer hat das
eigentlich, dann brauche ich ja nur der Reihe nach durchzulaufen, alle
Wörter bis zu der Länge anzugucken, die alle durchzählen, habe dann
die Nummer für dieses Wort.
Das ist also, offensichtlich ist sowas machbar.
Und jetzt nehme ich einfach an, ich kann ja einfach auflisten, alle
Funktionen.
Ich nehme an, ich habe eine abzählbare Menge von Funktionen.
Wenn die abzählbar sind, dann kann ich F1, F2, F3 usw.
irgendwie hinschreiben.
Wenn ich diese Abbildung habe, in die Menge der natürlichen Zahlen,
dann kann ich doch genau solche Funktionen F1, F2, F3, der Reihe nach
hinschreiben.
Und jetzt definiere ich eine weitere Funktion.
Ich definiere eine Funktion G von E-Stern nach E-Stern auf folgende
Art und Weise.
Und jetzt kommt der Diagonalisierungsansatz.
Betrachte nämlich gerade die Elemente auf der Diagonalen.
Und so weiter.
Inwiefern betrachte ich die?
Ich schaue mir an, das i-te Wort WI, beziehungsweise irgendein Wort W
aus meinem E-Stern, hat irgendeine Nummer, meinetwegen I.
Jetzt schaue ich mir an, wie ist G auf diesem WI definiert.
Dieses G auf WI ist gleich U, wobei U irgendein Wort aus der Sprache E
-Stern ist, falls das FI von WI, also der entsprechende Eintrag auf
der Diagonalen, mit dem Index I, ungleich U ist.
Ich kann ja nachschauen, diese ganzen Felder hier in der Diagonalen,
wie die aussehen.
Ich nehme irgendein Wort W, das hat einen Index I.
Schaue ich nach, das fällt I, I.
Da steht drin das Wort FI von WI.
Wenn das ungleich U ist, dann sage ich das G.
Das soll aber jetzt genau den Wert U haben.
Damit ist G also unterschiedlich von FI.
Und wenn das FI von WI gleich U ist, dann nehme ich einfach ein
anderes Wort.
Und ich nehme an, es gibt mindestens zwei unterschiedliche Wörter in E
-Stern.
Mehr brauche ich dafür nicht.
Jetzt weiß ich, G ist definiert für alle Wörter aus E-Stern.
Liebiges Wort, ich schaue mir an, auf welche Nummer, welche natürliche
Zahl wird dieses Wort abgebildet.
Das ist ja, das W kann ich ja einfach suchen.
Ich gehe in die entsprechende Diagonale, in das Feld I, I.
Schaue nach, welches Wort steht dort.
Steht dort das U drin, dann ist das G von WI gleich V.
Steht dort nicht U drin, dann ist das G von WI gleich U.
Und jetzt haben wir also eine Funktion, die eine Diagonalisierung
dieser Tabelle darstellt.
Ich gebe eben hier, diese Funktion ist definiert genau über diese
markierten Felder, eine Diagonalisierungsfunktion.
Ein Standardverfahren, mit dem man viele interessante Sachen zeigen
kann.
Und jetzt nehme ich an, dass F abzählbar ist, das heißt, wenn das
abzählbar ist, dann gibt es natürlich eine Funktion FK, die gleich dem
G sein muss.
Wenn es abzählbar ist, ja diese Funktion ist ja berechenbar.
Dazu kommen wir noch.
Um Berechenbarkeit geht es hier nicht, es geht nur um Abzählbarkeit.
Es ist ja eine der Funktionen.
Es geht um alle Funktionen von E-Stern nach E-Stern.
Ja, das war das große F.
Das große F war die Menge aller Funktionen von E-Stern nach E-Stern.
Wenn es abzählbar ist, dann ist insbesondere diese Funktion G, das ist
ja auch eine Funktion von E-Stern nach E-Stern, die wir gerade
definiert haben, ist dann irgendein solches FK.
Irgendeine natürliche Zahl ist zugeordnet.
Das heißt, das FK muss natürlich auch auf das WK anwendbar sein.
Ich schaue also nach bei FK von WK.
Und da das G gleich FK ist, muss natürlich G von WK gleich FK von WK
sein.
Wir haben aber hier gerade festgelegt, dass die Funktion G immer
gerade unterschiedlich ist von dem Eintrag in einem Diagonalelement.
Also G ist garantiert unterschiedlich von FK WK.
Hiernach müsste es aber gleich sein.
Und das heißt, dass G kann nicht gleich FK sein.
Und damit heißt das, diese Annahme, F ist abzählbar, die muss
irgendwie falsch sein.
Das Verfahren ist sehr abstrakt.
Richtig, da haben Sie recht.
Allerdings auch sehr konkret.
Ich kann Ihnen genau angeben, wie ich Wörter anordne.
Wenn ich also die 0, wenn ich dann 0,1 habe, ich kann Ihnen alle
Abbildungen angeben von Binärwörtern auf irgendwelche Binärwörter.
Und das Ganze ist natürlich in dem Sinne abstrakt, dass das ein
Argument ist.
Ich nehme an, dass F ist abzählbar.
Dann muss es zu jeder Funktion da drin eine natürliche Zahl geben,
weil es abzählbar ja heißt.
Jedes Element kann auf eine natürliche Zahl eindeutig abgebildet
werden.
Und ich habe diese Abbildung G, die offensichtlich eine Abbildung von
E -Stern nach E-Stern ist, also drin ist in der Menge F, gerade so
definiert, dass sie unterschiedlich sein muss von allen diesen
Diagonalelementen FK von WK.
Damit kann es eben keine solche Funktion G sein.
Das ist ein abstraktes Argument.
Aber man kann eben mit abstrakten Überlegungen sehr praktische
Erkenntnisse gewinnen.
Noch eine Frage.
Absolut nicht verständlich.
Das tut mir sehr leid.
Ja.
Aber das müssen Sie sich einfach trotzdem klar machen.
Das Argument ist ein Diagonalisierungselement.
Oder ein Diagonalisierungsargument.
Sie nehmen an, die Menge ist abzählbar.
Wenn die abzählbar ist, dann gibt es eine Abbildung, die hatten wir
vorher mal aufgeführt.
Dann kann ich eben jedes Element von F, jede solche Funktion F, kann
ich halt abbilden auf irgendein Element K.
Also jede Funktion wird auf irgendein Element K aus N abgebildet.
Ich bilde Groß F auf N ab.
Das war die Abzählbarkeit.
Jetzt stelle ich fest, diese Funktion G ist ein solches Element von
Groß F.
Also muss ich dafür eine natürliche Zahl finden können.
Und wenn ich also angenommen habe, dass ich eine solche Tabelle
aufschreiben kann, in der alle diese Funktionen auftreten, dann stelle
ich fest, diese Funktion G ist aber keine solche, die dort aufgeführt
ist.
Das heißt, die Annahme, ich kann eine solche Tabelle aufschreiben, die
ist einfach falsch.
Ich kann keine solche Tabelle aufschreiben, bei der alle Funktionen so
abgezählt werden, also abzählbar sind entsprechend dieser natürlichen
Zahlen.
Noch eine Frage.
Danke.
Alles offensichtlich.
Also beschäftigen Sie sich ein bisschen damit, dann kommen Sie von dem
Zustand absolut nicht verständlich zu alles offensichtlich.
Das ist ein Standardverfahren, das man anwendet in Überlegungen zu so
Mächtigkeiten, die man sich irgendwo noch genauer angucken kann.
Also, das ist also der Widerspruch und damit haben wir gezeigt, dass
die Menge der Funktionen von E-Stern nach E-Stern nicht abzählbar ist,
also überabzählbar.
Andererseits, wenn wir uns anschauen, die Menge der berechenbaren
Funktionen, dann wissen wir, jede berechenbare Funktion ist durch
einen Text endlicher Länge beschrieben.
Ein Text endlicher Länge ist irgendein Wort über einem Alphabet.
Wir wissen, die Wörter eines Alphabets kann ich alle der Reihe nach
aufschreiben.
Da kann ich Ihnen sofort angeben, wie ich die Zahl bestimme zu
irgendeinem beliebigen Wort.
Und das heißt, da die Menge aller Wörter abzählbar ist, ist damit auch
die Menge aller berechenbaren Funktionen abzählbar.
Weil ich hier genau durch solche Wörter, nicht jedes Wort wird eine
berechenbare Funktion beschreiben, aber die Menge der berechenbaren
Funktionen über einem geeigneten Alphabet, nein, die Menge der
Beschreibungen von berechenbaren oder von berechenbaren Funktionen ist
halt eine Teilmenge aller Wörter über einem geeigneten Alphabet.
Und damit weiß ich, die Menge der berechenbaren Funktionen ist
abzählbar.
Das heißt, die berechenbaren Funktionen sind wirklich eine Teilklasse.
Und ich muss mir genau überlegen, was sind eigentlich die Funktionen,
die ich berechnen kann.
Wie kann ich diejenigen charakterisieren, die nicht berechenbar sind.
Von der Berechenbarkeit kommen wir noch zu einem äquivalenten Begriff,
zu dem Begriff der Entscheidbarkeit.
Hier haben wir, betrachten wir folgendes, eine Menge M1 und eine Menge
M2.
Und M1 nennen wir entscheidbar relativ zu M2, wenn wir für jedes
Element aus M2 feststellen können, ob das W in M1 liegt oder nicht.
Dann ist M1 entscheidbar relativ zu M2.
Also eine endliche Menge, wenn ich eine endliche Menge habe als
Teilmenge von E-Stern, die ist immer relativ entscheidbar oder
entscheidbar relativ zu E-Stern, selbstverständlich.
Ich gebe Ihnen gleich ein paar Beispiele.
Ein solches Verfahren, das diese Entscheidung trifft, gehört das
Element zu M1 oder nicht zu M1, sondern zu M2, nennt man dann ein
Entscheidungsverfahren.
Und das ist also der Algorithmus, der dieses Entscheidungsverfahren
darstellt.
Und dann nennt man eine Menge absolut entscheidbar oder einfach nur
entscheidbar, wenn M relativ zu E-Stern entscheidbar ist, wenn also
diese M2 das E-Stern ist.
Das ist also die Definition.
Und dann nochmal die Beziehung jetzt zu den berechenbaren Funktionen.
Wenn ich eine Menge mir hernehme, oder die beiden Mengen M1 und M2,
dann kann ich eine Funktion angeben, die gerade auf jedes Element von
M2 angewandt wird und jeweils True oder False ausgibt, je nachdem, ob
ein Element aus M2 zu M1 gehört oder nicht.
Also die charakteristische Funktion zu M1 und M2, also von M1
bezüglich M2, ist gerade die Funktion, die mir sagt, wahr, wenn das
ein Element von M1 ist und falsch, wenn das kein Element von M1 ist.
Das ist die charakteristische Funktion einer Menge und das soll
einfach nur darstellen, ich kann eine Menge beschreiben durch eine
charakteristische Funktion, also die Mitgliedschaft in einer Menge
durch eine charakteristische Funktion angeben.
Und wenn also M1 entscheidbar ist, relativ zu M2, das war diese
Definition hier oben, dann ist also die charakteristische Funktion für
M1 und M2 eine berechenbare Funktion.
Wir haben dann ja einen solchen Algorithmus, ein
Entscheidungsverfahren, das gerade diese Funktion berechnet.
Also Berechenbarkeit und Entscheidbarkeit haben sehr viel miteinander
zu tun, ist hier dargelegt.
Betrachtet der Entscheidbarkeit kann ich entscheiden, ob ein Element
zur Sprache gehört oder nicht.
Wir haben uns häufig jetzt schon mit Entscheidbarkeitsfragen
beschäftigt, nämlich bei der Frage, gehört ein Wort über dem Alphabet
zu einer rechtslinearen Sprache oder kontextfreien Sprache oder
kontextsensitiven Sprache, bezogen auf eine bestimmte Grammatik oder
einen Automaten einer bestimmten Klasse.
Das waren alles Entscheidungsprobleme, nämlich Wortprobleme.
Und jetzt sagen wir, wir können das auch übersetzen in
Berechenbarkeit, wenn nämlich die jeweils charakteristische Funktion
berechenbar ist, dann ist die Menge entsprechend entscheidbar.
Beispiele.
Die Menge der Primzahlen ist entscheidbar relativ zur Menge der
natürlichen Zahlen.
Man kann für jede natürliche Zahl feststellen, ob diese Zahl eine
Primzahl ist oder nicht.
Also entscheidbar relativ zu N.
Man muss nur testen, ob es irgendeine kleinere Zahl gibt, die diese
Zahl N teilt.
Oder jede endliche Menge ist entscheidbar.
Man muss ja nur diese endliche Menge durchsuchen und bin fertig.
Wenn ich also irgendein Wort habe, ich kenne die Menge, diese endliche
Menge RM, dann muss ich ja nur diese Menge einmal durchschauen,
endlich viele Dinge angucken, das ist in endlicher Zeit machbar.
Die Beschreibung dieser Menge gibt mir schon das endliche Verfahren
an.
Ganz einfach.
Oder kontextfreie Grammatik mit der endlichen...
Hier ist also die Frage, alle Grammatiken, M1 ist eine Menge von
Grammatiken, die kontextfrei sind und die von der Grammatik erzeugte
Sprache ist endlich.
Jetzt ist die Frage, ist diese Menge entscheidbar, relativ zu M2 und
M2 ist die Menge aller beliebigen kontextfreien Grammatiken.
Das heißt, kann ich entscheiden, ob eine Grammatik eine endliche
Sprache erzeugt oder eine unendliche Sprache.
Ja, ich habe also eine Grammatik gegeben, kontextfrei und die Frage
ist, ist L von G Betrag davon aus N.
Endlich.
Da sind Sie zunächst mal, werden Sie rätseln, wieso das entscheidbar
sein soll, aber erinnern Sie sich an das Pumping Lemma.
Wir brauchen nur nachzuschauen, ob diese kontextfreie Grammatik
irgendein Wort ableiten kann, über einer bestimmten Grenze.
Nämlich einer Grenze, bei der der Ableitungsbaum einen Pfad enthält,
bei dem mindestens ein Nicht-Terminalzeichen doppelt auftaucht.
Und sobald sie auf einer Grammatik einen Ableitungsbaum erzeugen kann,
bei dem ein Zeichen doppelt auftaucht, also sich wiederholt, wissen
Sie, dann können Sie beliebig viele Wörter erzeugen, weil Sie dann
gerade so eine Pumpstelle erzeugt haben.
Das heißt, Sie brauchen nur die Grammatik anzuschauen, sich alle
Pfade, Ableitungsbäume anzuschauen, bis zu einer bestimmten Länge und
sofort wissen Sie, ob die Sprache, die erzeugt wird, endlich ist oder
nicht endlich.
Falls Sie also einen solchen Ableitungsbaum erzeugen können aus der
Grammatik, bei dem Sie eine Wiederholung von Nicht-Terminalzeichen
bekommen, wissen Sie, die ist nicht endlich.
Das ist sehr einfach zu entscheiden.
Das heißt, ich kann diese Menge M1 entscheiden, relativ zu M2.
Was ich entscheiden muss, ist eigentlich nur, ist die Sprache zu einer
Grammatik, zu einer kontextfreien Grammatik, endlich oder unendlich.
Geht also relativ leicht.
Jetzt kommt der nächste Begriff.
Wir hatten jetzt Abzählbarkeit.
Tut mir leid, ich muss Ihnen das alles darstellen, weil wir auf einen
großen Satz hinsteuern, mit dem wir charakterisieren wollen,
Funktionen, die nicht berechenbar sind.
Jetzt müssen wir uns noch Folgendes anschauen, nämlich gerade in Bezug
auf diese Berechenbarkeit.
Wir sagen, eine Menge ist aufzählbar, genau dann, wenn es eine
surreaktive, berechenbare Funktion gibt, die die Menge der natürlichen
Zahlen abbildet auf meine Menge M.
Was ist da das Interessante?
Aufzählbar heißt Folgendes.
Ich mache mir eine Tabelle 1, 2, 3, 4, 5, 6, 7 und so weiter.
Ich schreibe mir die Zahlen hin, fange sogar mit 0 an.
Und jetzt möchte ich die Menge aufzählen.
Das heißt, meine Funktion f hier, die soll mir jetzt angeben ein Wort
w0 und ein Wort w1 und ein Wort w2 und so weiter.
Ich möchte also zu jeder Zahl angeben können, das ist das Wort mit dem
Index 1, 2 oder was immer.
Es kann sein, dass die 3 auch auf das w2 abgebildet wird und die 4
vielleicht auf irgendein w4 und so weiter.
Also es muss nicht injektiv sein.
Das heißt, es kann eine ähnliche Menge sein.
Es kann sein, dass die alle anderen dann nur noch hier auf das w4
gehen.
Aber ich muss in der Lage sein, alle Elemente von m aufzuzählen und
bekommen dadurch, dass ich für jede Zahl mir anschaue, was ist das
entsprechende Wort.
Und wenn das eine berechenbare Funktion ist, dann habe ich also ein
Verfahren, um die Menge m mit einem Algorithmus aufzuzählen.
Das ist also etwas anderes als nur abzählen.
Das hieß nur, es gibt eine Funktion, die die Menge injektiv abbildet
in die Menge der natürlichen Zahlen.
Hier möchte ich es wirklich aufzählen können.
Das heißt, ich schaue mir an, für irgendein k, was ist eigentlich das
Element wk, das dazu gehört.
Und der Satz, den man hier zu sich überlegen kann, ist für jede
beliebige Menge m.
Wenn das m aufzählbar ist, dann ist m auch abzählbar.
Umkehrung gilt natürlich nicht.
Also das ist auch nicht ganz offensichtlich.
Bei Aufzählbarkeit reden wir von einer Abbildung von n0 nach m.
Bei Abzählbarkeit reden wir von einer Funktion von m in die Menge der
natürlichen Zahlen.
Wir können praktisch über die Umkehrfunktion dieser
Aufzählungsfunktion genau diese Abzählbarkeit wieder hinbekommen.
Und das m ist entscheidbar genau dann, wenn m und e-m aufzählbar sind.
Wie kann man das denn einsehen?
Ich habe irgendein Wort w aus dem m.
Ne, ich habe irgendein Wort w aus e-stern.
Und ich möchte wissen, die Frage ist, ist das w aus m?
Wie kann ich das über Aufzählbarkeit hinbekommen?
Ich mache es einfach folgendermaßen.
Ich weiß ja, ich kann die Menge m aufzählen.
Ich kann also f von 0 hinschreiben, f von 1, f von 2 und so weiter.
Ich kann mir auch e-stern-m hernehmen.
Ich nehme an, e-stern-m ist auch aufzählbar.
Dann kann ich hier angeben irgendein f' von 0, f' von 1, f' von 2 und
so weiter.
Das erste Aufzählungsverfahren f liefert mir alle Elemente von m.
Das Aufzählungsverfahren f' liefert mir alle Elemente von e-stern-m.
Jetzt gucke ich der Reihe nach an, f0, f' von 0, f1, f' von 1, f2, f'
von 2.
Und irgendwann, wenn das Wort in w in m ist, wird es irgendwann
auftreten.
Es ist ja irgendwann einmal, wenn es in m ist, ist es irgendein f von
k.
Dann taucht das irgendwann auf.
Wenn es nicht in m ist, dann ist es ja hier in der Menge e-stern-m.
Dann ist es irgendein Strich von k oder Strich von j oder was immer.
Das heißt, wenn ich gleichmäßig m und e-stern-m aufzähle durch meine
Funktionen f und strich, bekomme ich irgendwann raus, ob das w in der
Aufzählung von m auftaucht oder in der Aufzählung von e-stern-m.
Und damit kann ich entscheiden, also nach endlicher Zeit feststellen,
ob das w zu m gehört oder zu e-stern-m.
Deswegen, wenn die Menge und ihr Kompliment aufzählbar sind, dann ist
die Menge entscheidbar.
Das ist also noch eine weitere Erkenntnis, die man hier gewinnen kann.
Damit haben wir also jetzt diese Struktur, der Bezug auf
Entscheidbarkeit, uns überlegt.
Es gibt also die abzählbaren Mengen, die hatte ich Ihnen zunächst
dargestellt.
Dann gibt es die aufzählbaren Mengen, das sind diejenigen mit einer
berechenbaren Funktion.
Und ich habe die entscheidbaren Mengen, bei denen die Menge aufzählbar
ist und der Kompliment auch aufzählbar ist.
Und damit habe ich also jetzt so bestimmte Begriffe definiert.
Wenn Sie in der Literatur nachschauen, finden Sie manchmal Begriffe
wie rekursiv.
Das ist das gleiche wie entscheidbar.
Also eine rekursive Menge ist eine entscheidbare Menge.
Eine rekursiv aufzählbare Menge ist eine aufzählbare Menge.
Oder es ist auch eine semi-entscheidbare Menge.
Nur das ist so, wenn Sie irgendwo was lesen, dass Ihnen klar ist, was
damit gemeint ist.
Damit habe ich Ihnen jetzt mehrere Begriffe dargestellt, die zunächst
mal sehr abstrakt klingen, sind auch sehr allgemeine Überlegungen,
weil man damit fundamentale Erkenntnisse gewinnen kann, denen wir uns
allmählich nähern.
Das nächste ist die Frage, welche Funktion kann ich eigentlich mit
Turing -Maschinen berechnen?
Das ist jetzt die Turing-Maschine, die Turing-Berechenbarkeit.
Allgemeine Berechenbarkeit war unabhängig von einem Maschinenmodell
definiert worden.
Irgendein endliches Verfahren.
Selbstverständlich ist jede Turing-Maschine ein endliches Verfahren.
Habe ich in endlichem Text hingeschrieben.
Ich weiß, wie ich eine Turing-Maschine arbeiten lasse.
Das heißt, ich habe dort eine endliche Beschreibung eines Verfahrens,
das irgendetwas tun soll.
Sind entscheidbare Mengen selbst aufzählbar?
Selbstverständlich.
Die Frage hätten Sie sich eben selbst beantworten können, trotzdem
dürfen Sie die gerne stellen.
Eine Menge ist entscheidbar, wenn sie selbst und ihr Komplement
aufzählbar sind.
Also entscheidbare Menge muss selbst aufzählbar sein.
Das steht in der Definition gerade drin.
In dem Satz haben wir das gerade eben festgestellt.
Jetzt gehen wir zu den Turing-Maschinen und sagen, wir haben jetzt
eine Turing-Maschine mit einem bestimmten Eingabeband.
Da steht das Wort W drauf.
Wenn die Turing-Maschine aufhört zu arbeiten, wenn sie endet mit ihrer
Berechnungsfolge, steht auf dem Band irgendwas anderes.
Und wir sagen, das V ist jetzt das Bild von W.
Beziehungsweise wir sagen, die Turing-Maschine berechnet eine Funktion
F, wenn sie für jedes Wort W nach endlich vielen Schritten anhält und
der Bandinhalt dann gerade das Bild von W und der F ist.
Ja, das also dann hält an in einem Endzustand.
Dann sagen wir, diese Turing-Maschine kann die Funktion F berechnen.
Das steht hier formal nochmal drin.
Hier war es nur die bildliche Beschreibung.
Intuitiv, formal müssen wir es so hinschreiben.
Wir haben eine Funktion von M1 nach M2 und wir sagen, dass die Turing
-Maschine diese Funktion berechnen kann, wenn für jedes Wort aus M1
genau dieses V erzeugt werden kann.
Also wenn W aus M1 ist und V gleich F von W, dann kann ich aus der
Anfangskonfiguration, bei der W auf dem Band steht und ich im
Anfangszustand S0 bin, nach endlich vielen Schritten auf eine
Endkonfiguration kommen, bei der die Bandinschrift UX gleich V ist und
das S ist ein Endzustand und ich kann nicht mehr weitermachen.
Die Turing-Maschine hat aufgehört zu arbeiten.
Also für V nicht aus M1 ist allerdings das Verhalten der Maschine
unbestimmt.
Ich sage nur für alle Elemente aus M1.
F ist aber auch nur eine Funktion von M1 nach M2.
Und das F heißt, diese Funktion heißt also Turing-Berechenbar, wenn
ich eine Turing-Maschine beschreibe oder erzeugen kann, die genau
diese Funktion berechnet.
Und jetzt habe ich ein formales Modell für einen
Berechenbarkeitsbegriff.
Ich kann Ihnen genau sagen, zu einem Text, den Sie mir hinschreiben,
beschreibt dieser Text eine Turing-Maschine oder beschreibt er
irgendwas anderes.
Wenn er eine Turing-Maschine beschreibt und diese Turing-Maschine
meine Funktion berechnet, dann ist diese Funktion Turing-Berechenbar.
Beispiel hatte ich Ihnen schon einige Jahre genannt.
Hier ist ein Beispiel, das Sie noch nicht so richtig einordnen können.
Hier steht, berechnen das 1-Komplement von W.
Das 1-Komplement lernen wir später kennen.
Das ist eine gewisse Möglichkeit, wie man irgendein Binärwort
umwandeln kann in eine Darstellung.
Wenn das also eine Zahl X ist, dann will ich das Komplement zu X
berechnen.
Das ist also im Prinzip 2 hoch N minus 1 minus X.
Das ist in dem Fall ein Komplement.
Kommen wir später drauf bei Zahlendarstellungen.
Wenn ich positive und negative Zahlen darstellen will, dann stelle ich
die negativen Zahlen dadurch solche Komplemente.
Und das witzige ist, man kann das genau erzeugen, indem man hier
einfach die Bits alle kippt.
Also wenn ich für X, wenn das irgendeine Binärkombination ist,
irgendeine Zahl ist, eine Binärzahl, ist das 1-Komplement zu X gerade
das Wort, das entsteht, wenn ich alle Bits kippe aus einer 1 eine 0
und aus einer 0 eine 1 mache.
Genau das soll hier geschehen durch meine Turing-Maschine.
Die Turing-Maschine, also diese Funktion F, liefert für die leere
Eingabe die leere Eingabe ab und für ein Wort, das mit einer 1
beginnt, wird ein Wort abgeliefert, das mit einer 0 beginnt.
Danach wird das Restwort entsprechend bearbeitet und andersherum aus 0
wird 1.
Die Turing-Maschine, die das macht, kann ich ganz einfach
aufschreiben.
Im Anfangszustand, wenn ich eine 0 sehe, schreibe ich eine 1.
Gehe nach rechts und bleibe in dem Zustand.
Wenn ich eine 1 sehe, schreibe ich eine 0 und gehe nach rechts und
bleibe in dem Zustand.
Wenn ich das Wort vollständig abgearbeitet habe und das Leerzeichen
sehe, gehe ich in den Endzustand und mache gar nichts mehr.
Gehe nach links, auch letzte Zeichen, unter Formel S1 kann ich nichts
mehr tun.
S1 ist der Endzustand.
Dann habe ich also hier eine ganz einfache Turing-Maschine, die das 1
-Komplement einer Zahl berechnet.
Wir kommen also später nochmal auf diese ganzen Zahlendarstellungen.
Dann haben wir entsprechend jetzt weitere Begriffe.
Wir haben jetzt Berechenbarkeit definiert über Turing-Maschinen.
Jetzt können wir auch die Aufzählbarkeit und Entscheidbarkeit über
Turing -Maschinen definieren.
Können nämlich sagen, eine Menge ist Turing-aufzählbar, genau dann,
wenn es eine sujektive Turing-berechenbare Funktion von N0 nach M
gibt.
Das heißt, wenn die Funktion für die Aufzählbarkeit gerade eine Turing
-berechenbare Funktion ist.
Und entsprechend Turing-entscheidbar, wenn die charakteristische
Funktion Turing-berechenbar ist.
Ich ersetze praktisch in allen Definitionen, die wir bisher hatten,
berechenbar durch Turing-berechenbar.
Offensichtlich sind alle Turing-berechenbaren Funktionen berechenbar,
das ist sofort klar.
Damit haben wir jetzt eine Teilklasse charakterisiert von Funktionen,
die Turing-berechenbar sind.
Eine Teilklasse der berechenbaren Funktionen.
Und es ist offensichtlich, M ist Turing-aufzählbar, genau wenn es eine
Turing -Maschine gibt, die genau die Eingaben W aus M akzeptiert, aber
für W nicht aus M eventuell nie stoppt.
Und man nennt deswegen diese Turing-aufzählbaren Mengen auch semi
-entscheidbar.
Also das kann man sich leicht überlegen, dass das so der Fall ist.
Die Begriffe hatte ich Ihnen schon dargestellt.
Und jetzt wollen wir uns folgendes weiteres überlegen.
Wir haben in der Rechnerwelt, wir wollen ja allgemein über
berechenbare Funktionen reden können.
Ich habe jetzt als Modell die Turing-Maschine genannt.
Sie haben in Ihren Hosentaschen oder vor sich stehen irgendein
Rechner.
In Ihrem Laptop oder in Ihrem Handy oder wer weiß wo.
Das sind Rechner, die können nicht nur eine Funktion berechnen, die
können viele Funktionen berechnen.
Das heißt, wir erwarten eigentlich, dass unsere Rechner
Universalrechner sind.
In dem Sinne, dass sie jede beliebige berechenbare Funktion berechnen
können.
Unsere Turing-Maschine kann aber nur eine Funktion berechnen.
Ist also kein gutes Modell.
Sehr eingeschränkt.
Jede Turing-Maschine berechnet eine Funktion.
Wenn Sie genauer sich anschauen, den Universalrechner, den wir noch
genauer kennenlernen werden, etwas später in der Vorlesung, dann ist
das natürlich auch nur ein Automat, den Sie beliebig füttern können
mit Programmen.
Sie können ein Programm eingeben in einen Rechner und dieses Programm
berechnet eine Funktion.
Wenn Sie also einen Rechner betrachten, in Bezug auf die Ausführung
eines Programms, dann ist das ein Gerät, das eine Funktion berechnet,
nämlich die Funktion dieses Programms.
Jetzt ist die Idee, kann ich das nicht übertragen auf Turing
-Maschinen?
Kann ich nicht einfach sagen, ich schreibe einfach auf mein Band der
Turing -Maschine ein Programm.
Und dann schreibe ich dahinter noch irgendein Eingabewort.
Und dann soll die Turing-Maschine alles das, was auf dem Band steht,
interpretieren, geeignet um das Wort.
Also ich habe hier mein großes Band.
Dann schreibe ich hier einfach erst mein Programm hin.
Und dann schreibe ich hier das W hin, die Eingabe.
Und dann soll meine Turing-Maschine, die hier unten dran sitzt und
darauf etwas lesen kann, für jedes Zeichen, oder praktisch dieses Wort
W entsprechend bearbeiten, entsprechend dem, was hier in diesem
Programmteil drin steht.
Das kann man ja alles lesen und interpretieren und so weiter.
Das heißt, die Frage ist, kann ich nicht einfach eine Turing-Maschine
definieren, die das kann?
Die eine beliebige Beschreibung einer Rechenvorschrift auf dem Band
akzeptiert, das ist hier meine Rechenvorschrift, und dann das, was
dort steht, geeignet umsetzt in eine Bearbeitung dieses Wortes, das
hier eingegeben wurde, um daraus dann irgendwann das F von B zu
erzeugen.
Wenn ich eine solche Turing-Maschine beschreiben könnte oder
definieren könnte, dann ist die ja genauso universell wie unser
normaler Rechner, der beliebiges Programm akzeptieren kann.
Und das ist genau die Idee, die man hier verwendet.
Ich möchte also, dass ich das Verhalten einer beliebigen Turing
-Maschine bei Eingabe von W simulieren kann, mit einer universellen
Turing -Maschine U.
Das heißt, ich brauche eigentlich gar nicht, mir ganz viele Turing
-Maschinen zu definieren, ich definiere mir eine und dann viele
Beschreibungen von Turing-Maschinen, die mir im Prinzip jeweils dafür
sorgen, dass das entsprechende Programm richtig interpretiert wird.
Hier ist die Idee nochmal, auf das Band dieser universellen Turing
-Maschine schreibe ich die Arbeitsweise einer Turing-Maschine rauf.
Ich brauche ja nur die Tabelle rauf zu schreiben, unsere Turing-Tafel.
Die schreibe ich einfach auf das Band einer anderen Maschine rauf und
jetzt liest hier steht irgendwo die Initialkonfiguration der Turing
-Maschine und dann muss ich einfach nachschauen, was macht eigentlich
die Turing-Maschine mit dieser entsprechenden Konfiguration.
Das steht ja alles in dieser Arbeitsweise hier drin und dann wird das
einfach angewandt und ich kann dann die nächste Konfiguration erzeugen
und die nächste und die nächste.
Ich erzeuge also alle Folgenkonfigurationen von T entsprechend der
Arbeitsweise, die dort definiert wurde und wenn ich auf dem Band eine
Endkonfiguration von T erzeugt habe, dann geht auch unsere universelle
Turing -Maschine in eine Endkonfiguration.
Das heißt, das simuliert genau das, was wir machen, wenn wir ein
Programm schreiben und in unseren Rechner ausführen lassen.
Genau das wird hier durch eine universelle Turing-Maschine gemacht.
Und jetzt kann man natürlich annehmen.
Ich habe die Turing-Maschinen alle normiert, beschreibe die alle durch
Nullen und Einsen.
Das heißt, ich mache irgendeine binäre Inschrift und muss die geeignet
interpretieren.
Das kann man alles machen.
Ich muss meine Zustandsmenge geeignet kodieren.
Da habe ich irgendwie N Zustände drin.
Hier kann ich die entsprechenden Zahlen von 0 bis N oder 0 bis N-1
gerade beschreiben.
Ich habe einen Anfangszustand, ich habe eine N-Zustandsmenge.
All das muss ich geeignet kodieren.
Und dann habe ich eine Kodierung, die dann zum Beispiel so aussieht.
Ich habe bei einem Übergang von SJ und dem Zeichen BI auf ein SK,
schreibe das Zeichen BR und mache eine Operation XM.
Da muss ich nur folgendes machen.
Ich kann das beschreiben durch J Einsen, davor eine Null.
Dann kommt wieder eine Null und dann kommen hier I Einsen.
Dann kommt wieder eine Null, es kommen K Einsen.
Dann kommt wieder eine Null, es kommen jetzt R Einsen.
Und dann habe ich wieder eine Null und es kommen M Einsen.
Das M kann sehr klein sein, weil ich hier nur drei verschiedene
Operationen unterscheiden muss.
Das ist also einfach.
Aber das hier würde genau das kodieren, was hier steht.
Durch Null und Einsen kodiert.
Dann muss ich die geeignet voneinander trennen.
Dann muss ich vielleicht zwei Nullen machen, um diese
unterschiedlichen Sachen voneinander zu trennen.
Und auf die Art und Weise kann ich also eine solche Tabelle
aufschreiben.
Also die aktuelle Bandinschrift und der aktuelle Zustand sind durch
Nullen getrennt und so weiter.
So kann ich meine Turing-Tabelle aufschreiben auf das Band und ich
kann das geeignet interpretieren.
Ich muss eben immer nur zählen können, habe ich hier J Einsen oder I
Einsen oder K Einsen, R Einsen oder M Einsen.
Und entsprechend muss ich das alles in meine Zustandsmenge meines
Automaten geeignet kodieren und kann das dann ausführen.
Und die Position des Schreiblesekopfes auf dem Band muss ich auch
simulieren.
Das mache ich durch drei aufeinanderfolgende Nullen vor dem zu
lesenden Zeichen auf dem Band und bin dann damit auch fertig.
Alles geeignet kodiert, kann man alles so machen.
Und dann muss ich schrittweise die Turing-Maschine simulieren.
Ich will Ihnen das jetzt nicht alles explizit formal hinschreiben, wie
die Funktion genau aussieht von U, die genau das macht.
Aber ich denke, Sie bekommen einen Eindruck davon, dass man das machen
kann.
Dass ich also die Arbeitsweise einer Turing-Maschine durch eine Folge
von Nullen und Einsen beschreiben kann.
Durch geeignete Kodierung mit wieder weiteren Nullen, ich eine
Trennung herstellen kann zwischen der Beschreibung der Arbeitsweise
und dem zu lesenden und der Bandinschrift.
Kann andeuten, wo ich gerade bin.
Also alles ist machbar.
Das ist dann die Simulation einer solchen Turing-Maschine, die eben
beginnt mit der Beschreibung der Arbeitsweise der Turing-Maschine.
Mit der Anfangskonfiguration und dann entsprechend in einen neuen
Zustand übergeht.
Und neben dieser Anfangsarbeitsweise jetzt die Beschreibung der
Folgekonfiguration hat.
Und so weiter, bis man irgendwann auf eine Endkonfiguration kommt.
Sofern die Maschine tatsächlich anhält oder auch nicht.
Das heißt, ich kann eine universelle Turing-Maschine angeben.
Eine beliebige Turing-Maschine simuliert.
Und damit habe ich jetzt also die Möglichkeit mit einer Turing
-Maschine alle berechenbaren Funktionen zu berechnen.
Ich kann natürlich auch alle möglichen Turing-Maschinen in eine feste
Reihenfolge bringen.
Ich muss ja nur meine Beschreibung der Turing-Maschinen lexikografisch
anordnen zum Beispiel.
Kann ich alle aufschreiben und habe dann eine Anordnung dieser Turing
-Maschine.
Dann kann ich natürlich alle möglichen Eingabewörter ebenfalls
anordnen.
In eine feste Reihenfolge, wie 1, wie 2, wie 3.
Und wenn ich das so mache, dann mache ich jetzt im Prinzip das
gleiche, was ich vorher auch schon überlegt hatte.
Gibt es eine Sprache, die ich nicht durch eine Turing-Maschine
erzeugen kann.
Oder beziehungsweise akzeptieren kann.
Das wäre eine Sprache LNA.
Und diese Sprache können wir uns ganz einfach, völlig analog zum
Existenz einer nicht berechenbaren Funktion hier überlegen.
Es gibt eine Turing-Maschine T.
Also ich nehme an, kann diese Sprache NA erzeugen mit einer Turing
-Maschine.
Dann gibt es natürlich, wegen der Abzielbarkeit der Menge der Turing
-Maschinen, das hatten wir gesagt, wir können uns die alle so
anordnen, wir können also eine Abzählbarkeit auf jeden Fall
postulieren.
Dann gibt es eine Turing-Maschine TJ, die gerade diese Turing-Maschine
ist.
Die die Sprache NA akzeptiert.
Und jetzt kommt das gleiche.
Das WJ, hier diese Sprache NA, ist eine besondere Sprache.
WI ist in der Sprache, wenn WI nicht aus der Sprache der ITEN-Turing
-Maschine ist.
Also wieder so eine Diagonalisierungssprache, genau wie vorher die
Diagonalisierungsfunktion.
Wenn ich also eine Turing-Maschine hätte, die diese Sprache
akzeptieren kann, bei der gerade das Wort WI nicht aus der Sprache der
Turing -Maschine TI ist, dann weiß ich, die Turing-Maschine ist
irgendeine Turing-Maschine TJ.
Das WJ ist also in der Sprache LNA, genau dann, wenn WJ aus L von T
ist, weil ich annehme, L von T ist gleich LNA.
Dann ist das WJ aber aus L von TJ, weil ich sage, T ist gleich TJ.
Wenn aber das WJ aus L von TJ ist, ist WJ nicht aus LNA, wegen dieser
Definition.
Und das heißt, ich habe hier einen Widerspruch.
Kann ja nicht sein, dass WJ aus LNA ist, genau wie wenn es nicht aus
NA ist.
Das heißt, die Annahme, ich kann diese Sprache hier erzeugen, durch
eine Turing-Maschine, ist falsch.
Es gibt eine Sprache, die kann ich nicht durch eine Turing-Maschine
akzeptieren.
Ich kann ihnen die nicht explizit hinschreiben, aber es gibt eine
solche Sprache, die ich hier formal definiert habe.
Und das heißt, diese Sprache ist nicht durch eine Turing-Maschine
berechenbar.
Also, es gibt Sprachen, die nicht in L0 enthalten sind.
L0 waren ja alle Sprachen, die ich durch Turing-Maschinen akzeptieren
kann, beziehungsweise die erzeugt werden können von Typ-0 Grammatiken.
Und dann ist die Frage, wie kann ich überhaupt Turing-Maschinen
konstruieren.
Das macht man einfach so, dass man sich elementare Funktionen hier
nimmt, für die einfache Turing-Maschinen aufschreibt, und dann einfach
für Addition, Multiplikation und Vergleich sich weitere erzeugt.
Also, ich erzeuge mir eine Turing-Maschine, die irgendwelche
elementaren Anweisungen machen kann und schreibe dann auf, wie die
Hintereinanderausführung aussehen soll.
Ich kann eine Wiederholung machen, ich kann eine Verzweigung
definieren und kann dann das im Prinzip aufschreiben als Verknüpfung
von Turing-Maschinen.
Und Sie sehen, das sind Beschreibungen von Turing-Maschinen, die auf
einmal sehr ähnlich aussehen wie programmiersprachliche
Beschreibungen.
Das heißt, im Prinzip erzeuge ich mit einer, wenn ich eine Turing
-Maschine konstruiere, ein höhersprachliches Programm und ich habe die
Analogie hinbekommen zwischen den Turing-Maschinen und
höhersprachlichen Programmen.
Jetzt ist es so, dass, das muss ich jetzt noch ganz kurz, dann bin ich
am Ende eines wohldefinierten Abschnitts, es ist sicherlich so, dass
jede Turing-Berechenbare Funktion auch intuitiv berechenbar ist.
Die Turing-Maschine war das erste formale Modell zur Charakterisierung
intuitiv berechenbarer Funktionen.
Jetzt kann ich viele andere Sachen angeben.
Ich kann den Lambda-Kalkül angeben, ich kann Postsysteme angeben, ich
kann sehr viele verschiedene Formalisierungen berechenbarer Funktionen
angeben.
Und der Wissenschaftler Church hat diese Hypothese formuliert, der
sagt, jede im intuitiven Sinne berechenbare Funktion ist auch Turing
-Berechenbar.
Das ist eine These, weil ich sie nicht beweisen kann, weil ich nicht
sagen kann, was ist eine intuitiv berechenbare Funktion.
Ich sage, die ist auch Turing-Berechenbar.
Das heißt, was immer ich mir für ein Modell mache für eine
berechenbare Funktion, kann ich das überführen auf eine Turing
-Berechenbare Funktion.
Und das ist die Church-These, die also die Grundlage darstellt dafür,
dass ich mir für beliebige Fragestellungen auch unterschiedliche
Modelle hernehmen kann.
Ich muss nicht alles mit Turing-Maschinen machen.
Ich kann es auch mit anderen machen, aber diese intuitiv berechenbaren
Funktionen sind im Prinzip alle Turing-Berechenbar.
Ich könnte mich also auf Turing-Maschinen beschränken.
Wir werden das nicht tun.
Wir werden sehr schnell davon wegkommen und andere Maschinen
betrachten, aber im Prinzip kann ich das so machen.
Man meint sogar, dass eben die Turing-Maschinen sogar die Rechenzeit
bis auf polynomielle Faktoren richtig erfassen.
Das heißt, ein Problem ist genau dann effizient polynomiell lösbar.
Also, wenn ich Problemgröße N habe in Zeit O von N hoch K für
irgendein Polynom, wenn es von Turing-Maschinen in polynomieller Zeit
gelöst werden kann.
Auf die Frage kommen wir nächstes Mal zurück.
Beziehungsweise übernächstes Mal.
Nächstes Mal geht es um die Charakterisierung einer Funktion oder
eines Problems, von dem wir zeigen, das ist nicht entscheidbar.
Das wird das Halteproblem sein.
Vielen Dank, das war es für heute.