GMU:My favorite things/Projekte/Erlebbare Turingmaschinen: Difference between revisions

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.

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.

[[Image:Md-turing-aufbau.png|thumb|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).

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.

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)

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

[[Image:Md-turing-programm.png|thumb|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.

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

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.

[[Image:Md-turing-modell-1.png|thumb|Abbildung 3: 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.

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.

   Gehe weiter nach '''links'''.

[[Image:Md-turing-modell-2.png|thumb|Abbildung 5: Programmablauf]]

[[Image:Md-turing-modell-3.png|thumb|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.

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.

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.

[[Image:Md-turing-lichttunnel.png|thumb|Abbildung 7: Erlebbare Turingmaschine als Lichttunnel (Person aus einem Photo von scott*eric)]]

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).

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

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.

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

* 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.

[[Image:Md-turing-scrollband.png|thumb|Abbildung 8: Erlebbare Turingmaschine als interaktives scrollbares Speicherband (Person aus einem Photo von Skeggzatori)]]

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.

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.

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.

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.

* Dort führt er/sie erneut die Programmanweisungen aus. Dies wird so lange wiederholt, bis das Programm beendet ist oder abgebrochen wird.

[[Image:Md-turing-eisenbahn.png|thumb|Abbildung 9: Erlebbare Turingmaschine als Modelleisenbahn (Personen aus einem Photo von dpape)]]

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.

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.

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.

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.

* Dort führen sie erneut die Programmanweisungen aus. Dies wird so lange wiederholt, bis das Programm beendet ist oder abgebrochen wird.

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.

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.