Wie funktioniert die Turingmaschine von Alan Turing? - Einfach erklärt auf Deutsch (German)
FH JOANNEUM Kapfenberg IT Plus
https://www.youtube.com/watch?v=-3SAdXABfio

Transkript (automatisch erstellt)

0:04 willkommen zu einem kleinen video aus der informant heute werden wir lernen wie eine touring maschine funktioniert
0:15 hatten diese tieren maschine als mathematisches modell aufgestellt und diese touring maschine dient dazu den begriff algorithmus zu definieren bzw zu
0:26 beweisen muss ist eine problemlösung eine genaue vorgehensweise wenn man schritt für
0:34 schritt ein gestelltes problem lösen kann thüringer das für die mathematik aufgestellt und er hat auch diese maschine definiert um allgemeine
0:44 generische probleme der mathematik zu lösen generell gesehen ist diese touring maschine ein mathematisches modell ist aber von ihm definiert worden als modell
0:55 das man aber auch in der realität umsetzen kann was heutzutage auch teilweise gemacht wurde sei er sitzt in der software oder auch in der hardware
1:05 aber wie schaut eine touring maschine aus welche teile gibt es in dieser touring maschine wie funktioniert sie genau sie haben ja eingeblendet nur ein
1:14 bild von einem nachbau aber wie funktioniert das rechenmodell an sich was kann ich damit tun lassen sie mich dazu kurz aufzeichnen wie sie
1:23 funktioniert sie haben ein band dieses band ist unendlich kann nach links und rechts bewegt werden und auf dem band haben wir fünf
1:35 und in diesen zellen haben sie entweder keinen oder die märkte ist null oder eins
1:44 zusätzlich bei der touring maschine haben sie einen schreib- und lesekopf dieser schreib und lesekopf kann einzelne zahlen schreiben lesen er kann
1:54 aber auch zb die zahlen löschen das heißt sie haben wir zb diesen schreib und lesekopf und dieser schreib und lesekopf kann eben zb diese neue hier
2:06 überschreiben mit einer 1 zum beispiel er kann aber auch die zahl so belassen wie sie ist das band selbst kann nach links und
2:16 rechts bewegt werden und genau eine zelle und die ganze tour i maschine kann einen gewissen status besitzen
2:27 im grunde genommen definieren sie einen status oder mehrere status für jede eventualität
2:34 es ist es so sie haben wie gesagt dieses band und ihren schreib lesekopf und jetzt können sie definieren zum
2:51 beispiel in welchen status sie gerade sind wenn sie zum beispiel im status 0 sind dann können sie jetzt natürlich das
3:01 aktuelle zeichen lesen das heißt wenn dieses zeichen hier so wie in unserem fall 0 ist dann kann man zum beispiel sagen welches zeichen gedruckt werden
3:11 soll oder ob es belastet werden soll sie können hier zum beispiel sagen sie würden jetzt aus dieser 0 gerne eins machen und das nächste was sie machen
3:21 müssen ist welche aktion sie mit einem schreib lesekopf ausführen es bedeutet sondern nach links nach rechts gehen oder da bleiben wo er ist in unserem
3:31 fall sagen wir wollen eins nach rechts gehen plötzlich nach rechts und das letzte was wir bestimmen müssen ist welchen neuen zustand jetzt unsere
3:41 maschine besitzt das heißt welchen zustand zum beispiel den zustand 1 so jetzt haben sie sozusagen die erste möglichkeit gehabt und natürlich muss
3:53 man bei einer touring maschine auf alle eventualitäten eingehen wenn man sie programmiert das bedeutet sie müssen jetzt zum beispiel sagen sie sind im
4:01 status 0 und was ist wenn jetzt am band eine eins ist was machen sie dann sie sind im status 0 und was ist wenn in dem band nichts steht ja was machen sie dann
4:13 und diese eventualitäten müssen sie aus programmieren jetzt haben sie grundsätzlich die funktionsweise von der touring maschine
4:20 gesehen aber wie funktioniert sie in der realität das heißt wie könnte man jetzt ein problem lösen für uns werden wir jetzt ein bestimmtes problem angehen und
4:30 zwar wir werden auf eine binär zahl eine 1 agieren immer wenn sie auf eine binya zahl 1 addieren schaut das wie folgt aus gehen wir davon aus dass wir die binär
4:41 zahl 11 01 haben und wenn wir eigens addieren sind wenn er system haben wir bei 1 und 1 1 0 das heißt nun an 1 weiter
4:58 und hier haben wir 1 und 4 1 das heißt das ist das ergebnis einer pinie zahl bleiben wir bei unserem beispiel im binärsystem und bei der zahl 1 1 0 1 und
5:13 schauen wir einmal wie dieses programm jetzt in der touring maschine umgesetzt werden kann also sie haben wieder ihr wand
5:22 und haben die einzelnen zellen und irgendwo in diesem band haben wir 1 1 0 1 in diesem band jetzt haben wir den
5:35 schreib- und lesekopf an in einer beliebigen stelle das erste was wir machen wollen mit diesem schreib und lesekopf ist dass wir
5:44 ihn wenn wir an einer beliebigen stelle beginnen auf die rechte seite bringen und dann praktisch stoppen wenn das band keine zahlen mehr
5:54 beinhaltet das bedeutet wir wollen jetzt praktisch in unserem status 0 wollen wir praktisch schauen ob wir
6:05 jetzt mit unserem schreib und lesekopf auf einer zahl sind oder nicht und wenn wir von der zahl sind dann soll diese zahl wieder geschrieben werden das heißt
6:13 es soll nichts verändert werden und wir wollen nach rechts gehen das bedeutet im status 0 wenn wir hier eine eins haben soll wie einst geschrieben werden und
6:22 wir gehen 1 nach rechts und sind dann nach wie vor ein status 0 wenn wir jetzt beim nächsten nächsten integration hier sind dann
6:36 haben wir bei unserem status 0 jetzt die zahl null es soll wieder eine null geschrieben werden und wieder ein 60 gegangen werden und wir sind wieder im
6:46 status 0 jetzt sind wir dann wieder hier jetzt greift praktisch ist diese regel und
6:55 sobald wir jetzt mit unserem schreib und lesekopf auf einem leeren feld sind dann wird hier jetzt der nächste status aktiv
7:05 nämlich der status 0 wenn wir hier auf einem leeren feld sind dann wird natürlich nichts geschrieben dass das bleibt ein leeres feld und wir geben um
7:16 1 nach links und aber dann in den nächsten status nämlich in den status 1 der status 0 weit nur dafür da und ein schreib lesekopf nach rechts zu bringen
7:27 und auch die erste zahl wo wir uns jetzt befinden ist der status 1 sie schreibt wieder das band auf und wir befinden uns mit unserem schreib und lesekopf hinauf
7:40 hier wir sind jetzt den status eines der status 1 geht davon aus dass wir einen übertrag von einst haben das heißt wir zählen 1 hinzu was so viel heißt wie wir
7:51 haben wir dafür unsere eventualitäten 0 1 und 0 entsprechende zahlen einzufügen das bedeutet wenn wird eine 1 hinzufügen dann haben wir wenn
8:05 der wert aktuell 0 wäre eine 1 wenn der wert aktuell 1 wäre würden wir 10 in kenia haben und wir müssten eine null hin schreiben und wenn wir keinen wert
8:16 hätten hätten wir ja 1 übertragt und wir anschreiben müssten und hessen eine 1 jetzt ist es interessant wo wir mit unserem schreib und lesekopf bzw mit
8:26 unserem status hin müssen in jedem fall müssen wir mit den schreib- und lesekopf wieder nach links jeden zur nächsten zahlen die frage ist haben wir jetzt
8:35 wieder einen übertrag oder nicht wenn die zahl vorher 0 war haben wir keinen übertrag das bedeutet wir können den status 2 weil die zahl zuerst 1 war dann
8:45 haben wir mit 10 jetzt einen übertrag und bleiben in diesem status 1 wenn wir jetzt vorher keine zahl oder gar nichts gehabt haben haben wir jetzt ein
8:55 übertrag gehabt wir gehen nach links und sind praktisch mit unserer berechnung fertig weil die nächste zahl oder das nächste feld links leer ist das heißt
9:06 wir haben den status ende erreicht jetzt haben wir unsere staat definiert und das müssen wir das für unsere zahl auch noch umsetzen das bedeutet wenn sie auf die
9:17 zeichnung schauen befinden wir uns jetzt im moment hier mit unserem schreib und lesekopf im status 1 auf der zahl 1 von sind
9:27 exakt hier wir haben hier 1 und müssen jetzt null schreiben und gehen mit unserem schreib und lesekopf 1 nach links und sind nach
9:38 wie vor im status 1 jetzt befinden wir uns hier und müssen praktisch statt der 0 engst schreiben gehen 1 nach links und sind aber dann im status 2
10:01 wir befinden uns jetzt im status zwei das weiß eigentlich ein status wo der wagen der schreib lesekopf nur an eine
10:11 bestimmte position gerückt wird es wird bald ist nichts geändert und es wird nur geschaut ob jetzt der schreib lesekopf am ende des bandes ist und wird dann
10:24 eine bestimmte position gesetzt sie haben jetzt gesehen wie man ein einfaches beispiel in der tormaschine
10:38 löst und in aller munde sind die begriffe wie touring berechenbar oder touring vollständigkeit oder touring complete das hat sehr viel gar nichts zu
10:47 tun mit der um übersetzung von formalen sprachen auf die touren maschine das bedeutet wenn sie jetzt zum beispiel in seine funktion in der touring maschinen
10:57 umsetzen können ist die touring berechenbar wenn sie jetzt eine formale sprache in der touring maschine umsetzen können bzw deren kontrollstrukturen in
11:08 der touring maschinen gut berechnen können haben sie eine touring vollständige sprache