Direkt zum Inhalt

Die Turing-U-Bahn

Kann eine Modelleisenbahn denken|? Vielleicht nicht, aber alles berechnen, was berechenbar ist – wenn man beliebig viele Schienen und Weichen zur Verfügung hat.

Die Tweedle-Zwillinge und ich standen eingezwängt in der überfüllten Berliner U-Bahn. Delia Tweedle wurde einfach nur Dee genannt, und folglich mußte ihr Bruder Dum heißen. Wie üblich fielen sie einander dauernd ins Wort.

"Nun, wenn das Universum algorithmisch ist, dann hat die starke künstliche Intelligenz..."

"Mach doch nicht so große Worte, Dee. Du meinst doch, Computer, die denken können..."

"... müssen im Prinzip möglich sein."

"Warum?" fragte ich.

"Wenn unser Universum algorithmisch ist..."

"Könnte man einen Computer so programmieren, daß er es simuliert..."

"Mit allem, was darin ist, einschließlich uns, wie wir diese Unterhaltung führen", folgerte Dee.

"Falls das stimmt, dann kann ein U-Bahn-Netz denken – wenn es hinreichend groß ist", sagte ich. "Ziemlich l-a-n-g-s-a-m, aber dennoch."

"Dummes Zeug!" rief Dee aus. "Eine U-Bahn kann nicht denken."

"Vielleicht nicht. Aber rechnen. Das habe ich gerade in einem faszinierenden Artikel in ,Eureka' gelesen. Er stammt von Adam Chalcraft und Michael Greene und handelt von den Rechenfähigkeiten von Zuganlagen."

"Meinst du Modellbahnen? Die sind doch heute ohnehin computergesteuert. Klar kann der Computer rechnen."

"Schon recht, aber ich meine die Anlage selbst: Gleise, Weichen, eine kleine Lok, Tunnel durch Gipsberge, Plastik-Fachwerkhäuschen..."

"Niedlich."

"Aber das reicht – und ein richtiges U-Bahn-Netz schon lange. Es rechnet zwar nicht ganz so schnell wie der neueste Parallelcomputer, aber theoretisch sind seine Fähigkeiten dieselben. Ein Computer ist nichts weiter als ein riesiges Netzwerk mit Schaltern, die es selbst umstellen kann; und Züge können während der Fahrt Weichen umstellen. Chalcraft und Greene haben sich nun gefragt: Wenn man einen genügend großen Vorrat an geraden und gebogenen Schienen, Brücken und Weichen verschiedener Art zur Verfügung hat, außerdem eine einzige Lokomotive und kein weiteres rollendes Material – welche Berechnungen kann man ausführen, wenn man die Anlage nur richtig aufbaut?"

"Wieso sollte ein Zug rechnen können?" rätselte Dee. "Das ist doch nur ein Ding, das sich auf Schienen bewegt."


Mehr oder weniger faule Weichen

"Elektronen sind auch nur Dinger, die sich entlang von Drähten bewegen, aber Computer rechnen damit", entgegnete ich. "In beiden Fällen ist Rechenfähigkeit eine Frage der Interpretation. Rechnen heißt, eine Eingabe (input) nach vorgeschriebenen Regeln in die richtige Ausgabe (output) zu verwandeln. Beide bestehen aus Binärzeichen – Nullen und Einsen. Man bezeichne die beiden Stellungen einer Weiche mit 0 und 1. Das Einlesen des Inputs besteht darin, daß man gewisse Weichen mit der Hand entsprechend einstellt. Dann läßt man den Zug durch die Anlage fahren; dadurch ändern sich manche Weichenstellungen, was wiederum den Weg des Zuges ändert. Schließlich wird er auf ein Abstellgleis geleitet und hält an: Das Programm ist beendet. Aus den Stellungen derselben Weichen liest man den Output ab."

"Na gut. Aber funktioniert das auch wirklich?"

"Ich will mit dem einfachsten Schalter beginnen, der faulen Weiche. Stell dir ein Y-förmiges Stück Gleis vor. Ein Zug, der in das Y von unten einfährt, verläßt es durch den oberen linken oder rechten Zweig, je nach der Stellung der Weiche, und läßt diese Stellung bestehen. Nennen wir die Stellungen rechts und links. Aber ein Zug, der von oben einfährt, stellt – falls nötig – sich die Weiche auf seinem Weg zurecht und verläßt sie durch den unteren Zweig" (Bild 1 links).

"Das kenne ich", sagte Dee. "Das kommt bei Straßenbahnen häufig vor."

Ich fuhr fort: "Der nächste Weichentyp ist die Federweiche. Im Gegensatz zur faulen Weiche hat sie eine Rückstellfeder, so daß jeder von unten einfahrende Zug die Weiche stets durch denselben oberen Zweig verläßt" (Bild 1 Mitte).

