Einführung in Turing Maschinen
Andreas Schaefer
https://www.youtube.com/watch?v=obwKl6yOEdg

Transkript (automatisch erstellt)

0:00 instant video geht es um die idee hinter den touring maschinen und meine erste formale definition der tormaschine am ende möchten wir die frage beantworten
0:10 können was können computer eigentlich typisches szenario was wir haben ist wir haben auf der einen seite ein computer der bordcomputer wird gesteuert durch
0:18 ein programm das wir hier geschrieben hat unsere premier sprache dieses computerprogrammen bekommt irgendwelche daten als input und tut damit irgendwas
0:26 und die frage wie man sich natürlich jetzt stellen könnte es welche arten von problemen können computer eigentlich lösen beziehungsweise gibt es probleme
0:35 die zwar praktisch sehr interessant sind die computer nicht lösen können und in einem zweiten schritt folgen angucken welche probleme die man zwar prinzipiell
0:42 lösen könnte man auch noch effizient lösen könnte das problem wirkt vielleicht auf der auf den ersten blick sehr theoretisch tatsächlich gibt es
0:51 eine ganze reihe von sehr vielen interessanten eigenschaften die wir angucken werden insbesondere sind das eigenschaften von programmen in seinem
1:00 programm geschrieben haben interessiert sie vielleicht die fragestellung wird man programm irgendwann mal halten wir jetzt
1:04 terminieren und da läuft das vielleicht unendlich weiter oder fragestellung ist die funktion die ich gerade geschrieben habe ist ja eigentlich erreichbar wird
1:13 jemals aufgerufen das sind eigenschaften von programmen bei denen interessant wäre wenn wir dazu etwas wissen könnten wenn du uns zum
1:19 beispiel unsere idee da eine hilfestellung geben könnte oder compiler und da wird sich zeigen dass diese probleme tatsächlich im allgemeinen und
1:27 entscheider sind das die im allgemeinen eben nicht von computern gelöst werden können was was dann zu eben vielen probleme macht und um das ganze formal
1:38 fassen zu können brauchen wir ein formales maschinen modell die computer die wir so haben die sie jetzt gerade vor sich stehen haben zum beispiel die
1:45 sind sehr aufwändig formal zu beschreiben um viele einzelteile verbrauchen ein modell was einfach formal zu beschreiben ist auf der
1:53 anderen seite soll das problem soll das modell auch nicht zu einfach sein weil das modell muss so ausgelegt sein dass alles was wir prinzipiell mit unserem
2:00 rechner tun können dass wir das auch mit einem computer tun können dass die idee dabei das modell was wir benutzen werden sind
2:07 die sogenannten touring maschinen die touring maschinen sind benannte nach allen thüringen journey ist ein britischer informatiker einer der väter
2:16 der informatik hat gelebt von 1912 bis 1950 und war auch maßgeblich als krippe analytiker an der entschlüsselung der enigma beteiligt
2:25 die tormaschine selber eingeführt in seinem bekannten aufsatz und komplett übernommen das bild in der klinischen studie entscheidungs problem wir haben
2:33 uns 136 was ist das besondere an diesen tagen erschienen diese tormaschine um einmal einen speicher ein unendlich langes band mit
2:41 einem schreib lesekopf und in dem schritt den so vor sie lesen das zeichen dass unter dem kopf steht ersetzen das durch ein neues zeichen und bewegen den
2:50 kopf nach links oder nach rechts oder unter umständen auch gar nicht und wechseln danach den zustand auf diesem unendlich langen band finden wir eine
2:59 eingabe wir verlangen hier das die eingabe nun endlich ist also wohl eher ein unendlich großen speicher haben darf die eingabe selber nun endlich sein und
3:08 wir haben dann links oder rechts von der eingabe von rechts und links von der eingabe unendlich viele leer zeigt uns plenk zeichen damit wir wissen wo die
3:16 eingabe steht haben wir als zusätzliche anforderung dass das schreib lesekopf initial auf dem ersten zeichen der eingabe steht zusätzlich zum speicher
3:28 haben wir auch noch eine kontrolleinheit die quasi das ist was beim computer das programm ist und dass sie dem relativ ähnlich was sie zum beispiel von den
3:37 keller automaten nun endlich in automaten kennen haben auf der einen seite endlich viele zustände die sind hier wir haben dann ein zustand
3:45 davon der staat zustand ist und wir haben ein oder mehr and zuständig pressen teilweise auch akzeptieren die zustände
3:53 wir haben zwischen den zuständen haben wir traditionen diese traditionen ist möglich es aktiv wenn das eingabe zeichnen was da steht also in diesem
4:05 fall zum beispiel wenn das auf dem band steht dann ist diese transaktion möglich die hier markiert ist und diese tradition wenn die genommen wird ersetzt
4:12 sie das was auf der aktuellen position steht durch ein nix und bewegt den kopf nach rechts dass die db zu gucken wir uns dazu mal ein beispiel
4:23 an wie sie so einem turnier maschine jetzt eine konkrete angabe abarbeiten würde wir haben hier unten die eingabe auf dem
4:29 band stehen die steht hier der sind initialen unserem staat zustand kuh 0 und an dieser stelle ist eine tradition möglich nebelt dass die tradition die
4:40 hier markiert ist weil wir mit dem kopf auf dem eis stehen können wir nur diesen übergang nehmen dieser übergang ersetzt das dadurch ja nix und bewegt den kopf
4:48 nach rechts nach den zustand entsprechend das heißt wir sind dann hier haben den kopf um 1 nach rechts bewegt muss dadurch nicht
4:54 ersetzt jetzt müssen wir gucken welche tradition ist wirklich möglich ist nur diese tradition die in dem zustand q1 bleibt
5:01 und den kopf nach rechts bewegt das heißt wir laufen hier nach rechts stehen immer noch auf einem ab das heißt die tradition die möglich ist jetzt wieder
5:09 die tradition die in dem zustand bleibt nur nach rechts geht wenn mit ihnen nehmen steht unser kopf plötzlich auf einem b jetzt ist diese transaktion
5:19 ermöglicht diese tradition ersetzt das bmx läuft nach rechts und wechselt den zustand sind jetzt also im zustand 2 im zustand kurz war bestimmt auf dem b
5:29 bei dem bleiben wir bei dem zu spielen einfach nur nach rechts stellen wieder auf dem b bleiben also immer noch in dem zustand gehen immer noch nach rechts
5:38 irgendwann finden wir dann ein täter kopf steht jetzt auf einem c dass das wir müssen jetzt diesen übergang nehmen in diesem übergang ersetzen wir das ziel
5:45 durch einig und laufen nach rechts hier an dieser stelle laufen jetzt immer weiter nach rechts und gucken so lange nach rechts bis irgendwann blenk finden
5:53 warum machen wir das an dieser stelle sicherstellen dass ab jetzt nur noch zäh es kommt das ist die idee dabei und das machen wir laufen also weiter nach
6:03 rechts und das tun der so lange bis wir irgendwann mit dem kopf auf diesen blinkzeichen stehen dieses zeichen wird symbolisiert durch
6:12 dieses rechteckiger kasten hier bei dieser tradition und sobald wir es gefunden haben wechseln wir also den zustand nach 4 beginnt schon einen nach
6:22 links und die idee bei q4 ist dass wir jetzt einfach ganz nach links rüber gehen alle zeichen die auf dem band vorkommen können also die
6:29 die asg ps und dci kurieren so lange bis wir das lenkt sehen also es einfach so zurückspulen wieder auf den anfang das machen wir in diesem zustand laufen nach
6:38 links bis für seinen blick sehen irgendwann haben wir es dann gefunden sind mit dem kopf auf dem bleck zeichen wenn wir auf diesem blog zeichen sind
6:46 dann die tradition die jetzt in abbott es gehen zurück nach kunden und setzen den kopf einen nach rechts hier in diesem zustand
6:55 sie ist jetzt so dass wir alle über lesen und danach quasi das gleiche nochmal von vorne machen also wir suchen wir da ein erstes ansuchen dazu ein
7:06 passendes baby was rechts davon stehen muss und wohl nur als nixe gekommen sein können und danach skippen will der alle babys finden das erste c fast dazu passt
7:15 ersetzen uns wieder durch nix und wieder zurück das machen wir einmal den satz in diesem zyklus und wenn man das einmal gelaufen haben sehen wir haben jetzt das
7:25 zweite h mit einem bmx und mit einem c gemischt und jeweils zwischen ex ersetzt werden soll so markiert dass das jeweils gepasst hat und machen das ganze noch
7:37 mal wieder für das nächste triple aus a b und c so wenn wir das geschafft haben sehen wir jetzt haben wir auf diesen band alle aßen bscs ix r setzt das auch
7:48 ein ganz typisches vorgehen virtuellen maschinen wenn wir irgendwie dem fall ist geht es uns darum die anzahl der sbs und sie ist nämlich zu vergleichen
7:57 das ist ganz typisches vorgehen das man immer die symbole die man schon bearbeitet hat dass man die irgendwie mit einem speziellen symbol markiert
8:04 also in dem fall jetzt die us psn csu wahrlich nichts ersetzt wenn diese schon bearbeitet hat und auf diese weise kann man dann jeweils die anzahl vergleichen
8:14 gut wenn wir jetzt sehen dass alle symbole durch nichts ersetzt sind dann gehen wir in diesem zustand kuh 0 da war lesen wir alex und gegen rechts
8:24 und wenn wir in diesen zustand irgendwann das blink sehen dann wissen wir dass auf dem brink bis da er auf dem tape bis dahin auf dem band ist ein nur
8:34 xi gestanden haben das heißt wir jetzt alle zeichen die vor auf dem band standen haben wir irgendwie in unseren streifen oben erwischt
8:40 gehabt das kann nur der fall sein wenn die anzahl der sbs und sie es gleich gewesen ist und deshalb in diesem zustand deshalb sitzungen so gesehen
8:51 dass prüft und jetzt in diesem zustand 0 hat sie die möglichkeit da sehe ich jetzt nur xi gelesen hat inzwischen nimmt sieht tradition hier und geht in
9:01 den endstand und an der stelle sind auch das relativ egal ist wo der kopf am ende steht hauptsache es an der stelle nur dass die tormaschine einen zustand
9:11 erreicht was wir jetzt gesehen haben ist also ein turm maschine die die sprache auch im büro in theorien akzeptiert und dass auch eine sprach von der wir schon
9:20 wissen dass sie nicht kontext preis das ist hier brauchen wir tatsächlich das dass das stärkere maschinen modell das die touren maschinen eben darstellt um
9:27 diese sprach zu akzeptieren das kann sie eben auch gut zum schluss warum das ganze noch einmal formal definieren was eine tormaschine ist und
9:37 wir beiden entchen automaten bei der keller automaten auch das drücken maschinen einen typen im fall 1 7 trubel wir haben eine endliche zustands menge
9:44 wieder cool werden ein eingabe alphabet gross sieht man dass das alphabet aus dem man die die eingabe weiter zusammen setzen darf wir haben außerdem ein band
9:55 alphabet grosse kammer das ist das hier dieses band alphabet gross kam hat das ist typischerweise größer als das eingabe alphabet insbesondere bald schon
10:05 das bringt was wir unten sehen in dem band alphabet ist aber kein gültiges eingabe bezeichnet häufig ist es praktisch das band alphabet noch größer
10:13 zu werden sie haben in dem letzten beispiel gesehen dass wir da immer die huskies und csu so ein sonderzeichen durch seine
10:19 nix ersetzt haben und das geht nur deshalb weil wir eben wissen dass es nicht eine eingabe vorkommen darf also wenn man sich marke
10:25 haben will dann würde man die instanz alphabet packen und eben nicht ins eingabe alphabet wir haben außerdem noch eine tradition
10:32 diese tradition funktion beschreibt die übergänge das heißt wir haben eine funktion von u dem aktuellen zustand kurz gamma dem
10:39 aktuellen symbol auf dem band nach groß crew wieder nachfolge zustand kreuz gamma das zeichen was das aktuelle zeichen auf dem band ersetzt also das
10:50 halten was jetzt geschrieben werden soll kreuz und jetzt haben wir die entsprechende kopfbewegung und da benutzen als symbole elf links- er für
10:59 rechtshänder neutral also wir bewegen uns nicht teilweise wird stadt ist entsetzt verwendete stoff aber das ist relativ
11:07 beliebig das also unser traditions- funktionen die die übergänge beschreibt wir müssen außerdem natürlich noch einen zustand auszeichnen als staat zustand
11:16 dass blenk selber hatte schon erklärt dass ich das sind die leerzeichen die wir nicht in der eingabe erlauben deswegen können wir immer sicher sein
11:24 dass das die eingabe zu ende ist weil wir zum beispiel einen blick lesen und das ist auch das zeichen des lebens und rechts jeweils von der eingabe steht
11:33 unendlich oft und wir haben eine menge von ihm zuständen groß f das kann eben eine oder mehr in zustände seien es kann auch keinen endzustand sein das ist eine
11:43 beliebige menge wir werden hier in diesem in diesen videos typischerweise die konvention beachten dass die ems zustände keine ausgehenden traditionen
11:52 haben einfach eine konvention die ganz praktisches weiteren das war jetzt formal definitionen und grundlegende idee von touring maschinen