Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Turingmaschine - Einfach erklärt | Simplexity
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 83 Zeilen
- 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
- so wir haben hier unser arbeitsband auf diesem arbeitsband steht eine Eingabe und wir haben einen schreiblesekopf der sich in einem
- bestimmten Zustand befindet und dabei die Eingabe liest der schreiblesekopf kann hierbei drei Aktionen durchführen er kann einmal ein neues Symbol
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- über und gehen nach links heißt unser schreiblesekopf befindet sich jetzt hier nach diesem Schritt dann geht der schreiblesekopf wieder ganz nach links
- 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
- 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
- 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
- Symbol hier durch ein anderes Zeichen wie z.B a ersetzen hierbei ist es immer noch unbekannt ob ein deterministischer LBA äquivalent zu einem
- nichtdeterministischen LBA ist aber eine nichtdeterministische toolingmaschine und eine deterministische toolingmaschine sind äquivalent heißt zu
- jeder nichtdeterministischen gibt es auch eine deterministische toolingmaschine die NTM und DTM kann man sich ähnlich wie einen dea oder NEA
- 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
- Übergang haben genau wie unsere anderen automatenmodelle kann man auch die tingmaschine grafisch darstellen wir wollen jetzt mit unserer tingmaschine
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- ein X ersetzt und werden dann in irgendeinem Zeichen stehen geblieben für jede Typ Einsprache existiert ein entsprechender LBA der diese Sprache
- 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
- Typ nullsprache existiert eine entsprechende tingmaschine die diese akzeptiert als jede Typ nullsprache kann von einer Tring Maschine akzeptiert
- 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
- 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
- die entscheidbar sind und die Typ einprachen sind hierbei eine Teilmenge von den entscheidbaren Typ nullsprachen und die entscheidbaren Sprachen sind
- eine Teilmenge von den semientscheidbaren Sprachen bzw den Typ Null Sprachen entscheidbar bedeutet das dass es für diese Sprache eine
- 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
- 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
- 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
- Schleife geraten als die tingmaschine wde unendlich lang rechnen und deswegen sind die entscheidbaren n eine Timing von den semi entscheidbaren Sprachen
- 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
- abschlusseigenschaften von den Typ 1 und Typ Null Sprachen anschauen die Klasse der Typ 1 Sprachen bzw den Kontext sensitiven Sprachen ist unter allen
- bullchen Operatoren also Vereinigung Schnitt und Komplement abgeschlossen und auch unter Produkt Stern und inversen homomorphismen also das einzige unter
- was die Typ ein Sprachen nicht abgeschlossen sind sind die normalen homomorphismen und die Typ nullsprachen bzw die rekursiv aufziehbaren oder
- semientscheidbaren Sprachen sind unter allen Operatoren außer dem Komplement abgeschlossen und wir können uns noch die entscheidbarkeiten zu den Typ 1 und
- 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
- alle anderen entscheidbarkeitsprobleme sind unentscheidbar und für die Typ nullsprachen sind alle Probleme also auch das wortproblem unentscheidbar das
- liegt daran dass es Typ null gibt die seie entscheidbar aber nicht entscheidbar sind also es gibt ein Wort womit die tmaschine in eine
- 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
- 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
- coroda Normalform wenn alle Regeln von der Form variable nach Terminal variable nach variable variable nach zwei Variablen oder zwei variaableen nach
- 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
- können jede Typ 1 Grammatik in eine Grammatik in coroder Normalform umformen
Zum Nachlesen
TuringmaschineEine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach …
Linear beschränkte TuringmaschineEine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) in der Theoretischen Informatik ist eine Turingmaschine, die den Bereich des …
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …
Wortproblem (Berechenbarkeitstheorie)Für die Chomsky-Hierarchie ist bekannt: Das Wortproblem für Typ-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar. Das Wortproblem für Typ-1 …