"Bis jetzt nicht besonders aufregend."

"Der dritte Typ ist eine Flip-flop-Weiche. Die Züge fahren stets von unten ein und verlassen sie abwechselnd durch den linken und den rechten Zweig" (Bild 1 rechts). Wir liefen scheppernd in die Station Alexanderplatz ein. "Die große Frage ist nun: Kann man mit diesen Komponenten einen Computer bauen?"

"Was für einen Computer?"

"Eine Turing-Maschine. Der britische Mathematiker Alan Turing (1912 bis 1954) hat bewiesen, daß sein extrem einfaches Modell eines rechenfähigen Systems im Prinzip dasselbe leistet wie jeder beliebige programmierbare Digitalcomputer. Stellt euch eine Turing-Maschine als einen Kasten vor, der sich auf einem sehr langen Band bewegen kann. Das Band ist in Felder eingeteilt, die jeweils das Zeichen 0 oder 1 enthalten. Im Prinzip ist es unendlich lang; aber wenn ihr das nicht mögt, genügt es, wenn ihr bereit seid, bei Bedarf Felder anzufügen.

Der Kasten kann endlich viele innere Zustände annehmen. Für jeden inneren Zustand und jedes Zeichen, das sich gerade genau unter ihm befindet, ist ihm eine gewisse Folge von Aktionen vorgeschrieben, und zwar:

- ,laß das augenblickliche Zeichen stehen' oder ,ändere es';

- ,dann geh ein Feld nach rechts' oder ,nach links';

- ,dann nimm einen bestimmten inneren Zustand an, bevor du den nächsten Schritt ausführst.'

Oder der Befehl lautet einfach ,Stop', und die Rechnung ist beendet" (vergleiche die zweidimensionale Verallgemeinerung, Turmiten, in Spektrum der Wissenschaft, November 1989, Seite 8).

Die Bahn war längst wieder in Bewegung, überfuhr mit großem Lärm zahlreiche Weichen, und die anderen Fahrgäste schauten uns schon mißtrauisch an, während wir uns schreiend zu verständigen suchten.

"Gib uns bitte ein Beispiel", bat Dum.

"Gern. Hier ist eine typische Liste solcher Regeln für eine Turing-Maschine mit den drei Zuständen 1, 2 und 3:

- ,Zustand 1, Zeichen 0: Ändere das Zeichen, geh nach links, nimm Zustand 2 ein.

- Zustand 1, Zeichen 1: Stop.

- Zustand 2, Zeichen 0: Laß das Zeichen stehen, geh nach rechts, nimm Zustand 3 ein.

- Zustand 2, Zeichen 1: Ändere das Zeichen, geh nach rechts, nimm Zustand 2 ein.

- Zustand 3, Zeichen 0: Ändere das Zeichen, geh nach rechts, nimm Zustand 1 ein.

- Zustand 3, Zeichen 1: Laß das Zeichen stehen, geh nach links, nimm Zustand 2 ein.' "

"Na schön. Und was berechnet die Maschine?"

"Keine Ahnung. Am besten probierst du es aus. Die meisten sinnvollen Programme benötigen sowieso mehr als drei innere Zustände."

"Aber wo bleibt die Modellbahn?"

"Kommt sofort. Die Zeichen, die anfangs auf dem Band stehen, sind die Eingabe für diesen Computer. Die Liste der Anweisungen, was in welchem Zustand und bei welchem Symbol unter dem Kasten zu tun ist, ist das Programm; und die Zeichen auf dem Band, wenn die Maschine anhält, sind die Ausgabe. Erstaunlicherweise können solche primitiven Geräte jeden denkbaren Algorithmus ausführen. Jetzt brauchen wir nur noch eine Gleisanlage, die eine gegebene Turing-Maschine simuliert."

"So tut, als ob sie eine Turing-Maschine wäre?"

"Wenn sie so tut, dann ist sie eine Turing-Maschine. Laßt euch von dem Wort ,simulieren' nicht in die Irre führen."

"Ah ja."

"Das Problem läßt sich in eine Reihe von Teilaufgaben zerlegen. Erstens: Konstruiere eine Gleisanlage, welche die Rolle des Kastens spielen kann. Statt ein Band zu verwenden, stöpseln wir einfach eine riesige Zahl solcher Kästen zusammen. Jeder Kasten hat mehrere Gleisanschlüsse, links und rechts jeweils gleich viele – einen für jeden inneren Zustand" (Bild 2 oben).

"Statt daß der Kasten sich auf dem Band bewegt..."

"... bewegt sich der Zug entlang der Kästen", fuhr Dum begeistert fort.

