Turing-Maschinen
NLogSpace
https://www.youtube.com/watch?v=y71nsciUW1c

Transkript (automatisch erstellt)

0:01 So, in diesem Video soll es um Touringmaschinen gehen. Ich möchte erklären, was Touringmaschinen sind äh und auch ein bisschen über die
0:08 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
0:17 britischer Mathematiker und Informatiker, der wirklich sehr großen Einfluss auf die ja die Anfänge der theoretischen Informatik hatte in den ja
0:28 40ern, 50ern, glaube ich, ähm war auch beteiligt an der Entschlüsselung der Enigma, ja, der deutschen Verschlüsselungsmaschine,
0:37 diese Schreibmaschine. Ähm ja und deswegen hier einmal mit Foto, weil er wirklich für die theoret theoretische Informatik extrem wichtig
0:47 ist. Ja, und natürlich die Touringmaschinen sind auch nach ihm benannt. Ja, die Touringmaschinen, die werden wir hier noch mal die Chomski
0:54 Hierarchie, ja, die werden wir jetzt hier erstmal einordnen. Ähm, die Touringmaschinen sind ja auch nur ein äh wieder ein Werkzeug, um Sprachen zu
1:03 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
1:11 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.
1:19 Später auch Kellerautomaten und kontextfreie Grammatiken. So sind die Touringmaschinen na ja ein deutlich stärkeres Modell. Ja,
1:28 und hier äh habe ich schon hingeschrieben, L0 heißen die Touring erkennbaren Sprachen. Äh die das zugehörige Automatenmodell, das sind die
1:38 Touringmaschinen. Ja, die Touringmaschinen, die gehören also hierhin. Mit denen beschäftigen wir uns jetzt. Man könnte sagen, äh, die
1:46 Touringmaschinen, die erinnern vielleicht ein bisschen an endliche Automaten. Ja, sie haben auch Zustände, Zustandsübergänge und so weiter, aber
1:53 die Touringmaschinen, die sind der Versuch dem ganzen deutlich mehr Mächtigkeit zu geben oder sage ich mal mehr Möglichkeiten. Ja, die endlichen
2:03 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
2:10 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
2:17 begrenzter Weise sich was an Information merken. Ja, aber die Touringmaschinen, die werden jetzt deutlich mächtiger und zwar funktioniert das so. Die
2:27 Touringmaschinen, die haben jetzt ein sogenanntes Eingabeband. Das kann man sich vorstellen wie ein unendlich langes Band. Ja, von nach links und rechts ist
2:37 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
2:46 Eingabewort drauf. Ja, und die Touringmaschine, die hat auch einen Lese und Schreibkopf. Der steht am Anfang auf dem ersten
2:56 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
3:06 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
3:14 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
3:23 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
3:34 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
3:42 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
3:50 da schreiben sogar. her, die darf Symbole verändern, die darf sogar da, wo das Eingabewort steht, das darf sie überschreiben und irgendwann
3:58 äh soll sie sich dann irgendwann entscheiden. Ja, dann irgendwann, wenn sie meint, okay, jetzt habe ich genug rumgerechnet oder was auch immer, dann
4:05 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
4:13 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
4:22 Lesekopf, der zeigt auf ein Feld in diesem Fall, dieses Feld hier. Sie liest dieses Eingabesymbol oder die liest das Symbol, was da gerade
4:31 in diesem Feld steht. Ja, und sie befindet sich ja gleichzeitig auch noch in einem Zustand. Sie ist ja eine zustandbasierte Maschine, sowie endliche
4:40 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
4:51 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
5:05 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
5:15 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
5:23 Wiederholen, wir lesen ein Symbol und wir befinden uns in einem Zustand. Ja, und aus dieser Kombination, ja, diese beiden
5:30 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
5:39 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
5:49 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
5:57 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
6:04 mal ein komplettes Beispiel, ein kompletten Ablauf einer Touringmaschine auf einem Eingabewort. Ja, dafür habe ich hier schon mal so eine
6:12 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
6:21 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
6:29 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
6:40 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
6:48 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
6:57 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
7:05 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
7:17 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
7:25 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
7:33 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
7:42 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
7:51 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
7:57 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
8:08 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
8:18 Schritt nach links. Nun befinden wir uns also hier. Und jetzt stellen wir fest, okay, in diesem Zustand, wir lesen ein Leerzeichen,
8:27 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
8:36 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,
8:46 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
8:55 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
9:04 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
9:13 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
9:24 wir also gesehen, wie die Touringmaschine ein Wort akzeptieren kann. Ja, nämlich genau dann, wenn wir dieses Wort darauf schreiben, in diese
9:31 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
9:42 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
9:52 Startkonfiguration. Das heißt, das ganze Band ist leer, außer irgendwo steht ACC und wir stehen auf dem äh ganz linken Symbol.
10:02 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
10:11 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
10:22 ersetzt, gehen nach rechts und wir bleiben in diesem Zustand. Und jetzt haben wir wieder dieselbe Situation. Wir lesen wieder ein C in
10:30 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,
10:38 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
10:48 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
10:57 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
11:06 Endzustand. Also wir nennen sie jetzt nicht mehr Endzustände, nennen sie jetzt akzeptierende Zustände bei Touring Maschinen. Ja, dann
11:13 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
11:20 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
11:28 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
11:35 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
11:46 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?
11:56 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
12:03 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.
12:11 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
12:21 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
12:33 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
12:42 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.
12:52 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
13:03 gibt's gar kein, aber es war hier nirgends der Fall, dass die Touringmaschine mehrere Möglichkeiten hatte, sich zu entscheiden. Das heißt,
13:10 das hier ist eine deterministische Maschine. Da kann man es tatsächlich Akzeptanz und nichtakzeptanz genauso beschreiben, wie wir das hier gemacht
13:18 haben. Wenn es eine nichtdeterministische Maschine gewesen wäre, ja, wenn die sich irgendwo entscheiden könnte, dann ist es wieder
13:27 dasselbe Prinzip wie bei den wie es bei den Deas und bei den Neas war. Ja. äh eine nichtdeterministische Touringmaschine, die akzeptiert dann,
13:37 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
13:47 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
13:55 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
14:05 mal die Schwierigkeit bei den nichtdeterministischen Touringmaschinen. So und um jetzt noch mal zurückzukommen zur Chomski Hierarchie, ja, die
14:15 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
14:26 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
14:34 Sprachen, die Touring erkennbaren Sprachen, die kann man sich so vorstellen als, na, jede Sprache, die die man mit irgendeinem Computerprogramm
14:43 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
14:53 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.
15:01 ä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
15:10 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
15:19 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
15:28 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
15:36 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
15:45 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
15:54 zweierpotenz oder was auch immer, ja, was diese schwächeren Automatenmodelle hier nicht können. Deswegen sind Touring Maschinen deswegen haben die eine
16:03 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,
16:12 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
16:21 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
16:30 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
16:39 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.