 |
Manuals |
Die Turing-Maschine (einfaches Alphabet)Über den ersten Computer der Welt wird viel gestritten. Die einen meinen es ist der Abakus, der bereits 1000 Jahre v. Chr. verwendet wurde um Handelsgeschäfte im mittleren Osten zu erleichtern, oder es wäre Konrad Zuses Z1 die ein Opfer des zweiten Weltkrieges wurde bevor sie fertig gestellt werden konnte. Andere glauben der Erfinder des ersten Computers wäre Alan Turing mit seiner Arbeit im Bletchley Park, ebenfalls während des zweiten Weltkrieges. Er und sein Team aus weiteren namhaften Mathematikern bauten die Collosus-Maschine um den Enigma Code zu entschlüsseln - was ihnen auch gelang, und nach einheliger Meinung, die Wende im zweiten Weltkrieg, zu Gunsten der Alliierten, herbei führten. Doch daß stimmt nicht ganz. Die Collosus-Maschine war einerseites genial und zuverlässig im Entschlüsseln des Enigma-Codes. Dieser Code wurde vom deutschen Oberkommando der Marine verwendet, die Aufträge und Positionen ihrer U-Boote verschlüsselt zu funken. Ein richtiger Computer war die Collosus nicht, sie kannte nur dieses Programm zum entschlüsseln des Codes. Vor der Collosus entwickelte Turing die Turing-Maschine mit der man jedes erdenkliche Mathematische Problem lösen könne - die Berechenbarkeitsmaschine. Und in der Theorie gelang es ihm - sie funktionierte bereits. Ihm kam jedoch der Krieg zuvor bevor er mit dem Bau beginnen konnte. Die Collosus ist eines der Werke an denen bereits Teile der Turing-Maschine verbaut wurden die Turing sich erdacht hatte. Der Bau der eigentlichen Turing-Maschine konnte nie vollendet werden da Alan an einigen Details scheiterte und sich 1954 das leben nahm.Die Turing Maschine war in der Theorie der erste programmierbare Computer vor Konrad Zuses Z1. Im wesentliche besteht Sie aus einem Endlosband mit Einsen und Nullen die durch einen Lese- und Schreibkopf verändert werden können - eine Art Arbeitsspeicher. Das eigentlichen Programm ist aufgeteilt in Register. Diese Register sind durchnummeriert von 1 bis, wenn man will, unendlich. Beispiel: Arbeitsspeicher / Endlosband ...00011101111000...Die Position des Lese/Schreibkopfs im Endlosbands ist fett dargestellt. Register 1 2 10R2 11L2 usw. 01R2 01L3Jedes Register besteht aus zwei Regeln zum Verhalten was geschehen soll wenn der Lesekopf entweder eine Eins oder eine Null liest. Im Beispiel steht im 1. Register, in der ersten Zeile was geschehen soll wenn der Lese/Schreibkopf eine 1 liest. Er soll dann auf diese Position im Endlosband eine 0 schreiben, dann nach rechts fahren und mit dem 2. Register fortfahren. Die zweite Zeile des 1. Registers beinhaltet das Verhalten bei einer 0. Es soll eine 1 auf diese Position geschrieben werden und den Lese/Schreibkopf nach Rechts verschieben. Danach mit dem 2. Register fortfahren. Der Lese/Schreibkopf brauch sich in seiner Position nicht unbedingt in einer Richtung verschieben, er kann auf seiner gegenwärtigen Position mit dem Steuerzeichen S (Stopp) stehen bleiben. Der Anfang und das Ende eines Programms wird immer mit der ersten 1 im Endlosband begonnen und beendet. Da die Daten in einer Turing-Maschine, mit einfachem Alphabet, offensichtlich binär, also sprich mit nur zwei Zuständen dargestellt werden, müssen wir die Umrechnung von Hand erledigen. Eine drei wird z.B. durch drei hintereinander folgenden einsen dargestellt und abgeschlossen durch eine 0. Die darauf folgende vier wird wiederum mit vier aufeinander folgenden Einsen dargestellt, wiederum mit einer 0 abgeschlossen. Aus diesem, zugegebenermaßen, simplen anwenden von Regeln auf Daten in einem Endlosband kann nunmehr jedes erdenkliche Programm ausgedacht werden. Eine Addition zum Beispiel das aus 111011110 uns 1111111100 errechnet. Also 3+4 = 7. Solch ein Programm würde folgendermaßen aussehen: Arbeitsspeicher / Endlosband ...0001110111100000... Register 1 2 3 4 5 11R1 11R2 10L4 11L4 11S5 01R2 00L3 00S3 00R5 00S5Die Position des Lese/Schreibkopfs im Endlosbands ist wiederum fett dargestellt. Das aktive Register ist ebenfalls fett dargestellt. Das erste Register arbeitet sich vor bis zur zweiten Zahl im Endlosband und übergibt dann an das zweite Register und löscht die 0 die die zwei Zahlen getrennt hat. ...0001111111100000... 1 2 3 4 5 11R1 11R2 10L4 11L4 11S5 01R2 00L3 00S3 00R5 00S5Jetzt haben wir zwar aus zwei Zahlen eine gemacht, allerdings macht 3+4=8 keinen Sinn. Der restliche Code wird sich bis zur nächsten 0 vorarbeiten und dort die letzte eins der zweiten Zahl entfernen und sich wieder bis nach vorne zum Ausgangspunkt bewegen. ...0001111111100000... 1 2 3 4 5 11R1 11R2 10L4 11L4 11S5 01R2 00L3 00S3 00R5 00S5Im nächsten Schritt wird das Programm eine 0 im Endlosband vorfinden und den Lese/Schreibkopf nach Links auf die letzte 1 verschieben, dann mit Register 3 fortfahren. ...0001111111000000... 1 2 3 4 5 11R1 11R2 10L4 11L4 11S5 01R2 00L3 00S3 00R5 00S5Die letzte 1 der zweiten Zahl ist gefunden. Sie wird durch eine 0 ersetzt. Die zweite Zeile des Registers ist in diesem Fall unwichtig, da wir ja wissen das diese Zahl nur eine 1 sein kann, und somit nie ausgeführt wird. Deswegen enthält es den Platzhalter 00S3. Wenn 0 dann schreibe 0 und bleib bei Register 3. Bei Verwendung dieses Codes würde normalerweise das Programm sich in eine Endlosschleife stürzen aus der sie nie wieder heraus kommt. Die einfachste programmierbare Rechenmaschine der Welt würde sich >aufhängen<. Also das gab es auch schon 1937 wie 1995, 1998, 2000 usw.. Jedoch hatte Alan Turing dies voraus gesehen und dieses auf der Stelle treten ausgenutzt. Wiederholt sich dieses auf der Stelle treten von Register und Lese/Schreibkopf, so ist dies die Abbruchbedingung eines jeden Turing Programms, des einfachen Alphabets. ...0001111111000000... 1 2 3 4 5 11R1 11R2 10L4 11L4 11S5 01R2 00L3 00S3 00R5 00S5Das vierte Register sucht nun bis zur ersten 0 und übergibt dann an das fünfte Register das in der ersten Zeile wieder unseren bekannten Platzhalter enthält und beendet das Programm indem es am Ausgangspunkt auf der Stelle tritt. Das Programm zum inkrementieren einer Zahl würde so aussehen. ...0001111111000000... 1 2 3 11R1 11L2 11S3 01L2 00R3 00S3Das Endlosband zeigt eine 7 aus der wir eine 8 machen wollen. Das erste Register sucht die letzte 0 der Zahl. Überschreibt diese mit 1 und gibt an das zweite Register weiter. Dieses geht ganz nach links zur ersten 0 und übergibt dann an Register 3. Dieses tritt auf der Stelle und erfüllt somit die Abbruchbedingung. ...00011111111000000... 1 2 3 11R1 11L2 11S3 01L2 00R3 00S3Das Programm ist beendet und hat die Zahl 7 um eins auf 8 inkrementiert. Das alles hat eigentlich nur das erste Register gemacht. Die letzten zwei Register waren nur zum einleiten der Abbruchbedingung notwendig. Das nächste Programm ist nur gering komplexer und dekrementiert eine Zahl. 1 2 3 4 11R1 10L3 11L3 11S4 00L2 00S2 00S4 00S4Auch in diesem Beispiel verrichten nur die ersten zwei Register effektiv Arbeit. Die letzten beiden Register leiten nur die Abbruchbedingung ein. Ein um einiges komplexeres Programm ist die Multiplikation zweier Zahlen die die zuvor gezeigten Programme des Inkrementieren und Dekrementieren voraussetzt. Um eine Zahl zu multiplizieren bedienen wir uns eines Tricks der in diesem Buch noch öfters zur Anwendung kommt. Die erste Zahl dient als Zähler während die zweite Zahl der Multiplikand ist. Wir addieren solange 6 mit dem letzten Ergebnis und dekrementieren bei jedem Schritt den Zähler bis dieser 0 erreicht hat. a) Zähler 3, Ergebnis 0 b) Zähler 2, Ergebnis 6 c) Zähler 1, Ergebnis 12 d) Zähler 0, Ergebnis 18 In Pascal würde der Code so aussehen: multiplikand := 6; repeat ergebnis := ergebnis + multiplikand; dec(zaehler); until zaehler = 0;In Turing würde das ganze um einiges komplizierter aussehen was allerdings den Rahmen dieses Buches sprengen würde und auch nicht besonders interessant wäre im Kopf von einem Register ins nächste zu springen bis das Programm nach 387 Takten endlich zwei Zahlen miteinander multipliziert hat. Das einfache Alphabet der Turing-Maschine ist auch eine sehr abgespeckte Version der eigentlichen Maschine die nicht nur mit Registern arbeitet, sondern auch mit States, in denen mehrere Register stehen können. Sie hat zudem noch ein größeres Alphabet in der a, b, c, x, y, z, $ und # darin vorkommen. Damit lässt sich, wie man sich vorstellen kann, so einiges mehr berechnen und lässt einen wirklich daran glauben das die Turing-Maschine Turing-Complete ist und man damit jedes erdenkliche mathematische Problem lösen kann. von Thilo Hardt |