"Man kann genau sagen, an welchem Feld des Bandes gerade gearbeitet wird..."

"... wenn man sieht, in welchem Kasten sich der Zug befindet. Pfiffig."

"Aber was ist in den Kästen drin?" fragte Dee. "Schrödingers Katze?"

"Ich werde es schrittweise beschreiben. Die Anschlußgleise dienen sowohl zum Ein- als auch zum Ausfahren, und es soll für den Kasten einerlei sein, aus welcher Richtung der Zug kommt. Deshalb setzt man den Kasten aus einer äußeren Hülle und einem inneren Kern zusammen. Die Hülle leitet Züge von links und rechts auf gemeinsamen Gleisen in den Kern und aus diesem wieder heraus zum linken oder rechten Nachbarkasten, je nach dem Ergebnis des Turing-Programms. Wir können nun also die Hülle vernachlässigen und uns auf den Kastenkern konzentrieren" (Bild 2 unten).

"Du brauchst bestimmt..." begann Dum.

"Unterprogramme", ergänzte Dee. Die beiden hatten wie immer vorausgedacht. Ein Unterprogramm ist ein Teil eines Programms, der wiederholt verwendet werden kann, indem man ihn aus einem anderen Programmteil aufruft. Wenn ein Unterprogramm seine Arbeit getan hat, macht das aufrufende Programm genau dort weiter, wo es seine Arbeit für das Unterprogramm unterbrochen hat. Aus mehreren Unterprogrammen kann man komplexe Programmsysteme zusammensetzen.


Lese- und schreibfähige Gleisanlagen

"Na klar", stimmte ich zu. "Man kann ein Unterprogramm basteln, indem man eine vollständige Gleis-Unteranlage an eine ganze Reihe von faulen Weichen anhängt. Dann kommt der Zug herein, stellt dabei die Weichen und durchfährt die Unteranlage, bis er berechnet hat, was immer das Unterprogramm berechnen soll. Schließlich kommt er dorthin zurück, wo er hergekommen ist, weil er die faulen Weichen bei der Einfahrt entsprechend gestellt hat" (Bild 3 links oben).

"Ach so."

"Ein Einzelteil brauchen wir noch: einen Lese-/Schreibkopf. Wenn ein Zug von links in dieses Stück Gleisanlage einfährt, verläßt er es nach rechts auf Gleis 0 oder 1, je nach der Stellung der faulen Weiche W; diese steht für das Zeichen auf dem zugehörigen Feld des Bandes. Von links einfahren bedeutet also Lesen. Schreiben – genauer: das Zeichen auf dem Band ändern – tut man durch Einfahren von oben. Ein solcher Zug verwandelt eine Null in eine Eins und umgekehrt und fährt unten wieder aus. Die Flip-flop-Weiche oben wird anfänglich so gestellt, daß der erste von oben einfahrende Zug die Weiche W umschaltet" (Bild 3 links unten).

Ich fuhr fort, die Modellbahn von Chalcraft und Greene zu beschreiben: "Aus all diesen Teilen kann man nun den inneren Kern eines Kastens zusammenbauen. Man wird ein paar Brücken brauchen, um Überkreuzungen zu vermeiden, aber das können wir außer acht lassen. Der Kern enthält eine Reihe von Lese-/Schreibköpfen, einen für jeden internen Zustand des Kastens. Deren Ausgabegleise 0 und 1 führen entweder direkt zu einem der Ausgabegleise des Kerns oder über eine Federweiche und eine faule Weiche in ein Unterprogramm, das den Zustand des Feldes auf dem Band ändert, oder aber zu dem Unterprogramm STOP, das den Zug zur Endstation leitet" (Bild 3 rechts).

"Das will ich sehen", unterbrach Dee. "In deinem Beispiel lautet eine Regel: ,Zustand 1, Zeichen 0: Ändere das Zeichen, geh nach links, nimm Zustand 2 ein.' Wie funktioniert das?"

"Sich im Zustand 1 zu befinden heißt, daß der Zug von links auf Gleis 1 in den inneren Kern einfährt. Die vorige Zelle hatte ihn nämlich auf Zustand 1 gesetzt, indem sie ihn auf Ausfahrgleis 1 entlassen hatte. In unserem Falle steht in der aktuellen Zelle eine Null, das heißt, alle faulen Weichen W in ihren Lese-/Schreibköpfen stehen auf 0. Der Zug fährt also in den obersten Lese-/Schreibkopf ein, verläßt ihn rechts auf Gleis 0 und kommt über eine Federweiche und eine faule Weiche in das Unterprogramm ,Zeichen ändern'. Über eine weitere Federweiche fährt er abwärts durch alle Lese-/Schreibköpfe und ändert deren Zustände von 0 auf 1. Damit enthält das aktuelle Feld also eine Eins. Der Zug fährt links von den Lese-/Schreibköpfen wieder nach oben, verläßt das Unterprogramm auf dem Gleis, auf dem er eingefahren ist, und fährt schließlich auf Gleis 2 links aus dem Kern aus. Das heißt, er fährt zum linken Nachbarkasten im Zustand 2, wie verlangt war" (gelbe Linie in Bild 3 rechts).

