Mystery Tour

Am berühmtesten ist das "Game of Life" [Ga87], das von John Horton Conway, einem hervorragenden Mathematiker an der Universität von Cambridge, endeckt wurde. Dabei handelt es sich ganz klar um zellulare Automaten. Aber wie kommen Züge und Ameisen dazu, mit solchen Automaten in Verbindung gebracht zu werden. Und überhaupt eine Zuganlage die rechnet [St95/2] und eine Ameise auf "Mystery Tour" [St95/8], [Ru95/9], [Ru95/10]. Bewegen wir uns da am Rande des Chaos [Ho95]?

Züge können rechnen

Literurquelle und Bilder: [St95/2]

In Eureka haben Adam Chalcraft und Michael Greene schon die Rechenfähigkeit von Zügen beschrieben. Man muß nur aus Zügen einen Computer bauen. Nur welchen? Eine Turing-Maschine - ganz klar. Stellt man sich eine Turing-Maschine als sich bewegender Kasten vor, der sich auf einem sehr langen Band bewegen kann, erhält man ein extrem einfaches System, das im Prinzip das selbe leistet wie ein Digitalcomputer. Wie simuliert aber ein Zug eine Turing-Maschine? Das Band ist in Felder eingeteilt, die jeweils das Zeichen 0 oder 1 enthalten und wird durch eine Reihe gleicher Kästen ersetzt. Der Kasten kann endlich viele innere Zustände annehmen. Und je nach Zustand und Zeichen unter ihm ist eine gewisse Aktion definiert. Anstatt den Lese/Schreibkopf (in diesem Fall ein Teil des Kasten) über das Band zu bewegen, lassen wir durch eine Reihe von gleichen Kästen einen Zug fahren. Damit ein Zug fahren kann, benötigt man Weichen. Es gibt drei verschieden Arten von Weichen:

faule Weichen
Federweichen und
Flip-flop-Weichen

Modellbahn von Chalcraft und Greene

Faule Weichen

Das ist ein Y-förmiges Stück gleich, in das der Zug von unten einfährt und je nach Einstellung links bzw. rechts oben verläßt. Kommt ein Zug von links bzw. rechts oben, muß er die Weiche wieder nach unten verlassen und legt so die Weichenstellung fest.

Federweichen

Die Federweiche hat eine Feder, die die Weiche - wenn sie von einem von oben einfahrenden Zug verstellt wurde - wieder in die alte Stellung zurückbringt. Ein von unten einfahrender Zug verläßt die Weiche also immer nach links oder nach rechts.

Flip-flop-Weiche

Diese Art von Weiche stellt sich nach jeder Durchfahrt in eine andere Richtung.

Flip-Flop-Weiche, Federweiche und Faule Weiche

Kasten

Wie bereits erwähnt, wird das Band einer Turing-Maschine durch eine Reihe gleicher Kästen ersetzt. Jeder Kasten hat links und rechts jeweils gleich viele Gleisanschlüsse. Im Kasten befindet sich ein Kern, der bestimmte Zustandsüberführungsregeln enthält. Der Kern hat links Eingänge, die die momentanen Zustände darstellen und unten Ausgänge die die folgenden Zustände darstellen und über eine Hülle zum Ausgang des Kasten führen. Im Kern sind die Lese/Schreibköpfe untergebracht, die für die Zustandsüberführung zuständig sind und den Zug lenken. Der Kasten selbst ist also ein zellularer Automat, die Ein- und Ausgänge die Verbindung zu seinen Nachbarn.

Inhaltsverzeichnis

Hülle

Da Züge zu einem Kasten aus beiden Richtungen kommen können, benötigt man eine Hülle, die die Züge richtig lenken. Sie sollen immer von links in den Kern fahren, kommen von Kern unten heraus und sollen den Kasten wieder links bzw. rechts verlassen.

Hülle mit Kern und oben aneinandergereite Kästen, auch jeweils mit Hülle und Kern

Lese/Schreibkopf

Der Lese/Schreibkopf ist ein Bauteil, daß aus Weichen zusammengestellt wird. Gelesen wird, indem man von links einfährt. Jenachdem ob man über eine faule Weiche rechts oben oder rechts unten ausfährt wird vom Band (Gleis) eine 1 oder eine 0 gelesen. Geschrieben wird, indem ein Zug von oben einfährt und eine Flip-flop-Weiche das Zeichen auf dem Band ändert.

Kern

Aus Weichen und Lese/Schreibköpfen kann der Kern zusammengebaut werden. Die Ausgabegleise der Lese/Schreibköpfe führen entweder direkt zu Ausgabegleisen des Kerns oder aber über Federweichen in ein Unterprogramm, das die Zustände des jeweiligen Feldes auf dem Band auf dem sich der Kasten befindet ändert. Eine weitere Alternative gibt es: der Zug kann zur Endstation STOP geleitet werden.

Beispiel zu Kern für untenstehende Regeln. Eine Weiche mit Balken bedeutet, daß man in diese Richtung nicht abbiegen, aber aus dieser Richtung in die Weiche hineinfahren darf. Der rote Strich stellt die Fahrt des Zuges zu Zustand 2, Zeichen 1 dar.

Regeln

Um die Berechnung durchführen zu können benötigt man Regeln. Hier eine Liste mit Regeln für eine Turingmaschine, die drei innere Zustände 1, 2 und 3 besitzt und für einen Input bzw. Output, der aus 0 und 1 besteht:

Zustand 1, Zeichen 1: Laß das Zeichen stehen, gehe nach rechts, nimm Zustand 3 ein.
Zustand 1, Zeichen 0: Ändere das Zeichen, gehen nach links, nimm Zustand 1 ein.
Zustand 2, Zeichen 1: Ändere das Zeichen, gehe nach links, nimm Zustand 1 ein.
Zustand 2, Zeichen 0: Laß das Zeichen stehen, gehe nach links, nimm Zustand 2 ein.
Zustand 3, Zeichen 1: Laß das Zeichen, gehe nach rechts, nimm Zustand 2 ein.
Zustand 3, Zeichen 0: Stop

Setzt man nun die Gleise gemäß den Regeln einer Turing-Maschine zusammen, könnte ein Zug rechnen. (Beispiel). Kann aber ein Zug eine Turing-Maschine simulieren, kann man auch eine Gleisanlage bauen, bei der nicht entschieden werden kann, für welche Eingabe der Zug die Endstation erreicht. Hat also ein Zug ein Halteproblem? Gibt es Bahnhöfe mit Gleisanlagen, von denen aus die Züge nie ankommen?

Inhaltsverzeichnis