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

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.

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.

Konzepte für erlebbare Turingmaschinen

Generell soll versucht werden, das Erlebnis der Personen, die in die Rolle der Maschine schlüpfen, so ansprechend wie möglich zu machen. Dabei sollen jedoch auch außenstehende Betrachtende mitverfolgen können, welche Ergebnisse die Aktionen der Agenten hervorrufen.

Lichttunnel

Abbildung 7: Erlebbare Turingmaschine als Lichttunnel (Person aus einem Photo von scott*eric)

Aufbau

Das Speicherband wird von einem nach zwei Seiten offenen Gang/Tunnel gebildet. Die Enden werden entweder durch vorstehende Gang-Elemente oder einer Markierung auf dem Boden in den Raum verlängert, um die Unendlichkeit des Bandes anzudeuten (siehe Abbildung 7).

Die Wände des Ganges bestehen aus weißem, lichtdurchlässigen Material und können von innen heraus mit verschieden farbigem Licht beleuchtet werden. Der Gang selbst wird in Stationen unterteilt, die für die Speicherplätze des Bandes stehen und jeweils seperat beleuchtet werden können.

Um zwei verschiedene Zustände der Speicherplätze zu symbolisieren (z.B. 0 und 1) gibt es zwei verschiedene Farben. Ein leeres Feld wird durch eine weiße Beleuchtung gekennzeichnet.

Die Interessierten schlüpfen in die Rolle des Schreib-/Lesekopfes der Turingmaschine und bewegen sich entlang des Speicherbandes, das heißt, sie laufen im Tunnel von Station zu Station und führen dort den vorgegebenen Programmcode aus.

Dazu gibt es an jeder Station drei Tastschalter, mit denen die Farbe der Beleuchtung der Station geändert werden kann.

Programmanweisungen

Für diesen Aufbau, bei dem die Agenten die Programmanweisungen von Station zu Station mitnehmen müssen, bietet es sich an, diese auf Postkarten zu drucken. Sie können dann am Ende mitgenommen werden und eignen sich dabei gut zur Bewerbung der Turingmaschine.

Programmablauf

Ein möglicher Programmablauf für einen Sortieralgorithmus könnte so aussehen:

• Von einem Computer/Mikrocontroller wird eine zufällige Belegung des Bandes generiert, jede Station wird in einer anderen Farbe beleuchtet, wobei nur die erste und letzte Station weiß bleiben.
• Die Interessierten nehmen die Programmanweisungen und betreten den Tunnel.
• An jeder Station wird die aktuelle Farbe der Station festgestellt und die Farbe entsprechend der Programmanweisungen für den aktuellen Programmzustand geändert. Dazu muss der Knopf für die entsprechende Farbe gedrückt werden.
• Wenn vom Programm eine Zustandsänderung verlangt wird, wird der Zustand geändert.
• Die Agenten gehen entsprechend der Anweisungen eine Station nach rechts oder links.
• Dort führen sie erneut die Programmanweisungen aus. Dies wird so lange wiederholt, bis sie die Farben korrekt sortiert haben und das Programm sie anhalten lässt.

Interaktives scrollbares Speicherband

Abbildung 8: Erlebbare Turingmaschine als interaktives scrollbares Speicherband (Person aus einem Photo von Skeggzatori)

Aufbau

Der Speicherbandinhalt wird von vorne oder hinten auf eine Oberfläche in Bandform projiziert (siehe Abbildung 8). Dabei wäre auch eine Variante ähnlich einer horizontal auf- und abrollbaren Papierrolle denkbar.

Bei einer statischen Leinwand kann der Bandinhalt entlang des Bandes bewegt werden, bei einer rollbaren Leinwand würde parallel dazu die Leinwand mitgerollt werden. Das würde den plastischen Eindruck des Speicherbandes erhöhen, setzt dem Bandinhalt allerdings gleichzeitig Grenzen aufgrund der beschränkten Bandlänge.

In beiden Fällen wird der Inhalt an der Position des Schreib- und Lesekopfes in der Mitte des Bandes hervorgehoben.

In einigen Metern Abstand zum Speicherband steht eine Konsole mit welcher die Agenten das Band steuern und den Inhalt überschreiben können. Die Steuerung erfolgt dabei mit Hilfe eines Touchscreens, der jeweils den Inhalt des Speicherfeldes an der aktuellen Position anzeigt. Soll der Inhalt überschrieben werden, wird der Bildschirm mit einer Wischgeste geleert und der neue Wert von Hand geschrieben. Das Band wird durch Ziehgesten nach rechts oder links bewegt.

Programmanweisungen

In diesem Aufbau bietet es sich an, die Programmanweisungen auf der Bedienkonsole mittels eines seperaten Touchscreens darzustellen, da sie nicht portabel sein müssen. Dies ermöglicht es außerdem, auf dieser Maschine verschiedene Programme auszuführen, da der Bandinhalt und die Programmanweisungen rein digital vorliegen.

