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.

==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===

[[Image:Md-turing-aufbau.png|thumb|Abbildung 1: Schematische Darstellung einer Turingmaschine]]

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

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)

===Programm===

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

===Aufbau===

[[Image:Md-turing-modell-1.png|thumb|Abbildung 3: Modellaufbau]]

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

===Ablauf===

[[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]]

===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===

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

====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:

===Interaktives scrollbares Speicherband===

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

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

===Modelleisenbahn===

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

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

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