Erlebbare Turingmaschinen
Moritz Dreßler, Oktober 2011

Vielen NichtinformatikerInnen fällt es schwer, das Konzept einer Turingmaschine nachzuvollziehen, auch oder gerade weil das Prinzip eines Algorithmus auf Unverständnis stößt. Im Folgenden soll die Idee einer erlebbaren Turingmaschine erläutert werden, in der Interessierte selbst einen Teil der Aufgaben der Maschine übernehmen, um dadurch besser zu verstehen, was passiert.

Turingmaschine

Das 1936 von Alan Turing beschriebene Modell der Turingmaschine ist, einfach formuliert, ein theoretisches Gerät zur Simulation von Algorithmen. Im Folgenden soll es kurz vereinfacht dargestellt werden.

Aufbau

Eine Turingmaschine besteht aus einem unendlichen und in gleichgroße Felder eingeteilten Speicherband, einem entlang des Bandes beweglichen Schreib- und Lesekopf sowie einem Programm zur Steuerung des Kopfes (vgl. Abbildung 1).

Funktionsweise

Während der Ausführung eines Programms auf der Turingmaschine wird der Wert des Feldes unter dem Schreib-/Lesekopf ausgelesen und dem Programm entsprechend neu beschrieben. Dann wird der Kopf in der vom Programm vorgegeben Richtung links oder rechts entlang des Speicherbandes ein Feld weiter bewegt.

Das Programm kann dabei verschiedene Zustände einnehmen und je nach Zustand unterschiedliche Handlungen hervorrufen, auch wenn der abgelesene Wert der gleiche ist.

Jeder Schritt der Turingmaschine kann dabei unterteilt werden in:

Feststellen, in welchem Zustand sich die Maschine gerade befindet
Auslesen des aktuellen Feldes

Aus dem aktuellen Zustand und dem ausgelesenen Wert ergibt sich laut Programm:

neuen Zustand setzen (kann auch der gleiche Zustand sein)
das Feld neu beschreiben (kann auch der gleiche Wert sein)
den Lesekopf nach links bzw. rechts bewegen oder die Maschine anhalten.

Sollte die letzte Richtungsangabe keinen Halt verursachen, wird der Zyklus für das erreichte Feld erneut durchlaufen.

Programm

Ein Programm für eine Turingmaschine lässt sich als Tabelle darstellen und soll hier am Beispiel eines Sortieralgorithmus gezeigt werden (Siehe Abbildung 2). Mit Hilfe dieses Algorithmus lässt sich eine zufällige und beliebig lange Reihe von zwei verschiedenen Zeichen (hier 0 und 1) in eine Ordnung bringen (hier von links nach rechts erst 0 dann 1). Die zu sortierende Reihe muss hierbei von leeren Feldern eingeschlossen sein, damit die Turingmaschine weiß, wo die Reihe anfängt und aufhört.

Beispiel für einen Speicherbandinhalt vor dem Durchlauf des Programmes:

 1 0 0 1 1 1 0 1 0 1 0 0

Der Speicherbandinhalt nach dem Durchlauf des Programmes:

 0 0 0 0 0 0 1 1 1 1 1 1