Was ist eine Turing-Maschine?

Turing Maschinen sind ein Gedankenmodell über die Berechenbarkeit von mathematischen Funktionen. Sie wurden 1936 von Alan Turing erfunden und tragen inzwischen seinen Namen (wie auch der bekannte Turing-Test).
Eine Turing-Maschine besteht aus zwei Teilen: dem Bandlaufwerk und der Steuerung, die eigentliche Maschine. Das Bandlaufwerk enthält ein Band mit idealerweise unendlich vielen Zellen. Jede dieser Zellen kann zwei Zustände einnehmen. Der eine Zustand: Leer, Null ,0 oder Strich (-), der andere: Voll, Eins, 1 oder Stern (*). (In dem Programm werden die Zustände durch unterschiedliche Farben dargestellt) Die Maschine sitzt in oder auf einer dieser Zellen und kann vier Aufgaben erledigen:

  1. gehe eins nach links
  2. gehe eins nach links
  3. schreibe Null
  4. schreibe Eins

Äquivalent zu obigen vier Regeln sind auch folgende (nach Prof. Hinst):
  1. schreibe 1 und gehe eins nach links
  2. schreibe 0 und gehe eins nach links
  3. schreibe 0 und gehe eins nach rechts
  4. schreibe 1 und gehe eins nach rechts

Jede dieser Anweisung wird in Abhängigkeit von dem Inhalt der aktuellen Zelle ausgeführt. In einer Art Programm stehen die Anweisungen der Maschine: eine Zeilennummer (Adresse), gefolgt von den Anweisungen, dann die Sprungadresse. Damit die Maschine ihre Arbeit auch einmal beendet, definiert man noch eine beliebige Regel zur Termination.
Darüber hinaus verfügen die Steuerung über keine weiteren Fähigkeiten. Dennoch ist es mit diesen einfachen Regeln (theoretisch) möglich, alle existierenden Algorithmen durchzurechnen. Eine Turing-Maschine besitzt sämtliche Fähigkeiten eines Computers.
Näher kann ich an dieser Stelle nicht auf die Materie eingehen, doch Literatur über Turing-Maschinen findet man an vielen Stellen, so z.B. auf der Alan Turing Homepage.

Alan Mathison Turing (1912 - 1954)

Warum einen Turing-Maschine-Emulator?

Jeder Informatik-, Mathematik- und Logikstudent bekommt es irgendwann mit Turing-Maschinen zu tun. Um diese Maschinen richtig zu verstehen, empfiehlt es sich, einige Maschinen praktisch durchzurechnen. Mit Papier und Bleistift ist das jedoch eine langwierige und mühsame Angelegenheit, ab einer gewissen Komplexität wird es sogar praktisch unmöglich. Warum also nicht den Computer zu Hilfe nehmen?

Was ist neuartig am Turing-Maschine-Emulator?

Der Turing-Maschine-Emulator weist eine Reihe von Besonderheiten auf: Die Maschinen lassen sich mit einem komfortablen Editor leicht erstellen und einfach von anderen Quellen adaptieren. Das Maschinenband besitzt natürlich nicht unendlich viele Zellen. Dennoch ist mit 20.000 Zellen ein unengeschränktes Arbeiten möglich. Die Felder sind zur besseren Orientierung durchnummeriert. Das Band lässt sich zu einer "Schleife" zusammenfügen (Pseudo-unendliches Band), do daß es sich wie ein tatsächlich unendliches Band verhält. Die Maschine läßt sich zusätzlich in Klartext anzeigen und in die Zwischenablage exportieren. Komplexe Maschinen lassen sich aus vorhandenen zusammensetzen. Der Rechnevorgang läßt sich protokollieren. Die Maschinen kann man -wohl einzigartig- bei ihrer Arbeit beobachten. Zur Fehlersuche schaltet man auf den Einzelschritt-Modus ein und muß jeden Schritt einzeln bestätigen. Nicht zuletzt kann man die Geschwindigkeit des jeweiligen Computers genau bestimmen und so ein ungefähre Abschätzung der Rechenzeit vornehmen. Das Busy-Beaver-Problem beeinflußt das natürlich nicht.

Was kommt danach?

Mit der Arbeit an dem Turing-Maschinen-Emulator (TME) begann ich 1994. Das Projekt habe ich jedoch nie vollendet, so daß sich das Programm noch immer in der Beta-Phase befindet. Alle wichtigen Funktionen sind aber schon implementiert, das Arbeiten mit dem Programm ist uneingeschränkt möglich (von ein paar kleinern Bugs abgesehen). Die Dokumentation der Software läßt sehr zu wünschen übrig; sie beschränkt sich auf diese Seite, ich hoffe, das Programm ist einigermaßen selbsterklärend.
Wünschenswert wäre eine Software, die nicht nur binäre Turing-Maschinen bearbeitet, sondern jede beliebige. Da der Code des vorliegenden Programms sehr auf Geschwindigkeit optimiert ist (soweit es bei Visual-Basic Programmen möglich ist), blieb die Flexibilität etwas auf der Strecke. Ein nachträgliches Umstellen auf mehrwertige Maschinen scheint nicht möglich. Für ein neues Projekt fehlt mir die Zeit. Es wird also voraussichtlich keine weitere Version des Emulators geben.

Das eigentliche Programm

Systemvoraussetzungen:

Hinweis:

Der Turing-Maschine-Emulator© kann zu Schulungszwecken kostenlos genutzt und weitergegeben werden. Das Copyright des Programms liegt unabhängig davon weiterhin bei Gerald Pienkowski.

Ich will zuerst einen Screenshot sehen! (18 kByte)

Turing-Maschine-Emulator jetzt herunterladen! (120 kByte)

Installation: Die gezipte Datei in ein seperates Verzeichnis kopieren und mit PKUNZIP entpacken. Das Programm wird mit dem Aufruf der Datei TURING.EXE gestartet.


Noch eine Bitte: Wenn Sie selbst eine interessante Maschine geschrieben haben, schicken Sie sie mir doch. Ich werde dann diese Maschinen sammeln und an dieser Stelle veröffentlichen. Die Dateien mit der Endung TME sind Textdateien und können daher einfach als E-Mail verschickt werden.


E-Mail an mich: Gerald Pienkowski

Zurück zur Homepage Zurück