Programmablauf

Ein möglicher Programmablauf könnte so aussehen:

• So lange niemand die Steuerung der Turingmaschine übernimmt, läuft sie in einem Demo-Modus und führt Programme von alleine aus.
• Sobald eine interessierte Person an die Maschine harantritt und einen der Bildschirme berührt werden die Instruktionen zum Bedienen der Maschine dargestellt. Der/die Interessierte wählt ein Programm aus, wird zum Agenten und steuert die Maschine durch das Programm.
• Dazu richtet er/sie sich nach den Programminstruktionen und ändert die Feldinhalte entsprechend.
• Notwendige Zustandsänderungen können in diesem Fall auch visuell angedeutet werden, zum Beispiel durch ein Blinken des neu auszuwählenden Zustandes.
• Der/die AgentIn bewegt das Band entsprechend der Anweisungen eine Feld nach rechts oder links.
• Dort führt er/sie erneut die Programmanweisungen aus. Dies wird so lange wiederholt, bis das Programm beendet ist oder abgebrochen wird.

Modelleisenbahn

Abbildung 9: Erlebbare Turingmaschine als Modelleisenbahn (Personen aus einem Photo von dpape)

Aufbau

Auf einem Tisch ist eine Modelleisenbahnstrecke aufgebaut und formt dabei einen geschlossen Ring (siehe Abbildung 9). Fast die gesamte Strecke wird von einem Güterzug eingenommen, der das Speicherband der Turingmaschine repräsentiert. Jeder Wagen steht dabei für einen Speicherplatz auf dem Band.

An einer Stelle der Strecke steht eine Be- und Entladestation mit einer Bedienkonsole (eventuell auch dem Tisch vorgelagert). Hier kann die Bahn entweder mittels eines Steuerhebels oder durch Drücken eines Tastschalters jeweils um einen Güterwagen nach rechts oder links bewegt und der aktuelle Wagen umbeladen werden. Zur Bewegung wird nur ein Kommando für rechts oder links gegeben, die Positionierung der Wagen erfolgt dann automatisch. Die Umladung erfolgt durch das Drücken entsprechender Tastschalter.

Sollten die Güterwagen mit realen Gütern beladen werden, muss eine Möglichkeit gefunden werden, die Be- und Entladung zügig durchzuführen, sowie einen großen Vorrat der Güter parat zu halten. Die Güterwagen könnten jedoch auch mit fiktiven Gütern in der Form von RGB LEDs beladen sein, deren Farbe man an der Ladestation ändern kann. Dies würde zusätzlich ein Zurücksetzen auf einen Startzustand erleichtern.

Programmanweisungen

Auch in diesem Aufbau bietet es sich an, die Programmanweisungen auf der Bedienkonsole statisch darzustellen, da sie nicht portabel sein müssen. Dabei wäre es trotzdem praktisch, den aktuellen Programmzustand etwa durch eine Beleuchtung der Zeile hervorheben zu können.

Programmablauf

Ein möglicher Programmablauf könnte so aussehen:

• Eventuell läuft die Maschine in einem Demo-Modus so lange niemand ihr Steuerung übernimmt. Das geht jedoch nur, wenn ein schnelles Zurücksetzen auf den Startzustand möglich ist.
• Sobald interessierte Personen an die Maschine harantreten und die Steuerung übernehmen, werden sie zu Agenten.
• Dazu richten sie sich nach den Programminstruktionen und ändern die Wagenbelegung sowie den Programmzustand entsprechend.
• Die Agenten bewegen den Gützerzug entsprechend den Anweisungen nach rechts oder links.
• Dort führen sie erneut die Programmanweisungen aus. Dies wird so lange wiederholt, bis das Programm beendet ist oder abgebrochen wird.

Weitere Überlegungen

Analog/Digital

Alle vorgeschlagenen Konzepte setzen die Anwendung eines Rechners bzw. Mikrocontrollers im Hintergrund voraus. Teilweise wäre es möglich, dies zu vermeiden, allerdings nur auf Kosten der Wiederholbarkeit. Sobald mehrere Personen die Turingmaschine erleben wollen, muss es eine Möglichkeit geben, den von vorhergehenden BesucherInnen herbeigeführten Zustand wieder zum Ausgangszustand oder auf einen neuen Anfangszustand zurückzusetzen. Ohne Elektronik müsste das manuell geschehen und würde einen hohen Administrationsaufwand verursachen.

Fehlerfeedback

Die verwendete Steuerungselektronik ermöglicht es, über eine falsche Ausführung der Programmanweisungen zu informieren. Dadurch kann verhindert werden, dass der/die BesucherIn aufgrund seines/ihres Fehlers das Programm nicht zu Ende bringen kann. Das könnte beispielsweise mittels eines Signaltons erfolgen.