"Hübsch. Nehmen wir die Regel ,Zustand 2, Zeichen 0: Laß das Zeichen stehen, geh nach rechts, nimm Zustand 3 ein.' Der Zug kommt auf Gleis 2 herein und verläßt den Lese-/Schreibkopf auf Gleis 0, das direkt zum Ausgabegleis 3 rechts führt. Und er kommt nicht einmal in die Nähe der Unterprogramm-Schleife; der Zustand des Kastens bleibt also erhalten" (rote Linie in Bild 3 rechts).

"Richtig", stimmte Dum zu. "Und genauso klar ist, daß die Regel ,Zustand 1, Zeichen 1: Stop' wie gewünscht funktioniert. Wenn der Zug auf Gleis 1 hereinkommt und den Lese-/Schreibkopf auf Gleis 1 verläßt, fährt er direkt zur Endstation."

"Genau. Man muß die Gleise nur gemäß den Regeln der Turing-Maschine zusammensetzen."

"Ist dir klar", fragte Dee besorgt, "daß damit gezeigt ist, daß das Verhalten eines Zuges in einer Gleisanlage unentscheidbar ist?"

"Na klar", meinte Dum. "Turing hat gezeigt, daß das Halteproblem für Turing-Maschinen formal unentscheidbar ist. Man kann eine Turing-Maschine bauen, bei der nicht von vornherein entscheiden kann, für welche Inputs die Rechnung irgendwann beendet ist."

"Und das bedeutet für die entsprechende Gleisanlage, daß man nicht weiß, ob der Zug je die Endstation erreicht."

"Das ist aber beunruhigend", bemerkte ich. "Eigentlich hat mich die formale Unentscheidbarkeit theoretischer mathematischer Fragen nie sonderlich gestört. Aber wenn man ein mechanisches System bauen kann, eine Modelleisenbahn meinetwegen, deren Arbeitsweise vollkommen transparent ist, aber trotzdem nicht zu sagen vermag, ob der Zug jemals ankommt..."

"A propos...", unterbrach Dee.

"Seit dem letzten Halt ist es schon ziemlich lange her", ergänzte Dum.

Ich wischte die beschlagene Scheibe sauber und blickte hinaus: "Hmm, wir fahren sehr langsam. Ich sehe nichts als ein großes Schild, auf dem die Ziffer 1 steht. Und – da hinten ist ein Schild, auf dem steht ,Flip-flop 7743A/91'."

"Au weia. Dee bekommt Zustände, wenn die U-Bahn zwischen den Stationen anhält", flüsterte Dum.

"In letzter Zeit sind zahlreiche Verbindungen im U-Bahnnetz neu eröffnet worden", überlegte ich. "Vielleicht hat es jetzt die Turing-Schwelle überschritten und die Stufe der künstlichen Intelligenz erreicht."

Dee wurde kreidebleich. In diesem Augenblick öffnete sich die Verbindungstür, und ein Uniformierter betrat den Wagen.

"Wir haben ein kleines technisches Problem", lächelte er. "Nicht weiter schlimm, aber wir müssen eine Weile langsam fahren." Dee seufzte vor Erlösung. "Was ist, geht es der jungen Frau nicht gut?"

"Ach", antwortete Dum, "sie dachte gerade, wir seien in einer Turing-Maschine mit künstlicher Intelligenz steckengeblieben."

"Wir sind kein Touring-Unternehmen", gab der Kontrolleur indigniert zurück. "Wir sind öffentlicher Nahverkehr, da weiß man, wann man Feierabend hat."

Aber dann sah er unsere zweifelnden Blicke und machte sich hastig auf, die übrigen Fahrgäste zu informieren.

Literaturhinweise

- Der neue Turing Omnibus. Von Alexander K. Dewdney. Springer, Heidelberg. Erscheint voraussichtlich im Februar 1995.

– Train Sets. Von Adam Chalcraft und Michael Greene in: "Eureka", Band 53, Seiten 5 bis 12, 1994. Zu beziehen über Arts School, Bene't Street, Cambridge CB3 3PY, England; Internet-Adresse: archim@phx.cam.ac.uk.


Aus: Spektrum der Wissenschaft 2 / 1995, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!