Turing-Maschine: immer wieder aktuell

25.000 Dollar haben Wolfram Research und Stephen Wolfram ausgelobt und zwar für einen Beweis über die Universalität einer bestimmten Turing-Maschine (mit nur zwei Zuständen und drei Symbolen). Seit Mitte Mai, anlässlich des fünften Jahrestages des Werkes "a New Kind of Science (NKS)" von Stephen Wolfram, läuft nun schon der Wettbewerb, doch noch scheint keine Lösung den Kriterien des hochrangig besetzten Preis-Kommitees (darunter auch "KI-Papst" Marvin Minsky) entsprochen zu haben. Bislang gilt daher weiterhin als kleinste universelle Turing-Maschine nach einem Beweis von Wolfram im NKS diejenige mit zwei Zuständen und fünf Symbolen (oder Farben).

Immer wieder gibt die von Alan Turing beschriebene Turing-Maschine Impulse, ist sie doch sozusagen die logische "Urmutter" eines Computers. Anhand der Turing-Maschine kann man Funktionen als prinzipiell berechenbar klassifizieren oder nicht. Eine Vielzahl von Aufgaben ist seit Turings Veröffentlichung 1936 "On Computable Numbers, with an Application to the Entscheidungsproblem" rund um diese einfache Turing-Maschine gestellt worden, viele davon sind gelöst, andere nicht. Auch der berühmte ungarische Mathematiker von Neumann – in dessen Namen gerade wieder eine Medaille verliehen wurde und dessen Von-Neumann-Prinzip als allgemeine Prozessorgrundlage gilt – hat vermutlich Anleihen bei Turing genommen.

Bei der jetzt gestellten Aufgabe geht es nicht um die berühmten fleißigen Biber, die über Jahrzehnte hinweg viele Rechner zum Glühen gebracht und einst gar die Kollegen von der Byte zu einem aufwendigen Busy-Beaver-Hardware-Projekt veranlasst haben. Nein, es geht um einen Beweis, den man wohl nicht mit Computer-Power wird lösen können. (as)