Turingmaschine - Einfach erklärt | Simplexity
Simplexity
https://www.youtube.com/watch?v=yaQ_1PrTkFw

Transkript (automatisch erstellt)

0:00 weiter geht's mit der tingmaschine das ein weiteres Maschinenmodell mit dem es uns möglich ist alle Typ nullsprachen zu erkennen eine tingmaschine funktioniert
0:08 so wir haben hier unser arbeitsband auf diesem arbeitsband steht eine Eingabe und wir haben einen schreiblesekopf der sich in einem
0:16 bestimmten Zustand befindet und dabei die Eingabe liest der schreiblesekopf kann hierbei drei Aktionen durchführen er kann einmal ein neues Symbol
0:24 schreiben heißt man könnte auch z.B dieses e durch einen anderen Buchstaben ersetzen dann kann den Zustand wechseln und die Position des schreiblesekopfs
0:33 kann um ein Feld nach links oder rechts geändert werden oder kann auf demselben Feld stehen bleiben heißt der schreiblesekopf würde hier erstmal ein E
0:40 einlesen könnte dann nach rechts gehen und würde dann das i einlesen und wenn er dann bei i ist könnte dann genauso wieder nach links zu e gehen die ting
0:49 Maschine ist als sie Tupel definiert wir haben einmal Z Sigma Gamma Delta Z0 blank und e Z sind wir immer unsere Zustände Sigma ist das Endliche Alphabet
1:00 GMA ist dann das bandalphabet dieses Alphabet enthält alle Zeichen die auf dem Band stehen können dann haben wir Delta unsere übergangsfunktion die ist
1:09 diesmal so definiert wir haben z K Gamma nach Z K Gamma K lrn für eine deterministische Turing Maschine und für eine nichtdeterministische Turing
1:19 masaschine haben wir z Kreuz Gamma geht nach P von Z kuz GMA kuz lrn heißt unsere übergangsfunktion sieht so aus wir haben einen Zustand in dem wir uns
1:28 befinden und ein Zeichen dass wir einlesen das auf dem Band steht und dann können wir in einen neuen Zustand gehen oder im gleichen Zustand bleiben dieses
1:36 Zeichen entweder stehen lassen oder es durch ein anderes Zeichen ersetzen und in eine Richtung gehen nämlich entweder l für links R für rechts und n für
1:44 neutral dann ist Z0 wie immer unser Anfangszustand und das was jetzt neu dazu kommt ist das leerymbol bzw das blank Symbol das ist das Zeichen das
1:53 sich links und rechts von unserer Eingabe befindet damit wir wissen wo unsere Eingabe anfängt und endet da wir eine endlich lange Eingabe auf einem
2:01 unendlich langen Band haben dafür können wir uns jetzt noch ein Beispiel anschauen z.B haben wir jetzt hier eine tmaschine die den Input bitweise
2:09 invertiert hei wir haben als Eingabe eine Binärzahl auf dem Band und wollen hier bei jede 0 und 1 invertieren unsere ting masaschine ist so definiert wir
2:18 haben die Zustände Z0 Z1 Z2 das Alphabet 01 das bandalphabet 01 blank Delta Z0 blank und Z2 als nzustand unsere über Funktion ist so
2:30 definiert wenn wir in Z0 eine 0 einlesen bleiben wir in Z0 schreiben eine 1 und gehen nach rechts heißt wirersetzen die Null die wir erlesen durch eine 1 und
2:40 wenn wir eine 1 lesen ersetzen wir die ein durch eine ull und gehen auch nach rechts und das machen wir sol lang bis wir dann am Ende unserer Eingabe
2:47 angekommen sind also ein blank einlesen wenn wir das blank einlesen gehen wir in Z1 über und gehen nach links und für jede 0 und 1 die wir dann einlesen
2:55 lassen wir die 0 und 1 stehen und gehen nach links bis wir dann wieder am Anfang von unserer Eingabe sind also ein blank einlesen dann gehen wir in den Zustand
3:03 Z2 über und akzeptieren das Wort weil wir im nzustand sind diese Übergänge bräuchten wir jetzt nicht unbedingt um unseren Input bitweise zu invertieren
3:12 durch diese wird nur dafür gesorgt dass sich der schreiblesekopf wieder am Anfang der Eingabe befindet wir haben jetzt z.B hier die Binärzahl 1 10 10 am
3:21 Anfang befindet sich unser schreiblesekopf am Anfang des Wortes in Z0 dann lesen wir eine 1 ein heißt wir gehen einen Schritt nach rechts und
3:29 ersetzen die ein durch eine Null dann lesen wir eine ein ersetzen die 1 wieder durch eine ull und gehen einen Schritt nach rechts und das machen wir dann
3:35 solange bis wir am Ende des Inputs angekommen sind also bis wir beim blank Symbol sind wenn wir dann das blank Symbol einlesen gehen wir den Zustand Z1
3:43 über und gehen nach links heißt unser schreiblesekopf befindet sich jetzt hier nach diesem Schritt dann geht der schreiblesekopf wieder ganz nach links
3:50 an den Anfang der Eingabe und befindet sich dann in Z2 und hat den Input invertiert kommen wir jetzt noch zum linearbeschränkten Automaten bzw LBA ein
4:01 LBA ist eine trwingmaschine die nur auf der Eingabe arbeiten kann heißt wir haben jetzt hier unser Band und hier unsere Eingabe und die ting masaschine
4:08 kann nur auf dieser Eingabe arbeiten und dar diese niemals verlassen heißt eine normale tingmaschine dürfte auch die Eingabe verlassen und z.B auch das blank
4:17 Symbol hier durch ein anderes Zeichen wie z.B a ersetzen hierbei ist es immer noch unbekannt ob ein deterministischer LBA äquivalent zu einem
4:25 nichtdeterministischen LBA ist aber eine nichtdeterministische toolingmaschine und eine deterministische toolingmaschine sind äquivalent heißt zu
4:33 jeder nichtdeterministischen gibt es auch eine deterministische toolingmaschine die NTM und DTM kann man sich ähnlich wie einen dea oder NEA
4:41 vorstellen heißt eine NTM hat mehrere Möglichkeiten und kann sozusagen den nächsten Übergang raten wie ein NEA und eine DTM darf nur einen möglichen
4:49 Übergang haben genau wie unsere anderen automatenmodelle kann man auch die tingmaschine grafisch darstellen wir wollen jetzt mit unserer tingmaschine
4:56 die Funktion x nach X + 1 berechnen heißt wir kriegen als Input eine Binärzahl und wir wollen die gleiche Binärzahl mit 1 addieren und auf dem
5:05 Band ausgeben in Z0 lassen wir unsere Eingabe so wie sie ist und bewegen unseren schreiblesekopf nach rechts heißt wir bewegen den schreiblesekopf so
5:14 lang nach rechts bis wir die gesamte Eingabe gelesen haben wenn wir dann das blank Symbol lesen gehen wir nach links und gehen in den Zustand Z1 über und
5:21 solange wir dann in Z1 eine 1 lesen ersetzen wir die 1 durch eine Null und gehen nach links heißt wenn jetzt unsere Eingabe so aussehen würde wir haben 1
5:29 ein 1 1 1 und darauf wollen wir jetzt ein addieren wenn wir jetzt ein addieren würde die Binärzahl so aussehen heißt wir müssen jede ein durch eine 0
5:38 ersetzen bis wir dann beim blank sind und das blank Symbol ersetzen wir dann durch eine 1 heißt in dem Fall hätten wir jetzt kein LBA vorliegen da wir ja
5:45 die Eingabe verlassen und ein blank Symbol ändern wenn wir jetzt diese Binärzahl hier hätten würden wir erstmal diese ein hier durch eine Null ersetzen
5:52 und nach links gehen dann würden wir eine Null einlesen heißt wir würden diesen Übergang hier gehen also ersetzen wir unsere Null durch eine ein und gehen
6:00 nach links und jede weitere Null oder ein die wir einlesen lassen wir so wie sie sind und gehen nach links bis wir dann wieder am Anfang der Eingabe sind
6:08 also das blank Symbol einlesen und dann gehen wir in den nzustand he unsere radierte Binärzahl würde dann so aussehen und dann können wir jetzt noch
6:15 eine tingmaschine für die Sprache L = A hoch n B h n c h n mit n aus n anschauen die tingmaschine funktioniert so dass wir ein Z0 starten und das erste a das
6:25 wir einlesen durch ein X ersetzen und nach rechts gehen heißt wenn wir jetzt z.B die Eingabe a a a BBB C CC hätten wenden wir erstmal das erste a hier
6:34 durch ein X ersetzen die anderen a die wir einlesen lassen wir erstmal so wie sie sind und gehen nach rechts bis wir dann ein B einlesen das erste B das wir
6:43 einlesen ersetzen wir dann wieder durch ein X und gehen nach rechts und die anderen BS die wir einlesen lassen wir wieder so wie sie sind und gehen nach
6:49 rechts und das machen wir dann bis wir ein C einlesen das erste C wird dann wieder durch ein X ersetzt und dann gehen wir wieder rechts durch die CS bis
6:56 wir dann beim blank Symbol angekommen sind mit dem geh wieder nach links und in Z4 lassen wir alle Eingaben auf dem Band so wie sie sind und gehen komplett
7:04 wieder nach links an den Anfang zurück bis wir dann das blank einlesen und gehen dann wieder nach rechts in den Startzustand dann werden wir jetzt ein X
7:11 einlesen das lassen wir einfach so wie es ist und das erste a das wir dann wieder einlesen markieren wir dann wieder mit einem X das A und das X
7:19 lassen wir wieder und das erste B das wir dann wieder einlesen wird dann wieder mit einem X ersetzt und das erste C das wir dann wieder einlesen wird dann
7:26 auch wieder mit ein X markiert heißt die tingmaschine funktioniert so dass wir immer ein a ein B und ein C miteinander matchen indem wir alle Zeichen durch ein
7:34 X ersetzen und damit dann unser Wort am Ende akzeptiert wird dürfen am Ende nur x stehen und dann können wir den nendzustand gehen denn wenn wir jetzt
7:42 alle a BS und CS durch ein X ersetzt haben würde unsere Eingabe so aussehen unser schreiblesekopf befindet sich hier am Anfang und er würde jetzt durch diese
7:51 Schleife hier komplett nach rechts gehen bis er wieder am Ende der Eingabe ist heißt bis er hier steht dann ein blank einliest und dann geht er in den
7:58 Endzustand wenn sich unser Wort aber nicht in der Sprache befindet heißt die Anzahl a BS und CS nicht gleich ist hätten wir irgendein Zeichen nicht durch
8:06 ein X ersetzt und werden dann in irgendeinem Zeichen stehen geblieben für jede Typ Einsprache existiert ein entsprechender LBA der diese Sprache
8:13 akzeptiert heißt diese Sprache hier L = A n B n C n ist von Typ 1 da diese tmaschine hier ein LBA ist da wir nur auf der Eingabe arbeiten und für jede
8:23 Typ nullsprache existiert eine entsprechende tingmaschine die diese akzeptiert als jede Typ nullsprache kann von einer Tring Maschine akzeptiert
8:31 werden aber nicht unbedingt auch von einem LBA und außerdem wird eine Sprache als entscheidbar bezeichnet wenn es hier für eine entsprechende Turing Maschine
8:38 gibt die auf jeder Eingabe hält denn wir müssen bei unserer chumpsk hierchie wieder die Typ Null Sprachen aufteilen den es gibt einmal die Typ nullsprachen
8:46 die entscheidbar sind und die Typ einprachen sind hierbei eine Teilmenge von den entscheidbaren Typ nullsprachen und die entscheidbaren Sprachen sind
8:54 eine Teilmenge von den semientscheidbaren Sprachen bzw den Typ Null Sprachen entscheidbar bedeutet das dass es für diese Sprache eine
9:00 tingmaschine gibt die auf jeder Eingabe hält heiß wir kriegen ein Wort in unsere tingmaschine die tingmaschine berechnet ob das Wort in der Sprache ist und gibt
9:09 entweder ja aus wenn das Wort in der Sprache ist oder nein wenn es nicht in der Sprache ist und SEM entscheidbar bedeutet dass es für das Wort entweder
9:15 ja ausgibt wenn das Wort in der Sprache liegt aber wenn das Wort nicht in der Sprache ist ist die tingmaschine undefiniert bzw kann in eine endlos
9:23 Schleife geraten als die tingmaschine wde unendlich lang rechnen und deswegen sind die entscheidbaren n eine Timing von den semi entscheidbaren Sprachen
9:32 denn es gibt z.B semientscheidbare Sprachen die aber nicht entscheidbar sind wie z.B das halteproblem und dann können wir uns noch die
9:38 abschlusseigenschaften von den Typ 1 und Typ Null Sprachen anschauen die Klasse der Typ 1 Sprachen bzw den Kontext sensitiven Sprachen ist unter allen
9:46 bullchen Operatoren also Vereinigung Schnitt und Komplement abgeschlossen und auch unter Produkt Stern und inversen homomorphismen also das einzige unter
9:56 was die Typ ein Sprachen nicht abgeschlossen sind sind die normalen homomorphismen und die Typ nullsprachen bzw die rekursiv aufziehbaren oder
10:04 semientscheidbaren Sprachen sind unter allen Operatoren außer dem Komplement abgeschlossen und wir können uns noch die entscheidbarkeiten zu den Typ 1 und
10:11 Typ Null Sprachen anschauen das wortproblem für Typ 1 ist entscheidbar da es ja eine Teilmenge von den entscheidbaren Typ Null Sprachen ist und
10:20 alle anderen entscheidbarkeitsprobleme sind unentscheidbar und für die Typ nullsprachen sind alle Probleme also auch das wortproblem unentscheidbar das
10:28 liegt daran dass es Typ null gibt die seie entscheidbar aber nicht entscheidbar sind also es gibt ein Wort womit die tmaschine in eine
10:34 endlusschleife Gerät bzw unendlich lang rechnet und damit kann das wortproblem nicht entschieden werden da es ja nicht klar ist ob das Wort in der Sprache
10:41 liegt oder nicht und aßerdem gibt es auch noch eine Normalform für die Type Einsprachen nämlich die coroda Normalform eine Grammatik g ist in
10:49 coroda Normalform wenn alle Regeln von der Form variable nach Terminal variable nach variable variable nach zwei Variablen oder zwei variaableen nach
10:58 zwei Variablen sind und für jede Typ 1 Grammatik mit ePS ist kein Element von L von G existiert auch eine entsprechende Grammatik in coroda Normalform heißt wir
11:08 können jede Typ 1 Grammatik in eine Grammatik in coroder Normalform umformen