Die fertige Turingmaschine ohne Gleis
Sebastian Flothow <sebastian@flothow.de>
Erstellt 2010-07-05, zuletzt geändert 2010-07-20
Die Lego-Turingmaschine wurde durch ein ähnliches Projekt an der Universität Århus [VGNH09] inspiriert1. Dies hat Jan Gampe und mich veranlasst, eine vergleichbare Turingmaschine aus Lego-Mindstorms-Komponenten als Exponat zu konstruieren, das Interesse an der Informatik als Studienfach wecken soll. Gleichzeitig ist ein Einsatz in der Lehre vorgesehen, um die Turingmaschine als wesentliches Konzept der theoretischen Informatik anschaulich zu machen.
Dieser Artikel beschreibt die Hardware der entstandenen Turingmaschine, eine Beschreibung der von Jan Gampe entwickelten Software findet sich in [Gam10].
Die dänische Turingmaschine weist zwei Eigenschaften auf, die der Anschaulichkeit abträglich sind: Schreib- und Leseeinheit sind versetzt angebracht, so dass zwischen dem Lesen und Schreiben derselben Zelle eine Fahrbewegung nötig ist. Außerdem können in jeder Zelle nur zwei verschiedene Zustände dargestellt werden; ein Nachteil, der dadurch ausgeglichen wird, dass mehrere Zellen zu einer logischen Zelle zusammengefasst werden können. Beides bringt aber mit sich, dass die Maschine Bewegungen ausführt, die sich nicht aus dem Turingprogramm ergeben, worunter die Nachvollziehbarkeit leidet.
Für die hier vorgestellte Maschine wurde daher gefordert, dass nur solche Bewegungen durchgeführt werden sollen, die durch einen Zustandswechsel des Turingprogramms ausgelöst werden. Konkret bedeutet dies, dass Schreib- und Lesemechanismus am gleichen Ort arbeiten können müssen ohne sich gegenseitig zu behindern, und dass drei Zustände pro Zelle darstellbar sein sollen, um ein angemessenes Bandalphabet zu bieten (0, 1 und ein Leersymbol)2.
Um in einer Ausstellungsvitrine ein möglichst langes Band unterbringen zu können, sollte die Maschine in der Lage sein, auf einem U-förmigen Band zu arbeiten. Das Durchfahren der Kurve setzt auf jeden Fall einen kurzen Radstand voraus, angestrebt wurde außerdem die Möglichkeit, Bandsymbole in der Kurve unterzubringen. Weiterhin sollte die Maschine möglichst schmal sein, um den Platzbedarf in der Vitrine zu minimieren
Eine weitere wichtige Anforderung ist die Eignung zum unbeaufsichtigten Dauerbetrieb. Dazu muss die Mechanik so beschaffen sein, dass im laufenden Betrieb und ohne Rückgriff auf externe Informationen eine Kalibrierung der Positionsmessungen möglich ist, idealerweise alleine mit den in den Mindstorms-Motoren enthaltenen Wegmessern, und Anfang und Ende des Bands eindeutig erkennbar sind3. Zusätzlich ist eine Netzstromversorgung nötig, was bei Verwendung der Lego-Komponenten den Einsatz des Mindstorms-Akkupacks erzwingt. Da das fertige Exponat auch einen per Netzwerk erreichbaren Rechner umfasst wäre es unter Umständen vorteilhaft ohne Akkupack auszukommen, da dann nach einem eventuellen Stromausfall Turingmaschine und Rechner gleichzeitig in einem definierten Zustand neustarten würden.
Die fertige Turingmaschine ohne Gleis
Als Band der Turingmaschine werden Lego-Schienen des Typs 7896 verwendet, da passend zu diesen auch Kurvenstücke existieren. Zwischen den Schienen sind Freiräume von jeweils 2x4 LE4, in denen sich jeweils ein Bandsymbol5 der Grundfläche 2x2 LE befindet, das drei verschiedene Positionen einnehmen kann durch Verschieben um je 1 LE rechtwinklig zur Fahrtrichtung.
Fahrwerk und Gestell der Turingmaschine müssen zwischen den Schienen eine beträchtliche Bodenfreiheit aufweisen, damit die Bandsymbole frei positioniert werden können und durch Fahrbewegungen der Machine nicht unerwünscht bewegt werden. Entgegen der Gepflogenheiten beim Bau von Schienenfahrzeugen befindet sich der untere Teil des Gestells, an dem die Räder befestigt sind, auf beiden Seiten außerhalb der Schienen, auch die Radkränze liegen außen. Tests haben gezeigt, dass der Antrieb eines einzelnen Rads unzureichend ist; andererseits ist es nicht möglich zwei Räder direkt mit einer Achse zu verbinden, ohne dass diese mit den Bandsymbolen kollidiert. Letztlich wurde daher eine Portalachsenkonstruktion gewählt, bei der zwei Räder von einer darüber liegenden Achse angetrieben werden.
Für die Positionierung der Maschine auf den Bandzellen wurde das Konzept optischer Marker übernommen; da in den aktuellen Mindstorm-Kästen statt des älteren Helligkeitssensors ein Farbsensor enthalten ist konnte es um eine Erkennung der Bandenden erweitert werden: Die erste und letzte Zelle des Bandes sind durch eine rote bzw. blaue Marke gekennzeichnet, die übrigen durch grüne Marken. Der erste Ansatz, die Marken als Verlängerung der Gleisschwellen anzubringen, ist daran gescheitert dass die Maschine seitlich der Gleise keine ausreichende Bodenfreiheit hat; stattdessen befinden sich die Marken jetzt zwischen den Schwellen, also jeweils neben einer Bandzelle. Der Farbsensor ließ sich allerdings nicht so an der Maschine anbringen, dass er die Marke neben der gerade bearbeiteten Zelle liest, da der Bereich seitlich davon für die Bewegungen des Schreibmechanismus frei bleiben muss. Daher wurde der Farbsensor außerhalb des Arbeitsbereichs platziert, infolgedessen müssen die Marken um zwei Zellen versetzt am Gleis angebracht werden.
Kraftübertragung zur Antriebsachse. Das Rad ist mit dem unteren grauen Zahnrad verbunden.
Rückseite der gleichen Baugruppe. Die Antriebsachse verläuft oberhalb der Räder.
Gegenüberliegende Seite der Antriebsachse
Maschine auf dem Gleis. Die Antriebsachse bietet genug Freiraum für die Bandsymbole.
Zur Bestimmung der Position eines Bandsymbols werden zwei nebeneinander montierte Mindstorms-Taster verwendet. Da deren Betätigungselemente abgeschrägte Kanten aufweisen, wäre es denkbar, die Taster feststehend zu montieren, so dass sie bei Fahrbewegungen über die Bandsymbole schleifen. Gerade diese Abschrägung führt jedoch dazu dass ein in der Mitte positioniertes Bandsymbol keinen der beiden Taster betätigt; die Betätigung beider Taster ist jedoch wünschenswert, um diesen Fall von einem fehlenden Bandsymbol unterscheiden zu können. Da feststehende Taster weitere Schwierigkeiten versachen würden – die Konstruktion des Schreibmechanismus würde aufwändiger, und es müsste das Umkippen von Bandsymbolen vermieden werden – wurde auf die Taster jeweils ein Stein von 2x2 LE aufgesetzt, wodurch die Lücke zwischen den Tastern geschlossen wird, und die Tasterbaugruppe beweglich angebracht. Durch den der dänischen Turingmaschine ähnlichen Schwenkmechanismus können die Taster näherungsweise senkrecht auf ein Bandsymbol abgesenkt werden; um zu verhindern dass die trotzdem vorhandene horizontale Komponente der Bewegung zum Umfallen des Bandsymbols führt wurden sowohl die Steine auf den Tastern als auch die Bandsymbole mit ebenen Deckflächen versehen.
Die Ruhestellung des Schwenkmechanismus entspricht dem oberen Anschlag, der ohne Vorwissen über die momentane Position eindeutig angefahren werden kann, die Selbstkalibrierbarkeit ist damit gegeben. Zu beachten ist jedoch, dass durch übermäßiges Absenken der Taster die Maschine aus den Schienen gehoben werden kann, die Abwärtsbewegung sollte daher auf einen von der Ruhestellung aus gemessenen festen Drehwinkel begrenzt werden, der experimentell ermittelt werden muss.
Die beiden Lesetaster mit aufgesetzten 2x2-Legosteinen und glatten Deckflächen
Lesen eines Bandsymbols
Der Schreibmechanismus muss so beschaffen sein, dass er zumindest in Ruhestellung das Absenken der Leseeinheit gestattet. Eine einfache von oben greifende Zange wie bei der dänischen Maschine kommt daher nicht in Frage, stattdessen fiel die Wahl auf einen seitlich verschiebbaren Rahmen, durch dessen Öffnung die Lesetaster hindurchfahren können, wenn sich der Rahmen in mittlerer Position befindet. Der Rahmen selbst liegt oberhalb der Bandsymbole, um bei Fahrbewegungen nicht mit diesen zu kollidieren. Seitlich trägt der Rahmen nach unten ragende Klauen, die die Bandsymbole verschieben. Dabei ist wichtig, dass die Klauen möglichst weit unten an den Bandsymbolen angreifen, um diese nicht umzukippen.
Der Schreibrahmen muss über eine große Distanz beweglich sein, größer als die Breite des Rahmens. Um diese Beweglichkeit zu erreichen laufen die Führungsstangen des Schreibrahmens in ihrerseits beweglichen Läufern. Angetrieben wird der Schreibrahmen über eine Zahnstange, wobei zwei Zahnräder nötig sind, damit immer mindestens eins in die Zahnstange greift. Der Verstellweg ist mechanisch begrenzt, so dass eine Kalibrierung zur Laufzeit möglich ist. Der Motor muss allerdings mit relativ geringer Leistung betrieben werden, da sonst in den Endstellungen des Schreibrahmens die Zahnräder aus der Zahnstange springen.
Der Schreibrahmen in der vorderen Endposition
Antrieb des Schreibrahmens. Die drei oberen Zahnräder dienen dem gemeinsamen Antrieb der beiden unteren Zahnräder.
Die beiden unteren Zahnräder greifen in die dahinterliegende Zahnstange
Schreiben eines Bandsymbols
Da die Maschine eine kleine Grundfläche haben muss, ist sie relativ hoch. Massereiche Komponenten sind die Motoren, von denen zwei weit oben liegen, sowie der NXT-Brick, der zuoberst angebracht ist. Dies führt zu einem hoch liegenden Schwerpunkt, insbesondere wenn der NXT-Brick mit Akkupack bestückt ist. Bei einigen Konstruktionsentwürfen war nicht sichergestellt dass alle Räder Bodenkontakt haben; im jetzigen Zustand ist das Problem akzeptabel gelöst, indem der NXT-Brick möglichst dicht an der nichtangetriebenen Achse platziert und die Befestigung so konstruiert wurde, dass er in Schritten von 1 LE seitlich versetzbar ist. Dennoch ist eine vorsichtige Ansteuerung der Motoren nötig, um ein Entgleisen zu verhindern.
Der Antrieb des Schreibrahmens ist derzeits nur mäßig zufriedenstellend, da zum einen die Zahnräder dazu neigen Zähne der Zahnstange zu überspringen, und zum anderen nach längerem Betrieb der Rahmen angefangen hat sich zu verkanten. Letzteres ist darauf zurückzuführen, dass der Rahmen nur an einer Seite angetrieben wird; beide Probleme lassen sich wahrscheinlich lösen, indem anstelle von Zahnstangen Ketten verwendet werden und der Rahmen an beiden Seiten angetrieben wird. Da hierfür jedoch größere Umbauten auch am Rahmen der Maschine nötig wären und das Problem erst spät erkannt wurde wurde hierauf verzichten; das Verkanten des Rahmens konnte verhindert werden, indem durch Besprühen der Führungsschienen mit Silikonspray die Reibung reduziert wurde. Die aufgetragene Silikonschicht hat sich bei ausgedehntem Betrieb der Maschine als verschleißfest erwiesen, so dass dieser Ansatz als dauerhafte Lösung in Betracht kommt.
Das größte noch bestehende Probleme ist die Abschirmung des Farbsensors zum Schutz vor Umgebungslicht, die aufgrund der Funktionsweise des Sensors nötig ist. Der eigentliche Sensor ist eine einzelne Fotodiode, die keine Farben unterscheiden kann, die Farberkennung beruht auf einer ebenfalls im Sensormodul enthaltenen RGB-LED. In jedem Messzyklus wird die Helligkeit bei roter, grüner, blauer und ausgeschalteter Beleuchtung gemessen und aus diesen Messwerten die Farbe ermittelt. Dieser Ansatz setzt aber voraus, dass die LED des Sensormoduls mindestens ähnlich hell ist wie das Umgebungslicht, bei hellerer Umgebung (z.B. Sonneneinstrahlung, aber auch schon unter einer Tischleuchte mit 40-Watt-Glühlampe) versagt die Farbunterscheidung. Bisher wurden Bürstenleisten sowie Hülsen aus Stoff und Klebeband als Abschattung getestet – diese haben zwar das Sensorproblem behoben, aber die Fahrbewegung blockiert, eine Lösung steht also noch aus.
[Gam10] Gampe, Jan: Theoretische Konzepte und Entwicklung einer Software für eine mechanische Turingmaschine. Bachelor Thesis, Hochschule RheinMain (2010)
[VGNH09] Vester, Mikkel ; Geggi, Sean ; Nissen, Anders ; Have, Martin: Lego of Doom. http://legoofdoom.blogspot.com
1. Man beachte insbesondere das hervorragende Video dort, das die Vorzüge der Maschine anpreist.
2. Prinzipiell hat der Umfang des Bandalphabets keinen Einfluss auf die Mächtigkeit der Maschine, allerdings ist der Umgang mit sehr kleinen Alphabeten eher unerfreulich. Da außerdem bei einem mechanischen Modell notgedrungen nur ein endliches Band verwendet werden kann, beeinflusst die Größe des Alphabets sehr wohl die Mächtigkeit der Maschine. Im übrigen kommt die Verwendung von 0 und 1 sowie einem Leersymbol der Denkweise des typischen Informatikers entgegen.
3. Das einfache Mitführen eines Positionszählers von einer definierten Ausgangsposition aus scheidet aus, da die Maschine ohne Vorwissen über ihre Position starten können soll, und außerdem auch im Betrieb Fehler wie das „Übersehen” einer Zelle erkennbar sein müssen.
4. Lego-Einheit, definiert über die Abmessungen des Einheitssteins (Typ 3005). Da dieser nicht würfelförmig ist ergeben sich zwei Einheiten, die horizontale LE (8 mm) und die vertikale LE (9,6 mm). Sofern nicht anders angegeben ist in diesem Text mit LE die horizontale LE gemeint.
5. Der Begriff „Bandsymbol” wird hier etwas abweichend von seiner eigentlichen Bedeutung verwendet: Strenggenommen ist es die Position des beweglichen Steins, die ein Bandsymbol repräsentiert; im Laufe des Projekts hat sich der Begriff jedoch auch als Bezeichnung für den beweglichen Stein selbst etabliert.