YT YouTube2Text

YouTube2Text → Transcripts → Turingmaschinen und Typ-0-Sprachen

Turingmaschinen und Typ-0-Sprachen — Transcript

by Prof. Markus · 8,154 words · 1,383 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00touring maschinen sind die richtigen
0:03automaten zur erkennung von typ 0
0:06sprachen
0:06das hatte ich zumindest bisher behauptet
0:09und dann haben wir eine ganze menge über
0:10touring maschinen gelernt und über
0:12berechenbarkeit gelernt und über das
0:14alte problem genannt
0:15es wird zeit dass wir mal wieder zu den
0:17typen uhr sprachen zurückkommen und das
0:20wollen wir diesmal tun es geht um 20
0:22sprachen und touring maschinen und ich
0:24werde ihnen ganz genau zeigen wie die
0:26beiden zusammen hängen es wird auch noch
0:28ein paar kleine bemerkungen zur
0:30unscheinbarkeit geben die vielleicht
0:31auch ganz interessant sind aber das
0:33kommt gleich am anfang mein name ist max
0:36coacht willkommen zurück zur
0:37vorlesungsreihe formale sprachen und
0:40automaten der tu dresden
0:43kuhring mächtigkeit darüber hatte ich
0:45zuletzt gesprochen und ihnen im
0:48wesentlichen gesagt dass die touring
0:49maschine das mächtigste bekannte
0:51berechnungsmodell ist nicht das einzige
0:54mächtigste bekannte rechnet mutter es
0:56gibt viele berechnungsmodelle die alle
0:59ebenfalls touring mächtig sind und das
1:03ist in gewisser weise eine feste größe
1:05in der informatik und spielt für uns
1:07natürlich eine große rolle was nicht
1:09drin berechenbar ist wofür man keine
1:11touring maschine finden kann gilt
1:13dementsprechend als unberechenbar
1:16und ich hatte erwähnt es gibt sehr viele
1:18verschiedene touring mächtige dinge
1:20touring maschinen selbst natürlich in
1:22mehr als einer variante da hatte ich
1:26schon einiges darüber gesagt mehr band
1:28touring maschinen nicht deterministische
1:29touring maschinen und auch verschiedene
1:31andere kleinere variationen kann man
1:33sich anschauen
1:35natürlich sind auch alle echten
1:37programmiersprachen turin möchte ich das
1:39ist das mindeste was wir von einer
1:41programmiersprache erwarten selbst wenn
1:42sie sonst nicht besonders
1:44alltagstauglich vielleicht sein sollte
1:46sollte sie doch zumindest in der lage
1:48sein alle berechnungen auszudrücken
1:50die sprachen die ich hier übrigens liste
1:54wenn man hier lesen kann sind in der
1:57reihenfolge geordnet nach der anzahl
2:00ihrer wikipedia artikel in verschiedenen
2:03sprachen also ein großes maß an
2:05popularität von sprachen
2:08zumindest wenn man den internationalen
2:11dokumentations- stand in wikipedia als
2:14anhaltspunkt für popularität nimmt
2:17theoretische kalküle gibt es auch
2:19verschiedene die man in der mathematik
2:22ursprünglich noch bevor es die
2:23informatiker ab eigentlich schon
2:24betrachtet hat die prädikaten logik als
2:27ein wichtiges das lambda kalkül
2:30regressive funktionen verschiedener
2:32sparten auch die sind alle touren
2:33mächtig und manch anderes was eigentlich
2:36nicht als touring mächtig gedacht und
2:38entwickelt wurde zum beispiel das
2:40template system von c++ was eigentlich
2:42ein vor verarbeitungsschritt in der
2:44kompilierung von programm sein sollte
2:46und nicht etwa beliebige berechnungen
2:48durchführen muss noch dazu welche die
2:52vielleicht niemals terminieren sql auch
2:55das sicherlich nichts was unbedingt tui
2:57möchte ich sein müsste eine datenbank
3:00anfrage sollte normalerweise nicht ein
3:03komplexer software projekt
3:05implementieren sondern einfach eine
3:06antwort liefern agennix haben sich auch
3:09eingereiht in die c + + template reihe
3:13und manch anderes was größer als er
3:16unterhaltsam als ganz ernst gemeint ist
3:19okay dass also die touring mächtigkeit
3:21und wir haben gelernt dass das alte
3:23problem
3:24ein gutes beispiel für ein erstes
3:29unentschuldbares problem ist was gerade
3:31noch mit einer touring maschine erkannt
3:34werden kann aber nicht mehr entschieden
3:35werden kann das heißt die tour die
3:37maschine ist nicht mehr in der lage in
3:39jedem fall nach endlich vielen schritten
3:41das richtige ergebnis zu liefern sie
3:43kann höchstens noch sicherstellen dass
3:44sie in den fällen in denen das die
3:47antwort ja lautet nach endlich vielen
3:49schritten das herausfindet dass haben
3:50wir sehr entscheidend genannt wir hatten
3:54auch sonst verschiedene beispiele ja
3:56also ganz einfache sprachen wie zum
3:58beispiel hier die sprache der
4:00wiederholten wörter ist sind sicherlich
4:03entscheid bar und damit auch semi
4:05entscheid war da kann man algorithmen
4:07finden und auch touring maschinen das
4:08alte problem selbst ist immerhin noch
4:11sehr entscheidend also touring erkennbar
4:12das kompliment dieses problems dagegen
4:15ist das nicht
4:16da sehen wir auch semi entscheid barkeit
4:17ist ein asymmetrischer begriff ja wenn
4:19ich das problem umdrehe also ja und nein
4:21als antwort und vertauscht dann ändert
4:24sich die begrifflichkeit dann habe ich
4:26also ein problem bei dem ich die antwort
4:28nein nach endlich vielen schritten mit
4:31sicherheit feststellen kann aber nicht
4:32nur bedingt die antwort ja es gibt auch
4:34unentschuldbare probleme bei denen weder
4:36das problem selbst noch das kompliment
4:38semi entscheidbar sind das ist auch
4:41durchaus möglich aber wir wollen uns
4:43nicht ganz so weit ins esoterische wagen
4:45das reicht erst mal dass man diese
4:47wichtigen probleme erkennt für alles
4:49andere gibt es fortgeschrittene kurse in
4:51denen wir noch mehr über solche dinge
4:53reden
4:54okay das also die entscheid nochmals
4:56zusammengefasst und ich möchte jetzt an
4:58dieser stelle noch ein wichtiges kleines
5:00resultat ihnen mitteilen dass manchmal
5:02schon auch als fortgeschrittenes
5:03resultat gesehen wird aber eigentlich
5:05eine wunderbar einfache aussage ist die
5:08uns in der informatik auch gute dienste
5:10leistet damit kann man auch ein bisschen
5:12angeben
5:13als informatiker informatikerin wenn man
5:15spontan die unendlichkeit aller
5:18möglichen probleme feststellen kann
5:20mit hilfe dieses netten resultates
5:23verdanken
5:24können wir das einem forscher namens
5:27henry golden rice und dementsprechend
5:29ist es auch bekannt als the jam oder
5:32satz von was sagt der schöne satz von
5:35preis der schöne satz von reis sagt
5:37einfach an jede nicht triviale frage
5:40über die von einer touring maschine
5:42ausgeführte berechnung ist
5:44unentschuldbar
5:47warum ist das eine instrumentalversion
5:49naja weil jede nicht triviale frage ein
5:52bisschen vage ist was ist eine milliarde
5:54frage hier ist es wirklich mal so zu
5:57verstehen wie man das wort eigentlich
5:59verstehen sollte trivial ist etwas was
6:01überhaupt kein nachdenken erfordert ja
6:04in der forschung gibt es ja zuweilen die
6:09tendenz dinge zu real zu nennen die
6:12nicht allzu schwer zu sehen sind für
6:15jemanden der sich schon einige zeit mit
6:16dem thema beschäftigt hat so wollen wir
6:18das nicht verstehen hier sehen wir
6:19wollen wirklich trivial also
6:22es sollte wirklich etwas ganz extrem
6:24einfacher sein und alles andere alle
6:26fragen die wir über die berechnung einer
6:28touring maschine haben könnten
6:30die nicht extrem einfach sind in einem
6:33formellen sinne den ich ihnen gleich
6:35noch mit teile sind unentschuldbar
6:38das heißt der satz von reis sagt uns im
6:40wesentlichen grob zusammengefasst alles
6:43interessante ist unentschuldbar
6:46zumindest wenn man sich interessiert für
6:48das was eine touring maschine tut oder
6:50das was irgendein anderer formalismus
6:53tut der auch touring mächtig ist also
6:55dann können die touring maschinen auch
6:56genauso mit java ersetzen oder
6:58irgendeiner anderen programmiersprache
7:01und es würde ebenfalls natürlich geld
7:04wenn diese formalismen sind äquivalent
7:06okay ich mache mir noch ein bisschen
7:09formella sei eine eigenschaft von
7:13sprache die für manche touring
7:18erkennbare sprachen gilt und für manche
7:21touring erkennbare sprachen nicht geht
7:24das ist das was wir nicht triviale
7:26eigenschaft nennen würden also trivial
7:28sind die eigenschaften die immer gelten
7:31oder nie
7:32das ist trivial alles andere egal wie
7:34einfach es ist das vielleicht
7:36festzustellen ist nicht trivial sofern
7:38es eine tui maschine gibt die die
7:40eigenschaft nicht hat und eine andere
7:42die sie hat weiche vorsichtig sein muss
7:44es geht immer um eigenschaften von
7:46sprachen nicht von touring maschinen
7:47machine kann man ja auch relativ einfach
7:50darstellen und wir wollen aber nicht die
7:52eigenschaften dieser darstellung
7:54hinterfragen sondern wir wollen wissen
7:56was die berechnet und da gibt es eben
7:59viele nicht triviale eigenschaften
8:01wenn wir also eine nicht reale
8:03eigenschaft haben die möglicherweise war
8:06und möglicherweise falsch ist dann ist
8:09das folgende problem und entscheid bei
8:11eingabe eine tui maschine m
8:14ausgabe die antwort auf die frage hat
8:17die sprache dieser maschine die
8:20eigenschaft dass kann man beweisen ist
8:23nicht sehr schwierig in dem man es auch
8:25das alte problem reduziert also zeigt
8:27dass das alte problem gelöst werden
8:28könnte wenn man das lösen könnte für
8:30jede beliebige nicht triviale
8:32eigenschaft und
8:35das müssen wir aber nicht das reicht uns
8:37das mitzunehmen
8:38was wir aber machen wollen ist noch
8:40einmal kurz darüber sprechen wie man das
8:42korrekt anwendet und was man alles
8:44unmittelbar aus diesem ergebnis
8:46rausziehen kann hier sind paar beispiele
8:49für dinge die nicht egal sind zum
8:51beispiel ist das wort aber in der
8:54sprache die die tormaschine erkennt wo
8:56er ein scheinbar für ein ganz konkretes
8:58kurzes wort kennt die sprache touring
9:02maschinen keine wörter also ist die
9:04sprache leer wird alles abgelehnt und
9:06scheinbar denn es gibt touring maschinen
9:08bei denen ist die sprache leer es gibt
9:10andere bei denen es die sprache nicht
9:11leer also nicht triviale eigenschaft ist
9:14die sprache endlich ist die sprache
9:16regulären all das sind eigenschaften der
9:20erkannten sprache anna touring maschine
9:22der berechnung die sie ausführt und all
9:24diese eigenschaften sind unentschuldbar
9:26denn sie könnten verschiedene antworten
9:29haben aufpassen müssen wir eigentlich
9:31nur in ganz wenigen fällen die triviale
9:37eigenschaften oder eben eigenschaften
9:39der touring maschinen kodieren die gar
9:41nichts mit der berechnung zu tun haben
9:42zum beispiel könnte ich fragen hat die
9:44touring maschine mindestens zwei
9:45zustände
9:45das ist natürlich etwas was sie
9:47entscheiden können schauen sie die
9:48tormaschine an dann wissen sie es das
9:50ist aber eben keine sprache eigenschaft
9:52ihrer sprache sondern eine eigenschaft
9:54ihrer darstellung könnte vielleicht für
9:56die gleiche sprache auch wieder eine tui
9:57maschine finden die drei zustände hätte
10:00oder vier oder was auch immer
10:01und das hat also nichts mit abrechnung
10:05zu tun die ausgeführt wird eine andere
10:09eigenschaft die hier in dem fall trivial
10:11ist ist die eigenschaft oder die frage
10:15ob die sprache semi entscheidbar ist ja
10:18wir haben ja gerade gesagt jede sprache
10:20die eine tormaschine erkennen kann ist
10:22per definition semi entscheidbar also
10:24ist das trial
10:25das ist etwas was ich nicht fragen muss
10:27die antwort lautet immer ja das kann ich
10:28natürlich entstand aber alles andere
10:30egal welche frage zu stellen ist
10:32unentschuldbar und wie gesagt das gilt
10:35für alle touring mächtigen formalismen
10:37das gilt für sql anfragen das gilt für
10:40jegliche ist java programm c++ programm
10:43das gilt für alle
10:45für prädikaten logik
10:46als ein formalismus und so weiter und so
10:49fort also alle dinge die irgendjemand
10:52als touring mächtig feststellt haben die
10:54eigenschaft dass man fragen über die
10:56berechnung die sie ausführen oder die
10:59sprache die sie konkret erkennen nicht
11:01algorithmisch beantworten kann mit
11:04sicherheiten einführen ok und das ist
11:07sehr schön weil es erlaubt uns mit
11:10sicherheit auskunft zu geben über die
11:12entscheid beziehungsweise unhaltbarkeit
11:14von vielen vielen dingen in der
11:16informatik ohne dass wir uns mit den
11:18genauen beweisen beschäftigen müssen das
11:20ist so dieses das grundgefühl das sobald
11:22die mächtigkeit im spiel ist alles
11:24interessante und entscheidender wird ist
11:26formal richtig okay gut aber eigentlich
11:31sollte mein video von 20 sprachen
11:33handeln wir kommen aber nochmal fonds
11:36umsatz von reis zurück am ende natürlich
11:37weil und insofern diskutieren erstmal zu
11:42lang
11:44es geht los mit dem hauptteil des videos
11:4820 sprachen und boeing-maschinen wie
11:53genau hängen die zusammen das den gewiss
11:57beweisen wollen ist hier aufgeschrieben
12:01genau der folgende die typ 0 grammatiken
12:04erzeugen genau diejenigen sprachen die
12:06von anna touring maschine erkannt werden
12:09kann
12:10also das ist das was ich schon mehrfach
12:12behauptet hatte type-0 und touring
12:14erkennbar ist das gleiche und das wollen
12:16wir jetzt verstehen im detail und genau
12:19ins überlegen wieso das so ist und ich
12:23hoffe das hat doppelten nutzen zum einen
12:26natürlich dass wir etwas besser die
12:29sprachen und die grammatiken verstehen
12:31mit denen wir uns hier in diesem kurs
12:33beschäftigt haben und weiter
12:34beschäftigen und zum anderen dass wir
12:36auch mal sehen wie man im prinzip zeigt
12:39dass ein formalismus touring mächtig ist
12:41ja also ich hatte ja erwähnt alle
12:43möglichen formalismen sind als touring
12:44mächtig bekannt aber die hat man das
12:47denn überhaupt festgestellt
12:48und wir werden sehen das ist nicht so
12:49schlimm man kann das feststellen ich
12:51werde in diesem video für type-0
12:53grammatik machen das zeigen dass ihr
12:55turin mächtig sind
12:56und dass man mit ihnen beliebige
12:58berechnungen kodieren kann und das zeigt
13:02ihnen im prinzip die grundidee sie
13:03können das auch auf andere formalismen
13:06so anwenden und das kann ganz
13:09unterhaltsam sein je nachdem was man
13:10sich da heraus sucht die techno
13:15grammatiken sollen also die touring
13:17erkennbaren sprachen erzeugen wie können
13:18wir das machen natürlich haben wir hier
13:20wieder eine äquivalenz vor uns dieser
13:22diese behauptung hat zwei richtungen
13:24das heißt wir werden zeigen müssen dass
13:26man das was die type-0 grammatiken als
13:28sprache darstellen
13:29mit einer boeing maschine erkennen kann
13:31und umgekehrt dass man das was eine tui
13:33maschine erkennen kann mit einer
13:34geeigneten type-0 grammatik darstellen
13:36kann
13:36das wären getrennte teile seien in
13:38diesen beweis wenn uns das gelingt haben
13:41wir damit eine reihe von interessanten
13:44dingen festgestellt zum einen natürlich
13:46dass type-0 kamera ticken touring
13:49mächtig sind und berechnungen kodieren
13:51können obwohl sie eigentlich nur ganz
13:52einfach ersetzung regeln als grundlage
13:55haben
13:57wir haben außerdem gezeigt dass typ 0 in
13:59gewisser weise das ende der fahnenstange
14:01ist wenn es darum geht implementierbare
14:04formalismen zu beschreiben ich hatte ja
14:06schon eingangs gesagt als wir über
14:07sprachen geredet haben es gibt sehr
14:09viele sprachen aber es gibt nur eine
14:12beschränkte menge an grammatiken und man
14:14kann sich jetzt natürlich fragen die
14:16vielleicht kann ich ja noch mehr
14:16schaffen vielleicht ist grammatik nicht
14:18das richtige heran
14:19nicht die richtige herangehensweise für
14:21die darstellung von sprachen vielleicht
14:23gibt es jenseits von typ nur sparen noch
14:27andere die ich darstellen kann aber eben
14:31nicht mit irgendeiner grammatik auch
14:32nicht mit einer von kripo und in
14:34gewisser weise vereint dieses ergebnis
14:37diese vermutung und sagt uns denn alles
14:40was überhaupt implementierbar ist lässt
14:43sich auch mit type-0 grammatiken
14:44beschreiben und implementierbar heißt
14:47hier nicht einmal durch einen
14:48entscheider sondern unter umständen
14:49durch einen sehen wie entscheid natur
14:53ich kann man formal mathematisch auch
14:54andere sprachen beschreiben die nicht 50
14:56sind das ist klar haben wir hier auch
14:57schon gemacht
14:58wenn werden nicht dem entscheid bahre
15:00sprachen geschrieben haben aber das ist
15:03dann eben kein berechnungs formalismus
15:06der uns erlaubt in irgendeiner weise die
15:09wörter dieser sprache zu erkennen oder
15:12zu generieren sondern wir
15:14charakterisieren sind nur abstrakt
15:16mathematisch indem wir im reißen was in
15:18der sprache gehört und was nicht okay
15:21typ deutsch sprachen sind genau diesen
15:23entscheid bahn sprach und natürlich das
15:25wort problem für typen sprachen ist
15:26ebenfalls ein entscheid basim ihr
15:28entscheid war ja mit der touring
15:30maschine kann man alle würde die man
15:33erzeugen kann tatsächlich nach endlich
15:36vielen schritten erkennt aber falls ein
15:38wort nicht erzeugt werden kann dann kann
15:40es mir passieren dass die touring
15:41maschine ewig rechnet und es gibt kein
15:44programm in keiner programmiersprache
15:46das mit sicherheit in den fällen in
15:49denen etwas nicht durch eine type 0
15:51grammatik erzeugt werden kann
15:52nach etlicher zeit immer diese ausgabe
15:55erzeugen kann
15:57ok also viele viele interessante dinge
16:00die wir mit diesem ein ergebnis lernen
16:03können gut ich hatte schon erwähnt der
16:07beweis braucht zwei richtungen es gibt
16:09eine äquivalenz zu zeigen hier und ich
16:12teile das in zwei schritte auf erster
16:14schritt wenn eine sprache von einer typ
16:160 grammatik erzeugt wird dann kann sie
16:19auch von einer touring maschine erkannt
16:21werden
16:22wichtig hierfür eine beliebige typ 0
16:24grammatik findet man eine ganz genau
16:28passende touring maschine also für alle
16:33grammatik ich habe eine beliebig
16:34grammatik zu bearbeiten kann ich mir
16:36eine beliebige eine bestimmte touring
16:38maschine suchen die diese grammatik
16:40genau implementiert wenn mir das gelingt
16:41habe ich diesen ersten teil gezeigt
16:43zweiter zurück richtung wenn eine
16:46sprache von einer zugmaschine erkannt
16:47wird dann kann sie durch eine type 0
16:49grammatik erzeugt werden
16:51hier ist es genau umgekehrt wir müssen
16:53in der lage sein beliebige touring
16:55maschinen zu behandeln aber wir können
16:58uns aussuchen wie die grammatik aussehen
16:59sollen und müssen nur eine grammatik
17:02finden die für eine beliebige
17:04tormaschine geeignet ist
17:06ok deshalb also zwei richtungen weil die
17:08konstruktion einmal die konstruktion
17:10einer maschine ist und einmal einer
17:11grammatik ja okay wir beginnen mit der
17:14ersten 20 zu touring maschinen gegeben
17:18eine beliebige grammatik gesucht eine
17:20tormaschine die die genau gleiche
17:23sprache erkennt die die grammatik
17:25generiert wie können wir das schaffen
17:30ok im prinzip muss man sich jetzt eine
17:34implementierung überlegen das ist es ja
17:36was eine tui maschine codiert eine
17:37implementierten implementierung
17:39überlegen die die grammatikregeln einer
17:41type-0 grammatik nutzt um zu ermitteln
17:45ob ein bestimmtes wort in der sprache
17:47liegt oder nicht
17:48und das darf sogar einer nicht
17:50deterministisch implementierung sein wir
17:52haben ja gezeigt dass nicht
17:53deterministische touring maschinen auch
17:55keine größere ausdrucksstärke haben das
17:57heißt wir können uns sogar die
17:59vereinbarung erlaubt dass unsere touring
18:01maschine gerät was sie tun muss in jedem
18:04schritt wenn es manchmal nicht so ganz
18:05klar ist und sie können schon an dass es
18:07bei grammatiken natürlich so aussieht
18:08eine grammatik hat oft viele
18:10möglichkeiten wie sie ein wort erzeugen
18:13kann und es gibt in jedem schritt
18:14verschiedene besetzungen die man
18:16durchführen könnte es ist also sehr
18:18praktisch wenn man hier nicht
18:19deterministisch arbeiten darf weil man
18:22dann keinen mechanismus finden muss der
18:25zielgerichtet die richtige ersetzung
18:28entdeckt man kann einfach sagen wir
18:31neben einer und wenn die richtige dabei
18:33ist dann funktioniert das schon okay gut
18:37wie machen wir das jetzt ein zweites
18:39wichtiges element das wir uns noch klar
18:45machen müssen was grammatiken und thurk
18:47maschinen unterscheidet ist natürlich
18:50dass eine tormaschine ein wort als
18:54eingabe erhält und für das dann eine
18:56prüfung durch führt wer hat eine
18:58grammatik ein wort erzeugt das heißt sie
19:01beginnt mit dem staatssymbol und am ende
19:03steht das erzeugte wird das heißt in
19:05gewisser weise sind die arbeitsrichtung
19:06der beiden formalismen genau
19:08entgegengesetzt und das heißt eine tui
19:11maschine die ein wort als eingabe erhält
19:14und entscheiden soll oder
19:16erkennen soll sollte ich vielleicht
19:17lieber sagen ob das wort durch die
19:21grammatik erzeugt werden kann die muss
19:22in gewisser weise rückwärts vorgehen die
19:24muss also ab leitungs regeln der
19:27grammatik rückwärts an wänden und
19:28schauen ob sie irgendwie zum start
19:31symbol gelangen kann und das ist genau
19:32das was wir hier tun wollen also
19:36grundidee die touring maschinen können
19:38natürlich ab leitungs regeln anwenden
19:39aussetzen eines teil wortes innerhalb
19:43eines größeren wortes ist kein problem
19:44das lässt sich irgendwie implementieren
19:46touring maschinen haben ja ein wort auf
19:47dem band stehen das kann man sicherlich
19:49dann auch entsprechend umschreiben die
19:52das band eignet sich um den
19:54zwischenstand der ableitung zu speichern
19:56wir können terminale und auch nicht die
19:58arminia in unserem band alphabet zu
19:59lassen und die einfach aufschreiben
20:02wir können nicht determinismus nutzen um
20:04die geeigneten ableitung regeln zu
20:06wählen dann müssen wir uns nicht
20:07überlegen wie man die eigentlich findet
20:08und wir müssen das ganze rückgrats tun
20:11also mit dem erzeugten wort beginnen und
20:14dann in die andere richtung umschlagen
20:16jetzt ist vorwärts oder rückwärts
20:18umschreiben wenn man mal ehrlich ist bei
20:20type-0 grammatik ohnehin kein großer
20:21unterschied denn da wir keinerlei
20:23einschränkungen haben welche wörter
20:25links und rechts der aussetzung regeln
20:30stehen dürfen ist die umkehrung dieser
20:33dieser ersetzung am ende auch nur eine
20:35ersetzung gut dass uns als die grundidee
20:41und das kann man jetzt im detail
20:43umsätzen ich vermute sie haben die
20:45meisten die das wesentliche schon
20:47verstanden jetzt mit der idee aber hier
20:48gibt es noch mal ein bisschen mehr
20:49details auf dieser folie zu den touren
20:52maschine die das schaffen könnte also
20:54die grammatik hat eine reihe von nicht
20:56terminalen die variablen ein eingabe
20:58alphabet produktions regeln und ein
21:00statussymbol das eingabe alphabet der
21:03tui maschine wird das gleiche sein dann
21:05das band alphabet soll beinhalten alle
21:09zeichen dass eingabe alphabet ist alle
21:11nicht terminal- symbol aller variablen
21:13und natürlich das blank was wir
21:14zusätzlich noch haben um die noch nicht
21:16benutzten felder zu markieren
21:18die arbeitsweise skizziert wie immer ist
21:22wie folgt wir wählen nicht
21:25deterministisch eine regel
21:27aus in der grammatik also eine regel die
21:29ein teil durch ein tv ersetzt
21:31wir finden nicht deterministisch auf dem
21:34band ein vorkommen von irgend eines und
21:40wir ersetzen dann dieses foul durch
21:43dabei verschieben wir den rest des
21:44bandes entsprechend wenn die länge von
21:47omv nicht gleich sein sollte und das
21:51wiederholen wir so lange bis entweder
21:53auf dem band nur noch das staatssymbol
21:55steht und wir akzeptieren oder kein
22:00vorkommen von v zur ersetzung mehr
22:03gefunden wird und wir also nicht
22:07erfolgreich sind beim umschreiben beim
22:09rückwärts und schreiben vielleicht auch
22:12einfach falsch beraten haben das
22:14praktische ist also hier ist es hier ich
22:16das ganze natürlich nur aber auch in der
22:17implementierung können diese diese
22:20ersten und zweiten schritt der
22:21extremfall vorgehen sie müssen sich
22:22nicht viel mühe geben eine gute wahl zu
22:26treffen
22:26sie können einfach irgendetwas wie er in
22:29oder sogar die möglichkeit in betracht
22:31ziehen dass sie gar nicht gewählt haben
22:32und am ende ist wird das ankommen hat
22:33immer noch keinen vorkommen von frau
22:34gefunden haben dann verwerfen sie eben
22:36auch die nicht deterministische touring
22:38maschine probiert ja alle möglichkeiten
22:41aus und es reicht wenn wir etwas angeben
22:44was zumindest die richtige das richtige
22:47vorgehen des rückgangs um schreibens mit
22:49beinhalten würde
22:54gut dass wir auch ein paar sehen hier
22:57ist wenn die touring maschine ein wort
23:00als eingabe was ich hier wählen eine
23:03dann hat sie genau dann einen
23:06erfolgreichen lauf wenn die grammatik
23:07eine ableitung von w zulässt wenn so
23:10eine ableitung möglich ist dann gibt es
23:12irgendeine folge von umschreibungen und
23:13man kann nicht die termin ist sich diese
23:15folge finden dann kommt man zu es und
23:17akzeptiert und wenn es keine möglichkeit
23:22gibt zuerst zu kommen dann gibt es auch
23:23keine entsprechende ableitung okay dass
23:29also die eine richtung und die ist die
23:31in gewisser weise einfachere ich werde
23:33ihn nicht die tui maschine im detail auf
23:34schaut mal wir sehen dass es im prinzip
23:36funktionieren würde okay die rück
23:39richtung soll als nächstes folgen
23:42wir wollen eine touring maschinen mit
23:43hilfe einer grammatik darstellen und das
23:45ist vielleicht die interessantere
23:46errichtung also dass man irgendwie typ 0
23:48grammatiken im die ansetzungen die dort
23:50stattfinden in software implementieren
23:52kann zumindest wenn man sich nicht darum
23:56kümmert ob die software irgendwann
23:57terminiert also oder ob sie ewig läuft
24:00wenn sie sich wenn sie keinen ergebnis
24:02findet wenn sie keine ableitung entdeckt
24:04hat ich glaube das ist relativ klar
24:06gewesen ja das ist auch nicht die
24:07einzige art wie man das machen könnte
24:08wie ich das hier aufgeschrieben hat man
24:10könnte zum beispiel auch die touring
24:11maschinen nutzen um systematisch alle
24:13ableitungen zu erzeugen die möglich sind
24:15und dann anhalten wenn man das erste mal
24:18das wort gefunden hat irgendwo muss
24:21natürlich aufpassen dass man keine
24:22tiefen suche macht auch da würde man
24:23wieder in der unendlichkeit in reihen
24:25laufen und vielleicht was vergessen
24:26aber wenn man eine breiten suche
24:27durchführt dann wäre auch dass eine
24:29mögliche implementierung um die um mit
24:32einer tour maschine die akzeptanz zu
24:36erkennen ok
24:39die rück richtung ist interessanter die
24:41sagt letztlich dass wir auch diese
24:43dieser rechten vorschrift die die touren
24:45maschine implementiert in ihrem zustand
24:47trafen mit ihren übergangsregeln dass
24:48wir all das letztlich mit einfachen
24:50umsetzungs regeln mit einfachen stringer
24:52setzung regeln implementieren können und
24:55es sagt uns das string umsetzungs regeln
24:57die bestimmte muster innerhalb eines
24:59längeren strings in einer längeren
25:01zeichenkette ersetzen unter umständen
25:04sehr sehr ausdrucks mächtig sind und das
25:06mussten auch schon manche in der
25:07informatik lernen also zum beispiel
25:10diverse rewrite regeln die man benutzt
25:13um zb e mail adressen oder umzuschreiben
25:18in solchen anwendungen wie sind mir
25:21sitzen email verarbeiten das programm
25:24oder oder apache als ein web-server die
25:27wurden auch schon in verschiedenen
25:29fällen als touring mächtig erkannt weil
25:32man eben auch mit solchen einfachen
25:33stringer setzungen schon sehr viel
25:36ausrichten kann sehr viel komplizierte
25:39dinge unter umständen passieren okay gut
25:42also das wollen wir jetzt machen wir
25:43suchen eine grammatik die für eine
25:45gegebene touring maschine die gleiche
25:47sprache erzeugt ok auch hier ist die
25:52idee wieder relativ direkt wir wollen
25:57das was die tormaschine tut in einer
25:59grammatik umsetzen das heißt die
26:01grammatik wird jetzt auf etwas arbeiten
26:04auf zeichenketten arbeiten die letztlich
26:06konfigurationen von touring maschinen
26:08codieren also das heißt wir wollen dass
26:11die grammatik teil wird was sie bisher
26:15erzeugt hat so erzeugt dass das im
26:19prinzip die konfiguration einer boeing
26:21maschine nach einer bestimmten anzahl an
26:23schritten darstellt und jedes mal wenn
26:24wir eine ersetzung durchführen wollen
26:26wir einen schritt weiter gehen in der
26:27berechnung die berechnung schritte
26:30können relativ einfach wir sehen werden
26:32durch aussetzungen von teil wörtern
26:34simuliert werden und das können sie sich
26:35vielleicht sogar schon ein bisschen
26:36vorstellen hatte ich dieses band habe
26:37das tonband auf dem die verschiedenen
26:40zeichen gespeichert sind ist mein lese
26:42schreib coop an einer bestimmten stelle
26:44und das was in einem schritt passieren
26:46kann dass die tormaschine nehme ich an
26:48dieser stelle etwas schreibt und den
26:50zustand verändert und vielleicht den
26:52kopf um ein feld verschiebt das ist eine
26:55sehr lokale veränderung ja das meiste
26:58teil des bandes bleibt ja genau gleich
27:00wie verändern nur dort wo der kopf
27:01gerade ist eine kleinigkeit und das kann
27:04man sehr schön mit aktions regeln von
27:06teils trinks kodieren wie wir gleich
27:08sehen werden
27:09okay das ist also eine schöne sache aber
27:12wir dürfen nicht vergessen es gibt ja
27:14noch das problem dass die grammatik doch
27:17eigentlich in die andere richtung
27:19arbeiten muss als die tormaschine so wie
27:20es ihnen gerade beschrieben haben
27:22wäre ja die grammatik auch ein
27:25formalismus der nach vorne rechnet ja
27:27das soll also in jedem schritt in jedem
27:28ersetzt schritt wollen wir eine einen
27:31touring maschinen übergang ausführen und
27:33am ende erhalten wird dann akzeptiert
27:36aber wir wollten doch am ende ein wort
27:38generieren ja ein wort was die
27:40tormaschine akzeptiert und die grammatik
27:42erhält doch eigentlich gar keinen input
27:44denen wir simulieren können oder auf die
27:46tour in maschine simulieren können also
27:48wie passt das zusammen dass wir vorwärts
27:49rechnen wollen aber die grammatik
27:51eigentlich erst am ende das wort zeit
27:53und die idee ist einfach wie folgt wir
27:59drehen den ganzen spieß um und nutzen
28:03auch wieder hier den extremen nicht
28:04determinismus der grammatik
28:06wir wählen nämlich eingangs ein
28:08beliebiges eingabe wird das heißt die
28:10grammatik erzeugt erstmal einen einen
28:13input und dann simulieren wir die
28:16tormaschine auf diese eingabe sowie
28:19skizziert habe schritt für schritt
28:20und falls die türken maschine akzeptiert
28:22sind noch nicht fertig sondern dann
28:25stellen wir das eingabe wort mit dem wir
28:30begonnen haben wieder her
28:31das heißt wir löschen alles in unserem
28:34teils trinkwasser methode maschinen
28:36simulationen zu tun hat und ersetzen den
28:39inhalt stattdessen durch das eingabe
28:42wort das wir am anfang als eingabe
28:44simuliert haben und dann erst ist die
28:46grammatik fertig dann erst wird
28:48irgendetwas ausgegeben was generiert
28:50worden ist und das ist natürlich auch
28:53wieder ein sehr wenig zielgerichteter
28:55ansatz wir erzeugen beliebige wörter und
28:58probieren einfach auf die tormaschine
29:00darauf
29:01funktioniert und weil es ja dann geben
29:04wir die wörter tatsächlich auch so wird
29:05die grammatik arbeit aber das ist
29:08vielleicht kein besonders effizientes
29:10vorgehen aber es ist geeignet um zu
29:14zeigen dass man wirklich alle wörter
29:15erzeugen kann
29:16die tormaschine akzeptieren würde indem
29:18man einfach alle wörter erzeugt dann
29:20nochmal prüft ob die maschine wirklich
29:21akzeptiert und nachdem man das gemacht
29:24hatten aufräumen darin sicherstellt dass
29:26die ausgabe so aussieht wie sie eben
29:29aber sehen so ok wie kodieren wir dass
29:33es gibt einen einfachen und die schönen
29:36kotierung strict um das übersichtlich zu
29:38halten damit wir wirklich die genauen
29:40regeln angeben können sie werden sehen
29:41die grammatik ist nicht mal besonders
29:43kompliziert ja die ich ihnen zeige passt
29:45auf eine vorher aber damit dass schönen
29:48lesbar bleibt nutzen wir einen trick
29:50indem wir sagen variablen von ge also
29:53die nicht terminale sollen gleich drei
29:56informationen auf einmal codier nämlich
29:59zum einen ein ursprüngliches eingabe
30:02band zeichen
30:04das ist entweder ein eingabe symbol oder
30:07blank wenn an der stelle nichts vorkommt
30:112 ein simuliertes arbeits band das ist
30:15das was wir was ich eigentlich als
30:16erstes beschrieben hatte werden wir mit
30:18einer grammatik an der touring maschine
30:20nach stellen wollen dann würden wir den
30:22string denn die grammatik erzeugt das
30:24teil wort zu verwenden als wäre das die
30:26aktuelle konfiguration und das ist im
30:28wesentlichen natürlich das arbeitsblatt
30:29und das soll auf jeden fall auch mit
30:31vorkommen in jedem zeichen in jedem
30:34variablen zeichen der grammatik und als
30:38dritter spur werden wir position und
30:42zustand codieren
30:43das heißt es gibt zusätzlich noch
30:46entweder ein zeichen aus gut als zustand
30:48individuellen maschine gerade ist oder
30:50dieses - hier das sollte andeuten dass
30:52die maschine dort eben nicht ist und
30:56diese drei dinge bündeln wir jeweils in
30:58einem zeichen zusammen das heißt wir
31:02stellen uns vor unsere zeichen sind
31:03trippe eigentlich aus drei unabhängigen
31:05komponenten und jede kombination gibt es
31:08als variablen zeichen und das macht uns
31:10ziemlich einfach dann
31:12die übergangsregeln zu schreiben hier
31:14ist ein kleines beispiel ich denke dass
31:15wir das am besten klar machen wir ich
31:18schreibe das so als wenn so eine art
31:19vector darstellung übereinander dann
31:21sehen sie auch gleich wie das
31:23verschiedene bänder oder verschiedene
31:25spuren hier codiert oben steht die
31:28eingabe abb und danach nichts mehr
31:32lenkt das ist also das sind das eingabe
31:34wort mit dem wir begonnen haben
31:35das müssen wir die ganze berechnung über
31:37aufbewahren denn wir wollen
31:39sicherstellen dass wir es am ende werden
31:41wir feststellen die tormaschine
31:42akzeptiert dann wirklich ausgeben können
31:44mit unserer grammatik die mittlere spur
31:47hier ist ein up arbeits band xxx lenkt
31:52das wäre also eine detail konfiguriert
31:56oder ein teil aus dem arbeits bank der
31:58touring maschinen und die untere spur
32:01sagt uns in welchem zustand an welcher
32:03stelle wir uns befinden
32:04wir hatten die unteren beiden spuren
32:07wenn wir konfigurationen als wird
32:08dargestellt haben gern kombiniert
32:10indem wir das so geschrieben haben wir
32:13hier also das was direkt vor dem kopf
32:16steht wird als erstes geschrieben dann
32:18kommt der zustand und das zeichen auf
32:20dem dazu stand steht und der rest des
32:21bandes folgt und hier ist aber praktisch
32:25ein bisschen übersichtlicher
32:27wenn man das schön trend okay das sind
32:31also die art von variablen symbolen mit
32:33denen meine grammatik arbeiten soll so
32:36viel information steckt in jedem symbol
32:39trotzdem ist es letztlich nur ein symbol
32:40also das ist jetzt hier keine neue
32:42datenstruktur wert benutzen einfach
32:44variablen die so aussehen die diese
32:46seltsame form haben mit zwei großen
32:48klammern usw
32:49trotzdem ist eine variable es gibt
32:51einfach nur sehr viele davon für jede
32:52mögliche kombination sehr viele japaner
32:57wie viele so schlimm ist es nicht okay
32:59außerdem brauchen wir noch ein paar
33:01variablen zusätzlich zu diesem preis
33:03spuren variable wir brauchen eine stadt
33:06variable die ich es nenne
33:07wir brauchen noch hilfs variablen a und
33:10b die ich gleich ein führen werde und
33:11wir werden
33:12er lenkt als einzelnes symbol benötigen
33:18das entsteht irgendwie beim aufräumen
33:19mit wärme auch gleich das heißt die
33:21variablen mit denen wir arbeiten in uns
33:23grammatik sind so beschrieben 4
33:27sonderformen und dann all diese triebe
33:31die ich so darstellen kann ja das
33:33eingabe alphabet mit blank x dem band
33:37alpha beta tormaschine x den zustand des
33:41jungen vereinigt mit einem minuszeichen
33:42mit so einem zusätzlichen zeichen hier
33:45als dritte komponente okay gut dass in
33:50unsere variablen jetzt brauchen die
33:51übergangsregeln und die sind gar nicht
33:53so schwer zu schreiben
33:55wir arbeiten in drei phasen die erste
33:58phase ist die initialisierung ich hatte
34:00ja gesagt die tormaschine die grammatik
34:02weiß nicht auf welche welcher eingabe
34:05sie arbeiten soll das heißt sie muss
34:06zunächst einmal eine eingabe erzeugen
34:08für die touren maschine dazu rät sie ein
34:10wort auf den wir dann die tormaschine
34:13simulieren
34:14das heißt die grammatik kann beliebige
34:16wörter raten wie macht man das einfach
34:21durch verschiedene ersetzung regeln das
34:25staatssymbol steht ganz am anfang
34:26und jetzt habe ich hier viele
34:29möglichkeiten und zwar für beliebige
34:31input symbole in beim input alphabet
34:35darf ich das staatssymbol umschreiben in
34:37ein zeichen dass die form hat kohl 0
34:41gefolgt von großer und ja wie gesagt
34:45wenn es hier b c und was auch immer noch
34:48gibt im eingabe alphabet dann sind auch
34:49diese möglichkeiten alle hier noch mit
34:51entsprechend optional alternativen wir
34:55getrennt ja okay das ist natürlich der
34:59erste anfang der erste schritt ich habe
35:03ein beliebiges zeichen am anfang des
35:06eingabe wortes gewährt ich habe ein
35:07beliebiges zeit ich habe das gleiche
35:09zeichen auf das touring maschinen band
35:11kopiert und ich setze die tormaschine im
35:13zustand 0 das ist ja statt zustand
35:15darunter so muss es immer beginnt
35:17natürlich muss man nicht immer das ein
35:20wort mit einem zeichen haben es könnte
35:22auch sein wir haben ein leeres wort und
35:24für diesen fall habe ich hier noch die
35:25zweite möglichkeit das einfach nur blenk
35:28blanco erzeugt wird das ist wenn wir für
35:30exelon prüfen wollen ob es in der
35:31sprache ist und in diesem fall gehen wir
35:33direkt zu bieten
35:35da kam kannte allerdings noch
35:37weitermachen da kann noch weitere
35:38zeichen erzeugen das ist jetzt fast die
35:40gleiche regel wie oben nur dass statt es
35:43steht das heißt einer kann wieder
35:45ersetzt werden durch ein beliebiges
35:46eingabe symbol oder auch b oder c also
35:50darf man nicht vergessen dass das große
35:53heer heißt nicht dass hier das kleine
35:54rad stehen wo es könnten noch
35:55irgendwelche anderen zeichen sein und in
35:57der untersten spur steht dann das - weil
36:00der zustand ist ja schon am anfang bei
36:01kundus
36:02alle weiteren zeichen die wir jetzt noch
36:04erzeugen die haben nicht in maschinen
36:07lesekopf dort und auch kein zustand dort
36:10angegeben und das kann man jetzt
36:13beliebig oft wiederholen man kann also
36:15beliebig viele zeichen auf das band
36:16schreiben und weiter machen und
36:18irgendwann wenn man genug geschrieben
36:20hat kann man auch b als anstelle von
36:25anschreiben und b ist dann die der
36:29moment in dem wir aufhören neue zeichen
36:31zu generieren wie tut aber auch noch
36:34etwas für b dürfen wir beliebig banks in
36:38die eingabe und industrial verbeet
36:41einfügen wobei auch hier wieder dazu
36:43stand nicht dort wo kommt das heißt also
36:45wenn ich bis auf diese erste ansätze
36:48dann kann ich das eingabe wird noch mit
36:50blanks verlängern
36:51und irgendwann wenn all das ausreicht
36:55wenn ich denke ich habe jetzt wirklich
36:56genug generiert dann kann ich absolut
36:58verwenden um das bios zu werden das die
37:00einzige möglichkeit das abzuschließen
37:01diese generierung irgendwann muss mal y
37:04stehen ansonsten kann ich keine
37:06ableitung erzeugen die irgendwann nur
37:10noch terminal- symbole enthält wesen die
37:11grammatik ja nochmal was machen sollte
37:13also was wir hier haben mit diesen
37:15regeln ist also nicht deterministisch
37:17prozess der aus dem start symbol
37:19beliebig viele eingabe symbole als so
37:22eine dreigeteilte spur hier oder da als
37:26zeichen aus drei anteil generiert und
37:30irgendwann und danach noch eine beliebig
37:32lange zeit in folge von links generiert
37:37die intuition dazu habe ich schon
37:40großteils erklärt was vielleicht noch zu
37:44erklären sein wird ist
37:46warum wir noch blanks erzeugen warum wir
37:48es nicht dabei belassen dass wir eine
37:49eingabe generieren und das wird sich
37:51gleich ergeben
37:55hier steht auch schon geschrieben das
37:57ist unsere arbeit sprecher ja also die
38:00zusätzlichen blanks dienen dazu der
38:02grammatik die möglichkeit zu geben
38:05die tormaschine noch auf weiteren
38:07speicherzellen zu simulieren
38:10wir generieren allen speichert jemals
38:14benötigt sein wird vorher ja wenn die
38:17tormaschine erfolgreich ist wenn sie
38:19akzeptiert dann akzeptiert sie nach
38:20endlich vielen schritten und den endlich
38:22vielen schritten wird sie auch nur
38:23endlich viel speicher brauchen
38:24das heißt wir können nicht
38:26deterministisch geraten wie viel
38:27speicher das sein wird wir alle zieren
38:29den schon mal in form dieser variable
38:33die ich hier beliebig oft generiere bis
38:35ich irgendwann y&r setzte und das wird
38:39der speicher sein den ich dann für die
38:40eigentliche simulation und das macht die
38:42situation ein bisschen einfacher ich
38:43muss dann während der simulation nicht
38:45darüber nachdenken wie ich das band
38:47erweitern könnte dynamisch oder
38:48verschiedene fälle betrachten oder so
38:50mal abgesehen davon das ist gar nicht so
38:52einfach wäre das ende des aktuellen
38:55bandes zu finden da müsste man dann
38:57zumindest dafür noch irgendein zeichen
38:58vor sich
39:00okay gut dass also phase eins wir
39:03erzeugen eine zufällige eingabe sie ist
39:05endlich aber sie kann beliebig lang sein
39:07und wir geben dem noch einen
39:08zusätzlichen arbeitsspeicher der auch
39:10endlich ist aber auch beliebig phase 2
39:14die eigentliche simulation so jetzt
39:18wollen wir die touring maschine
39:21darstellen mit hilfe von grammatikregeln
39:23und das ist jetzt relativ einfach hat
39:27nur ein paar bestimmung stücke weil
39:30natürlich jeder touring maschinen
39:31übergangen wie sie wissen aus fünf
39:33teilen besteht wir haben für ein
39:35bestimmtes für einen bestimmten zustand
39:38in dem wir uns befinden und ein
39:40bestimmtes zeichen iks dass wir gerade
39:42lesen an dieser stelle des bandes können
39:44wir in einen neuen zustand cool strich
39:47übergehend ein neues zeichen y schreiben
39:49und zum beispiel nach rechts gehen wie
39:53schon bei der beschreibung von läufern
39:55autorin maschine werde ich auch hier für
39:57die verschiedenen bewegungsrichtungen
39:58verschiedene fälle haben weil das
40:01strukturell unterschiedlich aussieht was
40:03man eine setzung in der jeweils bekommen
40:05hier beginnt also mit den fällen in
40:07denen wir nach rechts gehen können
40:09ich schreibe das hier mit seinem element
40:11symbol dh das was ich hier mache gilt
40:13auch für eine nicht deterministische
40:14touring maschine
40:15sie können damit direkt also nicht
40:18deterministische touring maschinen
40:19darstellen ich glaube nicht dass ich
40:22sonst irgendwo explizit dargestellt
40:24wurde wenn sie eine deterministische
40:25maschine hätten dann wäre das einfach
40:27gleichheit diese situation
40:32ok falls wir also so einen übergang in
40:37der tormaschine haben und falls a und b
40:42beliebige zeichen sind im eingabe
40:44alphabet bzw
40:45herr blank und falls z ein beliebiges
40:48zeichen ist dass im band alphabet oder
40:52eingabe alphabet vorkommt bei dass ein
40:54bisschen übertrieben ist hier das
40:58eingabe alphabet nochmal hinzuzufügen
40:59dass es nur zur erinnerung das band
41:01alphabet enthält natürlich dass eingaben
41:02tropez zuwiesen dann haben wir eine
41:05solche übergangsregel was tut diese
41:07regel
41:08wir sehen gleich hier die zeichen a und
41:10b sind völlig beliebig also das ist
41:13diese zeichen kommen in dieser eingabe
41:15spur vor die hatte ich ja am anfang nur
41:16angelegt um zu merken worauf meine tolle
41:19maschine eigentlich simuliert wurde denn
41:20die tormaschine kann ja die eingabe
41:22löschen auf ihrem arbeitsplan kann da
41:24was ganz anderes hin schreiben und wenn
41:25ich da am ende weiß die tormaschine
41:27akzeptiert dann weiß ich nicht mehr was
41:28dort eigentlich stand und ich kann
41:30dadurch nicht das richtige ausgeben das
41:32heißt ich möchte mir die eingabe
41:34irgendwo erhalten und das mache ich auf
41:36dieser obersten spur aber für die
41:38eigentliche umformung für die
41:40eigentlichen schritte der touring
41:41maschine ist diese oberste spur völlig
41:42egal
41:43die arbeitet die maschine arbeitet dort
41:45nicht deshalb haben wir diese übergänge
41:47oder diese umformung regeln diese
41:49produktions regeln hierfür beliebige
41:51zeichen a und b könnten noch die
41:53gleichen sein zweimal weil es wirklich
41:55unerheblich ist was da steht genauso
41:57egal ist das zeichen z das an der
42:01position hier rechts von aktuellen
42:04schreib lesekopf auf dem band steht denn
42:06das ließ die touring maschinen ja nicht
42:07und das ist völlig unerheblich für das
42:09verhalten der touring maschine was dort
42:11eigentlich geschrieben steht die
42:12tormaschine im zustand kuh liest nur das
42:15iks und die ersetzung sagt also wenn
42:18irgendwo auf einem band was ich so
42:21codiert habe ein iks vorkommt an der
42:23stelle wo ich mich gerade im zustand kuh
42:25befinde
42:26mit meinem frei bläse kommt und es gibt
42:29eben diesen übergang hier
42:30danach setzte ich das aktuelle band
42:32durch ein neues bei dem die erst das
42:36erste der beiden symbole so ersetzt wird
42:39das an dieser stelle des band ist jetzt
42:40y steht das ist das was die tormaschine
42:42schreibt und der zustand sich nicht mehr
42:44dort befindet und stattdessen ist der
42:47zustand jetzt rechts davon im und zwar
42:51im neuen zustand kuh strich also das ist
42:54einfach die der übergang der hier
42:55beschrieben wird in form von diesen
42:58dreier hülsen da ausgeführt auf einem
43:01band und natürlich kann die grammatik
43:03dieser ersetzung irgendwo auf dem band
43:04durchführen es gibt aber auf dem band
43:06per konstruktion immer nur eine stelle
43:08an der ein q steht also das ist die eine
43:11einzige position in der der schreib
43:13lesekopf sich gerade befindet und nur
43:15dort können wir irgendwas aussetzen
43:17während wir simulieren
43:18okay das ist also ein schritt bei dem
43:20die tor maschine nach rechts geht wir
43:22können das auch nach links durchführen
43:24dass es passt genau das gleiche wie oben
43:26nur dass ich hier ein l stehen habe und
43:28dass jetzt zwei hülsen ersetze bei der
43:31den ich die linke und die rechts davon
43:34stehen mit dem schreib lesekopf
43:35betrachter und dann in die andere
43:38richtung wechselt ja alles andere ist
43:40gleich hier sollte ich vielleicht dazu
43:42sagen diese ersetzung nimmt an dass ich
43:45links vom schreib lesekopf überhaupt
43:47etwas habe und tatsächlich beim beweis
43:51funktioniert nicht für touring oder
43:52betrachtet nicht den fall dass touring
43:55maschinen am linken rand anstoßen und
43:58sich dann nicht bewegen so wie es mal
43:59definiert hatte für meine druckmaschinen
44:01also das ist eigentlich eine etwas
44:02andere art von touring maschine diese
44:04tormaschine hier kann übergänger die
44:07nach links wollen einfach nicht
44:09ausführen wenn links vom schreib
44:12lesekopf kein zeichen mehr zur verfügung
44:14steht das ist aber auch äquivalente sich
44:16leicht denken können dass nicht viel
44:18dazu man kann das auch leicht ineinander
44:19umwandeln
44:20für uns ist er praktisch müssen wir
44:23nicht noch
44:23sonderregeln einführen wie würde man das
44:27machen wenn man diese sonderregel haben
44:28wollte naja man würde irgendein
44:29markierung an den anfang des bandes
44:31setzen bei der generierung die es uns
44:34erlaubt zu erkennen wenn wir am linken
44:35rand anstoßen und dann müsste man noch
44:37eine zusätzliche regel hand wird diesen
44:38sonderfall spare ich mir okay das ist
44:41die möglichkeit nach links zu gehen und
44:43dann gibt es natürlich noch den fall
44:45indem ich einfach nicht den schreib
44:52lesekopf bewegen möchte dass das ändert
44:54das ist noch einfacher da muss ich
44:55einfach nur den aktuellen den die
44:58aktuelle kotierung an der stelle des
45:00zustandes versetzen durch die neue mit
45:02dem neuen zustand dem neuen zeichen und
45:03es ist egal was links und rechts davon
45:04passiert gut außerdem ist hier noch eine
45:10bemerkung aufgetaucht am rand ich gehe
45:13mal ein bild das ich dir auch notfalls
45:14lesen können was dahinter steht ist die
45:17in phase eins vorbereiteten zeichen auf
45:21dem band können hier nicht verlassen
45:24werden das heißt also all diese regeln
45:25die ich ihnen gezeigt habe
45:27navigieren nur innerhalb des in phase
45:31eins geratenen wortes ich kann natürlich
45:35hier oben an wo a b und immer
45:39geschrieben steht auch ein blick haben
45:40ich kann in meinen arbeitsspeicher
45:42reingehen aber ich kann keinen neuen
45:44arbeitsspeicher erzeugen also auch die
45:47regel die rechts geht wird nichts
45:50anfügen man sie sehen auch schon das
45:52wäre auch ein bisschen schwierig etwas
45:53anzufügen weil ich ja gar nicht ist wenn
45:55ich wenn ich das werk ließe ob das
45:56wirklich das ende ist oder ob ich dann
45:58mit den worten seit mit den teilchen
45:59einfüge das will ich vielleicht nicht
46:02also so ist es bequemer und gibt uns
46:05schöne drei regeln für drei richtungen
46:07ok
46:09gut das also ist die simulation und wir
46:12sehen jetzt also wenn sie das so weit
46:14verstanden haben dann sehen sie
46:15hoffentlich dass tatsächlich die
46:17umschreibungen die hier schritt für
46:20schritt passieren genau die schritte der
46:22tormaschine simulieren das heißt wir
46:23werden am ende hier auf dem band genau
46:26das haben was die tormaschine auch auf
46:29das band geschrieben hätte
46:31und wir können solange aussetzungen
46:33durchführen bis die tormaschine
46:35irgendwann nicht weiterkommt hält und
46:39dann müssen wir entscheiden doch
46:40akzeptiert wurde und dazu habe ich hier
46:43eine regel die schluss macht und zwar
46:50sage ich für alle zuständig die ent
46:53zustände sind und alle symbole die auf
46:56dem band auftauchen könnten
46:58wobei gilt dass es keine übergänge gibt
47:02im zustand coo für dieses symbol also
47:04wir machen das nur für die kombinationen
47:06in denen die tormaschine feststecken
47:08würde also hält und natürlich für
47:11beliebige zeichen aber in der obersten
47:13spur führe ich so eine regel an diese
47:17regel ersetzt diese variable aus drei
47:20bestandteilen durch das was in der
47:23obersten spur steht und das ist der
47:26anfang vom ende quasi an dieser stelle
47:28wenn das passiert fängt die hat die
47:30touring maschine akzeptiert und wir
47:32markieren diese akzeptanz nicht durch
47:34irgendwelche zusätzlichen zeichen sollen
47:35wir markieren sie direkt dadurch dass
47:37wir das zeichnet aus der obersten spur
47:38zurück holen und an die stelle schreiben
47:41an der wir gerade sind
47:42wenn das einmal passiert ist dann wird
47:47können wir feststellen wir haben
47:49akzeptiert wir wollen jetzt alles aus
47:51der oberen spur zurück
47:53und das als generiertes wort ausgeben
47:56und das machen wir indem einfach solche
47:58zeichen wenn sie auf dem band vorkommen
48:01solche zeichen die noch aus drei teilen
48:04bestehen anstecken und dazu führen dass
48:08sie ebenfalls kollabieren das sieht so
48:11aus ich sage ich habe eine regel wenn
48:14irgendein zeichen links von einem
48:16zusammengesetzten zeichen auftaucht
48:19dann wird das zusammengesetzte zeichen
48:21ebenfalls kollabiert holte ich mir
48:23einfach den teil nach unten
48:25genauso gut genauso mache ich es für die
48:28fälle in denen das einfache zeichen
48:30rechts von dem zusammengesetzten zeichen
48:32steht auch da hole ich einfach dass b
48:34aus der ersten spur nach unten und so
48:36können sie sich vorstellen wie also die
48:37von der stelle aus wo die touring
48:40maschine akzeptiert hat wo der zustand
48:42am ende stand das gesamte wort in beide
48:44richtungen wieder völlig durch das was
48:48in der ersten spur
48:49geschrieben ist ersetzt wird ok damit
48:53sind wir schon fast fertig eine
48:54kleinigkeit fehlt noch in der ersten
48:55spur war ja auch unser zusätzlicher
48:57arbeitsspeicher noch vorhanden
48:59den wollen wir jetzt noch löschen wenn
49:00wir also hier blanks nach unten geholt
49:02haben danach setzen wir jetzt durch y
49:05die verschwinden das blenk war ja auch
49:07eine variable und kein termin als symbol
49:09und wenn wir das alles getan haben und
49:12die tormaschine also erfolgreich war und
49:14wird die längst alle gelöscht haben dann
49:15haben wir tatsächlich einen string der
49:17nur noch aus eingabe zeichen besteht und
49:19es werden genau die eingabe zeichen sein
49:21die wir am anfang geraten haben und für
49:22die wir gefunden haben dass die touring
49:24maschine akzeptiert und die grammatik
49:27kann auch nichts weiter tun und sie kann
49:28jetzt nicht weiter ersetzen das heißt
49:29wir haben ein wort erzeugt und das ist
49:31die ausgabe sie sehen ein ziemlich
49:36indirekter prozess um wörter zu erzeugen
49:39und sicherlich nicht das was man
49:40intuitiv zunächst gedacht hat als wir
49:42angefangen haben über grammatiken zu
49:44reden dass man so etwas internes erste
49:46mal ausrechnet und dann je nachdem was
49:48herauskommt unterschiedliche dinge
49:49überzeugt dann aber er hat durchaus
49:52etwas was doch am ende ganz einfach
49:55funktioniert also das ist das was ich
49:58schon gesagt habe die grammatik erzeugt
49:59ein wort wie genau dann wenn die tui
50:01maschine einen akzeptierenden lauf für
50:03hat unter verwendung von beliebig viel
50:07speicher es kann auch sagen dass das
50:09nicht gelingt für das für ein eingabe
50:11wort was in der was eigentlich
50:13akzeptiert werden würde
50:14nämlich dann wenn die tormaschine mehr
50:16speicher braucht als die grammatik
50:18geraten hat wenn die grammatik zu wenig
50:20freie zellen klänge erzeugt hat am
50:22anfang dann kann es auch sein dass kein
50:23übergang mehr möglich ist aber dass auch
50:27dass das schon passiert an einer stelle
50:29wo die tormaschine eigentlich noch ein
50:30übergang hätte wo also diese
50:31schafft zum beispiel nicht erfüllt ist
50:32aber wo es einfach nicht weitergeht weil
50:35es keine speicherstelle mehr rechts vom
50:37aktuellen diese schreibt kopf gibt dann
50:39steckt die ableitung halt fest da wird
50:41halt nicht so sagt es wird schon eine
50:42andere ableitung geben wenn das
50:43funktioniert gut
50:47damit sind wir im prinzip fertig mit
50:50diesem beweis wir haben gezeigt die typ
50:53nur grammatiken erzeugen genau
50:54diejenigen sprachen die von einer
50:56touring maschine erkannt werden können
50:58und dann jetzt können wir zurückkommen
51:00zu dem satz von reis den witz informel
51:03auch auf typ 0 grammatiken anwenden
51:05können
51:06und der dann so lautet etwa für eine
51:08gegebene type-0 grammatik ge und eine
51:11nicht triviale eigenschaften von typ 0
51:13sprachen ist es unentschuldbar
51:15ob die sprache von g die eigenschaft hat
51:19also wir ersetzen die sprache von ge
51:22oder die sprache der tour maschine aus
51:24dem satz von reis jetzt mit der sprache
51:26der grammatik
51:26alles andere bleibt im prinzip gleich
51:28nicht nicht trivial heißt auch das selbe
51:31wie vorher
51:31also das heißt nicht real ist die
51:33eigenschaft dann werden es kommt null
51:35grammatiken gebe bei denen die sprache
51:37die eigenschaft hatte hätte und andere
51:39bei denen das nicht so wäre also jede
51:42interessante eigenschaft der sprache und
51:45das ist unentschuldbar und damit haben
51:48wir auf einen schlag alles zu typ 0
51:50gesagt mehrheit universalität äquivalenz
51:53zu einer anderen typ 0,3 und so weiter
51:55sind alle ohne entscheid bar genauso wie
51:59auch für tore gut
52:02damit haben wir im wesentlichen typ 0
52:06schon so gut wie abgehandelt viel mehr
52:08kann man nicht machen ein bisschen über
52:10abschluss eigenschaften welche ihnen
52:11noch in kürze aktie aber die wichtigsten
52:13dinge wissen sie jetzt und als nächstes
52:16sollten wir uns mal typ 1 genauer
52:17anschauen und sehen wie wir denn das
52:20vielleicht auch noch irgendwie mit
52:22boeing maschinen oder ähnlichen
52:24automaten modellen zumindest erkennen
52:26können damit wird oder auch was haben
52:29was dem entspricht
52:30ok bis dahin danke für die
52:33aufmerksamkeit eines und ab wie das sie

About this transcript

This page contains the full transcript of Turingmaschinen und Typ-0-Sprachen by Prof. Markus, generated from the public captions YouTube serves with the video. The transcript has 8,154 words across 1,383 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.