Kleinste universelle Turing-Maschine gefunden

25.000 US-Dollar hat sich ein 20-jähriger Student aus England mit der Lösung eines Problems der theoretischen Informatik verdient, nämlich dem Beweis, dass eine bestimmte Turing-Maschine universell ist. Ausgelobt hatten den Preis der Erfinder des Computeralgebrasystems Mathematica, Stephen Wolfram und seine Firma Wolfram Research, im Mai 2007 anlässlich des fünften Jahrestags der Veröffentlichung von A New Kind of Science (NKS), eines Buches, in dem Wolfram auf dem Studium zellulärer Automaten einen ganz neuen Zweig der Wissenschaft begründen will.

Der englische Logiker, Mathematiker und Kryptanalytiker Alan Turing nahm Anfang des 20. Jahrhunderts mit den nach ihm benannten Maschinen die Funktionsweise heutiger Computer vorweg: Maschinen nämlich, die einem festen Regelsatz gehorchend (zum Beispiel dem x86-Befehlssatz), gefüttert mit einem Programm und Eingabedaten beliebige Berechnungen durchführen können. Turing-Maschinen sind ein theoretisches Konstrukt, das mit überraschend einfachen Mitteln universelle Berechnungen ermöglicht: Ein unendliches Band als Speicher, auf dem Zeichen eines bestimmten (endlichen) Alphabets stehen können, ein Zeiger auf eine bestimmte Stelle auf diesem Band, eine (ebenfalls endliche Menge) von Zuständen und schließlich ein Satz von Regeln, der vorgibt, was die Maschine in einem Schritt tun soll, wenn sie in einem bestimmten Zustand ein bestimmtes Zeichen vorfindet (nämlich ein Zeichen schreiben, in einen anderen Zustand wechseln und den Zeiger nach links oder rechts bewegen).

In seiner Original-Veröffentlichung aus dem Jahre 1936 brauchte Turing noch vier Seiten, um eine universelle Maschine für beliebige Berechnungen anzugeben. Später, 1962, konstruierte KI-Papst Marvin Minsky eine universelle Turing-Maschine mit nur sieben Zuständen und einem vierelementigen Alphabet, also nur 28 Regeln für die Zustandsübergänge. 40 Jahre lang war das die kleinste bekannte universelle Maschine, bis Wolfram in NKS eine mit nur zwei Zuständen und fünfelementigem Alphabet, anschaulicher dargestellt als fünf verschiedene Farben, angab.

Eine Maschine mit nur zehn Regeln, die beliebige Berechnungen ermöglicht, so etwas stachelt Theoretiker natürlich zu der Frage an, ob es nicht mit noch weniger geht und welches die kleinste solche Maschine ist. Wolfram zeigte in NKS, dass zwei Zustände und zwei Farben nicht genügen, fand aber eine Maschine mit zwei Zuständen und drei Farben, von der er intuitiv annahm, dass sie universell sein könnte, womit die kleinstmögliche universelle Turing-Maschine gefunden wäre.

Stephen Wolframs universelle 2,3-Turing-Maschine (Quelle: Wolfram Research) Das hat Alex Smith aus Birmingham nun bewiesen und damit die 25.000 Dollar eingeheimst. Sein 55-seitiges Paper soll in Complex Systems veröffentlicht werden.

Der Student sah das Problem als interessantes Puzzle und dachte zunächst, diese Maschine müsste eigentlich so einfach sein, dass man das Gegenteil beweisen könne, also dass sie nicht universell ist. Aber das Maschinchen widersetzte sich diesem Versuch und zeigte gewisse Verhaltensmuster, die doch ein bisschen komplizierter waren. Damit gelang Smith der Beweis der Universalität: Er konstruierte eine Art Compiler, der Code für eine als universell bekannte Maschine für die Wolframsche 2,3-Maschine umsetzte. Der entstehende Code ist in der Regel unglaublich umständlich und ineffizient, aber das spielt keine Rolle, es zählt die Theorie: Damit ist bewiesen, dass die eine Maschine zu denselben Berechnungen in der Lage ist wie die andere. Eine offizielle Preisverleihung soll in einigen Wochen an Turings Wirkungsstätte Bletchley Park stattfinden. (bo)