// SCINEXX — SPAZIO & SCIENZA
Eine einzige Billardkugel kann theoretisch jede Berechnung ausführen
Eine einzelne Kugel, die in einer speziell geformten ebenen Fläche von festen Wänden abprallt, kann mathematisch jede Berechnung einer universellen Turingmaschine nachbilden. Damit werden selbst einfache Fragen über manche solcher Bahnen algorithmisch unentscheidbar. Ein allgemeines Verfahren, das für jeden zulässigen Fall sicher vorhersagt, wohin die Kugel gelangt oder ob ihre Bahn periodisch wird, kann es dann nicht geben.
Bellaterra (Spanien). Billardsysteme gehören zu den einfachsten Modellen der klassischen Mechanik, denn eine punktförmige Kugel bewegt sich geradlinig und wird an festen Wänden spiegelnd reflektiert. Sind Form des Tisches und Anfangszustand exakt bekannt, ist die weitere Bewegung vollständig durch feste Regeln bestimmt. Trotzdem kann ihre langfristige Entwicklung grundsätzlich schwerer vorherzusagen sein, als es die aus der Chaostheorie bekannte Empfindlichkeit gegenüber kleinsten Abweichungen vermuten lässt.
Eine neue mathematische Arbeit zeigt nun, dass schon ein zweidimensionaler Billardtisch mit nur einer Kugel die Schritte einer universellen Turingmaschine exakt nachbilden kann. Dieses abstrakte Rechenmodell beschreibt, was sich grundsätzlich durch einen Algorithmus berechnen lässt. Kann ein dynamisches System die Zustandswechsel einer solchen Maschine vollständig simulieren, gilt es als Turing-vollständig und kann damit jede algorithmisch ausführbare Berechnung nachbilden.
Für ihre Konstruktion übersetzen Eva Miranda und Isaac Ramos die Zustände und Rechenoperationen einer Turingmaschine in geometrische Abschnitte und Korridore eines ebenen Billardtisches. Die Position der Kugel entlang bestimmter Strecken codiert dabei zugleich den Inhalt des Speicherbands und die Position des Lese- und Schreibkopfs. Parabolische sowie besonders fein strukturierte Wandstücke lenken die Bahn so um, dass jeder Durchgang durch einen Korridor genau die jeweils nächste Rechenoperation ausführt.
Entscheidend ist, dass die Autoren dafür reversible Turingmaschinen verwenden, bei denen sich jeder Rechenschritt eindeutig zurückverfolgen lässt. Dadurch können verschiedene Rechenwege geometrisch wieder zusammengeführt werden, ohne dass unterschiedliche Maschinenzustände dieselbe Bahn erhalten. Weil jede gewöhnliche Berechnung durch eine geeignete reversible Maschine ausgeführt werden kann, reicht diese Konstruktion aus, um universelles Rechnen mit einer einzigen Kugel zu verwirklichen.
Der dafür nötige Tisch ist allerdings kein gewöhnlicher Billardtisch, sondern besitzt eine speziell entworfene Begrenzung mit Strukturen auf immer feineren Größenskalen. An den meisten Stellen lässt sich diese Wand mathematisch glätten, während an zwei Grenzpunkten unendlich viele immer kleinere Strukturen zusammenlaufen. Die Arbeit ist deshalb vor allem ein Existenzbeweis dafür, wie viel rechnerische Komplexität bereits in einem sehr einfachen deterministischen Bewegungsmodell stecken kann.
Aus der Turing-Vollständigkeit folgt eine schärfere Grenze als bloße praktische Unvorhersagbarkeit. Miranda und Ramos koppeln den Lauf der Kugel an Turings Halteproblem, für das es nachweislich keinen Algorithmus gibt, der jede mögliche Eingabe korrekt entscheidet. Hält die simulierte Maschine an, erreicht die Kugel in der Konstruktion einen dafür vorgesehenen Abschnitt, kehrt ihre Bewegungsrichtung um und schließt schließlich eine periodische Bahn.
„Chaos setzt der Präzision eine Grenze; Unentscheidbarkeit setzt eine logische Grenze“, erklärt Prof. Eva Miranda von der Universitat Politècnica de Catalunya (UPC).
Hält die simulierte Maschine dagegen nicht an, erreicht die Kugel diesen besonderen Abschnitt nicht und die zugehörige Bahn wird nicht periodisch. Damit lassen sich Fragen wie „Erreicht die Kugel jemals einen bestimmten Bereich?“ oder „Wird ihre Bahn periodisch?“ nicht durch einen einzigen Algorithmus für alle derartigen Billardtische entscheiden. Für viele konkrete Fälle kann eine Antwort trotzdem gefunden werden, doch ein universelles Verfah