GMU:My favorite things/Projekte/Erlebbare Turingmaschinen

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

Abbildung 1: Schematische Darstellung einer Turingmaschine

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

Abbildung 2: Sortieralgorithmus für eine Turingmaschine

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

Idee einer erlebbaren Turingmaschine

Um den Interessierten das Konzept und die Funktionsweise einer Turingmaschine näher zu bringen, sollen sie selbst in die Rolle der Maschine schlüpfen. Dafür bietet sich am ehesten die Postition als Schreib-/Lesekopf an, da dort die Interaktion zwischen Programm und Speicherband stattfindet.

Die Idee einer erlebbaren Turingmaschine konnte bereits von mehreren Personen an einem einfachen Modell ausprobiert werden. Dieses Modell soll im Folgenden beschrieben werden, die teilnehmenden Personen werden dabei als Agenten ('Handelnde') bezeichnet.

Aufbau

Abbildung 3: Modellaufbau

Abbildung 4: Programmanweisungen für den Modellaufbau

In diesem einfachen Modell wird das Speicherband von einer Schnur gebildet, an der Buchstabenkärtchen (A und B, zufällig verteilt) befestigt sind. Die Agenten erhalten einen eigenen Vorrat an Buchstabenkärtchen, die sie während des Programmablaufs mit den bereits hängenden Kärtchen vertauschen können. Die Programminstruktionen liegen schriftlich vor (vgl. Abbildung 4), der aktuelle Maschinenzustand kann mit Hilfe einer Klammer an den Programminstruktionen markiert werden.

Programmierung

Auch hier wurden die Programmanweisungen ähnlich wie in Abbildung 4 angeordnet. Die Anweisungen wurden dabei schriftlich ausformuliert. Zur Verbesserung der Übersichtlichkeit wurden dabei sämtliche Aktionen weggelassen, die keine Änderung des Feldes oder Zustands bewirken.

Beispiel für eine Anweisung:

 Ändere den Wert auf B.
 Ändere deinen Zustand auf 5.
 Gehe weiter nach links.

Ablauf

Abbildung 5: Programmablauf

Abbildung 6: Speicherband nach dem Durchlaufen des Programmes

Die Agenten beginnen an einer beliebigen Stelle des Bandes (links vom ersten leeren Feld am Ende der Zeichenkette, sonst funktioniert das Programm nicht) im Programmzustand 1. Im folgenden sehen sie jeweils in der Programmtabelle nach und handeln entsprechend der Instruktionen für den abgelesenen Wert und ihren gegenwärtigen Zustand so lange, bis das Programm einen HALT verlangt. Damit sollten sie die Buchstaben auf dem Band sortiert haben.

Ergebnisse

Alle Personen gaben nach einem erfolgreichen Durchlaufen des Programmes an, das Konzept der Turingmaschine besser verstanden zu haben als nach einer rein theoretischen Erklärung.

Dieses einfache Modell einer erlebbaren Turingmaschine soll im nächsten Abschnitt zu drei verschiedenen präsentierbaren Konzepten ausgearbeitet werden.