Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Turing-Maschinen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
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.
Zum Nachlesen
TuringmaschineEine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach …
Nichtdeterministische TuringmaschineEine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine …
Automat (Informatik)Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.
Linear beschränkte TuringmaschineEine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) in der Theoretischen Informatik ist eine Turingmaschine, die den Bereich des …