Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Turing-Maschinen
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 112 Zeilen
- So, in diesem Video soll es um Touringmaschinen gehen. Ich möchte erklären, was Touringmaschinen sind äh und auch ein bisschen über die
- Hintergründe und auch über die Bedeutung in der theoretischen Informatik erzählen. Ja, die Touringmaschinen, die gehen zurück auf Allen Touring. war ein
- britischer Mathematiker und Informatiker, der wirklich sehr großen Einfluss auf die ja die Anfänge der theoretischen Informatik hatte in den ja
- 40ern, 50ern, glaube ich, ähm war auch beteiligt an der Entschlüsselung der Enigma, ja, der deutschen Verschlüsselungsmaschine,
- diese Schreibmaschine. Ähm ja und deswegen hier einmal mit Foto, weil er wirklich für die theoret theoretische Informatik extrem wichtig
- ist. Ja, und natürlich die Touringmaschinen sind auch nach ihm benannt. Ja, die Touringmaschinen, die werden wir hier noch mal die Chomski
- Hierarchie, ja, die werden wir jetzt hier erstmal einordnen. Ähm, die Touringmaschinen sind ja auch nur ein äh wieder ein Werkzeug, um Sprachen zu
- erkennen für uns erstmal. Ja, die Tmaschinen haben auch noch andere Anwendungen, die wir vielleicht später noch sehen werden, aber wir lernen sie
- jetzt erstmal nur kennen als ein Werkzeug, mit dem wir Sprachen definieren können, so wie wir Deas und Neas und reguläre Ausdrücke hatten.
- Später auch Kellerautomaten und kontextfreie Grammatiken. So sind die Touringmaschinen na ja ein deutlich stärkeres Modell. Ja,
- und hier äh habe ich schon hingeschrieben, L0 heißen die Touring erkennbaren Sprachen. Äh die das zugehörige Automatenmodell, das sind die
- Touringmaschinen. Ja, die Touringmaschinen, die gehören also hierhin. Mit denen beschäftigen wir uns jetzt. Man könnte sagen, äh, die
- Touringmaschinen, die erinnern vielleicht ein bisschen an endliche Automaten. Ja, sie haben auch Zustände, Zustandsübergänge und so weiter, aber
- die Touringmaschinen, die sind der Versuch dem ganzen deutlich mehr Mächtigkeit zu geben oder sage ich mal mehr Möglichkeiten. Ja, die endlichen
- Automaten und auch Kellerautomaten, die konnten ja nur eigentlich das Wort, das Eingabewort einmal von links nach rechts durchgehen und dann am Ende sollen sie
- entscheiden, ist das Wort in der Sprache oder nicht. Ja, dabei können Sie irgendwie Zustände wechseln oder der Kellerautomat durfte auch noch in
- begrenzter Weise sich was an Information merken. Ja, aber die Touringmaschinen, die werden jetzt deutlich mächtiger und zwar funktioniert das so. Die
- Touringmaschinen, die haben jetzt ein sogenanntes Eingabeband. Das kann man sich vorstellen wie ein unendlich langes Band. Ja, von nach links und rechts ist
- das unendlich mit immer einzelnen Feldern hier. Ja, und jedem Feld darf mal ein Symbol stehen. Ja, am Anfang da steht da vielleicht irgendwo das
- Eingabewort drauf. Ja, und die Touringmaschine, die hat auch einen Lese und Schreibkopf. Der steht am Anfang auf dem ersten
- Symbol. Ja, das wäre hier dieses A. Ja, alle anderen Felder links äh also links vor dem ersten Symbol und rechts hinter dem letzten Symbol. Alle anderen Felder
- sind erstmal leer. Ja, das ist sozusagen die Startkonfiguration. So fängt eine Touring Maschine immer an. Äh und ich will die Felder jetzt nicht
- leer lassen. Dafür nimmt man nämlich ein Symbol. Äh wir nehmen mal dieses Symbol hier als Leerzeichen. So. Links über Leerzeichen. Dann steht da das
- Eingaberwort z.B. A B C und dann stehen wieder ganz viele Leerzeichen. Eine Touringmaschine, die darf jetzt wie wie schon gesagt darf sie nicht nur äh na
- ja, einmal nach rechts laufen und muss sich dann entscheiden, ist das Wort in der Sprache oder nicht? Nein, die Touringmaschine, die darf, na beliebig
- oft hin und her laufen. Die darf sogar hier in diesen Bereich, wo jetzt noch Leerzeichen stehen, da dürfte sie auch hinlaufen. Die darf das lesen, die darf
- da schreiben sogar. her, die darf Symbole verändern, die darf sogar da, wo das Eingabewort steht, das darf sie überschreiben und irgendwann
- äh soll sie sich dann irgendwann entscheiden. Ja, dann irgendwann, wenn sie meint, okay, jetzt habe ich genug rumgerechnet oder was auch immer, dann
- soll die Touringmaschine sagen, ja, das Wort ist in der Sprache oder nein, es ist nicht in der Sprache. Ja, und was für was für Möglichkeiten hat sie jetzt
- im Detail? Dafür beschreiben wir jetzt mal genau einen Schritt, den die Touringmaschine macht. Und zwar in einem Schritt, da steht sie immer, ja, der
- Lesekopf, der zeigt auf ein Feld in diesem Fall, dieses Feld hier. Sie liest dieses Eingabesymbol oder die liest das Symbol, was da gerade
- in diesem Feld steht. Ja, und sie befindet sich ja gleichzeitig auch noch in einem Zustand. Sie ist ja eine zustandbasierte Maschine, sowie endliche
- Automaten auch. Befindet sich z.B. gerade in diesem Zustand hier. Dann wird es einen Übergang geben, der sagt, wenn du ein A liest, ja, in dem Fall lesen
- wir jetzt ein A, z.B. dann äh schreib an die Stelle mal ein C und bewege dich nach rechts, also R für rechts. Ja. Ja, wenn es so einen Übergang gäbe, ja, wir
- befinden uns gerade in diesem Zustand und hier steht ACR dran, dann bedeutet das, wir dürfen das A durch ein Csetzen und dürfen einen Schritt nach rechts
- gehen mit unserem Lesekopf und dann befinden wir uns in diesem Zustand hier. Ja, das ist ein Schritt einer Touringmaschine. Ja, also noch mal zum
- Wiederholen, wir lesen ein Symbol und wir befinden uns in einem Zustand. Ja, und aus dieser Kombination, ja, diese beiden
- Informationen, in welchem Zustand sind wir und was lesen wir, daraus folgen dann quasi mal drei, ich sag mal, drei Anweisungen, nämlich was schreiben wir
- hin auf dieses Feld, wo gehen wir hin und äh wo wir hingehen, dafür haben wir drei Möglichkeiten. Rechts, das heißt ein Feld nach rechts, links wäre auch
- eine Möglichkeit, ein Feld nach links oder n für neutral oder für nicht bewegen. Ja, also drei Möglichkeiten. wir ein Schritt nach links oder ein
- Schritt nach rechts oder stehen bleiben. Ja, und wo der Fall hinzeigt, das ist der neue Zustand, in dem wir dann kommen. So, ich würde sagen, wir machen
- mal ein komplettes Beispiel, ein kompletten Ablauf einer Touringmaschine auf einem Eingabewort. Ja, dafür habe ich hier schon mal so eine
- Touringmaschine vorbereitet. Die hat einen Startzustand, die hat wieder eine Menge von Nzuständen, die hat diese Zustände der Art, wie ich sie eben
- erklärt habe, ja, mit immer zu lesenes Symbol, zu schreibendes Symbol und Richtung. Und ja, gehen wir einfach mal durch. Also, wenn hier das, wenn hier
- das Eingabewort ABC ist, ja, das merken wir uns mal, dass das Eingabewort ABC ist, denn das Eingabewort kann sich ja auch dann während die Touringmaschine
- läuft, kann sich das auch verändern. Deswegen sollten wir uns auf jeden Fall merken, Eingabewort ist A wie C. Jetzt gucken wir mal, was die Touringmaschine
- macht. Ja, und wir haben noch gar nicht geklärt, wie die Touringmaschine am Ende entscheidet, ob das Wort in der Sprache ist oder nicht. Ja, das ist ein ganz
- wichtiger Punkt, den gucken wir uns erst am Ende dieser Simulation hier an. Jetzt erstmal nur gucken, was macht die Touringmaschine überhaupt? Ja, in diesem
- Fall äh wir befinden uns am Anfang in diesem Zustand, im Startzustand, ja, wir lesen ein A. Äh, dann können wir diesen Übergang hier nehmen, der sagt, äh, wenn
- du ein A liest, dann schreib ein B und geh nach rechts und geh in diesen Zustand. Und das machen wir jetzt mal. Wir schreiben ein B, gehen einen Schritt
- nach rechts und jetzt sind wir in diesem Zustand. So, was tun wir jetzt? Jetzt lesen wir ein B. Sind in diesem Zustand und lesen ein B. Welchen Übergang können
- wir dann nehmen? Können diesen Übergang hiernh? Ja, wenn wir ein B lesen, schreiben C und gehen nach links. Okay, machen wir das so. Wir haben in C
- geschrieben, sind nach links gegangen und jetzt sind wir in diesem Zustand. Ja, und wir merken schon, das ist nicht so wie mit endlichen Automaten. Ja, wir
- laufen nicht von links nach rechts durch. Ja, wir können auch wieder nach links zurückgehen und wir können auch das Wort ändern. So, jetzt befinden wir
- uns also hier, lesen ein B, dann können wir diesen Übergang hier nehmen, ja, von hier nach da. An diesem Übergang, also hier, das steht an dieser Kante hier
- dran. Wenn wir ein B lesen, schreiben Leerzeichen und gehen nach links. Ja, das machen wir jetzt mal. Schreiben hier ein Leerzeichen hin und gehen einen
- Schritt nach links. Nun befinden wir uns also hier. Und jetzt stellen wir fest, okay, in diesem Zustand, wir lesen ein Leerzeichen,
- aber es gibt ja hier gar keinen Übergang, der sagt, wenn du ein Leerzeichen liest, mach folgendes. Ja, es gibt hier ein Übergang, ja, zu sich
- selbst, wenn wir ein B lesen oder wenn wir ein A lesen, aber wenn wir in diesem Zustand sind und ein Leerzeichen lesen oder genauso wenn wir ein C lesen,
- gibt's keine Anweisung. Und das bedeutet, die Touringmaschine hält hier an. Ja, wenn sie keine wenn sie keinen Übergang für ein Eingabesymbol hat, dann
- hält sie an. Das heißt, sie befindet sich jetzt in einer Stoppkonfiguration und wenn sie anhält, dann wird geguckt, ist das ein akzeptierender Zustand? Und
- das ist es in diesem Fall. Ja, in diesem Fall wird also das Eingabewort akzeptiert, denn der Ablauf der Touringmaschine hat am Ende hier in
- einem akzeptierenden Zustand gestoppt. Und deswegen ist das Wort ABC in der von dieser Touringmaschine erkannten Sprache nennen wir jetzt mal L. Ja, jetzt haben
- wir also gesehen, wie die Touringmaschine ein Wort akzeptieren kann. Ja, nämlich genau dann, wenn wir dieses Wort darauf schreiben, in diese
- Startkonfiguration gehen und sie dann am Ende in einer akzeptierenden, also ja, in so einem äh rosa Zustand hier stoppt. Wie kann sie ein Wort
- verwerfen? wäre die nächste Frage. Ja, als Beispiel fürs Verwerfen gucken wir uns mal das Wort ACC an. Also, wir beginnen mit dem Wort ACC. Ja, wieder
- Startkonfiguration. Das heißt, das ganze Band ist leer, außer irgendwo steht ACC und wir stehen auf dem äh ganz linken Symbol.
- Dann gucken wir wieder, was passiert. Als erstes gehen wir diesen Übergang hier. A wird durch B ersetzt und wir gehen nach rechts. So, dann sind wir
- hier. Jetzt lesen wir ein C. Hier steht C wird durch ein Blank ersetzt und wir gehen nach rechts und bleiben in diesem Zustand. So, haben das C durch Blank
- ersetzt, gehen nach rechts und wir bleiben in diesem Zustand. Und jetzt haben wir wieder dieselbe Situation. Wir lesen wieder ein C in
- diesem Zustand, also wieder durch ein Blank ersetzen und nach rechts gehen. Dann sind wir in dieser Situation. Und jetzt stehen wir hier in diesem Zustand,
- lesen ein Blank, ein Leerzeichen, aber es gibt keinen Übergang von hier für ein Leerzeichen. Ja, es gibt ein Übergang für ein C, wenn wir C lesen, es gibt
- auch einen Übergang für ein A und für ein B, aber es gibt keinen Übergang, der von hier losgeht, bei dem wir ein Blank lesen. Das heißt auch wieder, die
- Touring Maschine hält an. Diesmal hält sie aber an in einem Zustand, der kein akzeptierender Zustand ist. Der hier hat keinen pinken Kringel, ist kein
- Endzustand. Also wir nennen sie jetzt nicht mehr Endzustände, nennen sie jetzt akzeptierende Zustände bei Touring Maschinen. Ja, dann
- hält sie also hier an. Der Zustand ist nicht akzeptierend. Das bedeutet das Wort ist nicht in der Sprache. Okay, das war ja einfach. könnte man sich jetzt
- denken, ja, wenn wir wir lassen die Touringmaschine laufen und irgendwann hält sie an und wenn sie wenn es ein akzeptierender Zustand ist, dann ist das
- Wort in der Sprache und wenn es ein nicht akzeptierender Zustand ist, dann ist es nicht in der Sprache. Ja, ist ja ganz einfach, könnte man denken, aber
- das ist noch nicht die ganze Wahrheit, denn wir haben hier, also das es gibt zwei Punkte, die ich jetzt erwähnen muss. Äh zum einen eine Touringmaschine
- muss gar nicht immer anhalten. eine Touringmaschine, die könnte auch in eine Endblusschleife geraten. Ja, die könnte weiß nicht gibt's das hier irgendwo?
- Ich sehe jetzt hier keine Möglichkeit, aber es könnte ja theoretisch sein, dass sie so eine Anweisung kriegt, wie wenn du ein Blank liest, dann schreib auch
- wieder ein Blank hin und bleibe im selben Zustand und beweg dich nicht. Ja, dann wird sie es immer und immer wieder tun. Sie würde gar nicht mehr anhalten.
- In einem solchen Fall, also wenn die Turmaschine nicht anhält, dann akzeptiert sie ebenfalls das Wort nicht. Ja, dann ist das Wort auch nicht in der
- Sprache. Ist aber immer noch nicht ganz die Wahrheit, denn diese Touringmaschine hier, die war deterministisch. Die hatte immer nur eine einzige Möglichkeit einen
- Zustandsübergang zu machen. Ja, wenn wir uns das noch mal angucken, wenn wir in diesem Zustand hier sind, wenn wir ein B lesen, können wir nur diesen Übergang
- nehmen. Wenn wir ein A lesen, nur diesen hier. Und für ein C und ein Blank gab's keinen. Ja, von diesem Zustand hier genauso. Für ein C gibt's nur diesen.
- Für B und A gibt's nur diesen Übergang. Für ein Blank gibt's keinen. Ja. Äh und hier auch für B, C und Blank gibt's nur einen Übergang. Für ein A
- gibt's gar kein, aber es war hier nirgends der Fall, dass die Touringmaschine mehrere Möglichkeiten hatte, sich zu entscheiden. Das heißt,
- das hier ist eine deterministische Maschine. Da kann man es tatsächlich Akzeptanz und nichtakzeptanz genauso beschreiben, wie wir das hier gemacht
- haben. Wenn es eine nichtdeterministische Maschine gewesen wäre, ja, wenn die sich irgendwo entscheiden könnte, dann ist es wieder
- dasselbe Prinzip wie bei den wie es bei den Deas und bei den Neas war. Ja. äh eine nichtdeterministische Touringmaschine, die akzeptiert dann,
- wenn es mindestens einen Lauf gibt, der akzeptiert. Ja, also wenn sie sie wenn die Entscheidung irgendwie so treffen könnte, dass sie akzeptiert, dann wird
- das Wort akzeptiert. Äh, da können dann auch ganz viele andere Läufe bei sein, die in der nicht akzeptierenden Stoppkonfiguration enden oder die
- unendlich lange laufen. Ja, solange einziger Lauf äh in einer akzeptierenden Stoppkonfiguration hält, ist das Wort dann in der Sprache. Ja, das ist noch
- mal die Schwierigkeit bei den nichtdeterministischen Touringmaschinen. So und um jetzt noch mal zurückzukommen zur Chomski Hierarchie, ja, die
- Touringmaschinen sind also die Werkzeuge für die Touring erkennbaren Sprachen. Und die sind die bekommen das Symbol L0. Ja, die Sprachklasse L0, das sind die
- Touring kennbaren Sprachen. Und das ist eine Sprachklasse, die ist deutlich größer als z.B. für die kontextfreien Sprachen. Ja, die Touring Maschinen
- Sprachen, die Touring erkennbaren Sprachen, die kann man sich so vorstellen als, na, jede Sprache, die die man mit irgendeinem Computerprogramm
- erkennen könnte. Ja, also wir erinnern uns erkennbare Sprachen, die konnten ja nicht mal feststellen, ob ein Wort von der Form a hoch n b hoch n ist. Ja, und
- Kontextfreie Sprachen, die konnten das zwar, aber konnten dann nicht feststellen, dass es von der Form a hoch n, b hoch n, c hoch n ist. Ja.
- äh Touring erkennbar Sprachen, die können das alles, die können sogar noch viel mehr Touring äh Touring Maschinen, die könnten erkennen, keine Ahnung, ist
- die, wenn ich da eine Zahl hinschreibe, ist die Zahl eine Primzahl z.B. Ja, selbst dafür gibt es Touring Maschinen, die das dann mit so einem Zustands
- Grafen hier äh lösen. Also, die die können tatsächlich deutlich mehr als man im ersten Moment annimmt. Ja, wenn man nur sieht, okay, die haben wieder ein
- paar Zustände, die können jetzt auch nach links gehen und stehen bleiben und die können auch hier sich irgendwelche Informationen zwischenpeichern. Aber
- tatsächlich reicht das schon schon aus, um eigentlich alles zu tun, was ein Computer auch könnte. Man kann quasi richtig programmieren, kann dann
- Programme schreiben, die mir alles berechnen und die dann, na ja, wie gesagt, eben von einer Zahl z.B. prüfen, ist es eine Primzahl oder ist es eine
- zweierpotenz oder was auch immer, ja, was diese schwächeren Automatenmodelle hier nicht können. Deswegen sind Touring Maschinen deswegen haben die eine
- besondere Bedeutung. Und hier in diesem Video haben wir jetzt erstmal nur geklärt, wie man sie zum Erkennen von Sprachen benutzt. Ja, mit Eingabwort,
- also wir kriegen ein Eingabewort und sagen dann am Ende akzeptiert oder nicht. Ja, Touring Maschinen können auch noch verwendet werden, um Funktionen zu
- berechnen. Ja, Funktionen berechnen, das heißt, wir kriegen irgendein Eingabewort und die Ausgabe ist nicht nur ja oder nein, also ist in der Sprache oder ist
- nicht in der Sprache, sondern die Ausgabe ist wieder ein ganzes Wort. Das ist auch noch mal ein interessantes Thema, passt aber jetzt zeitlich auch
- nicht mehr hier in dieses Video. Deswegen belassen wir es erstmal soweit hierbei. Also dann vielen Dank fürs Zuschauen und bis zum nächsten Mal.