Diese Grafik ist gegenüber der in der ZEIT erschienenen geändert. Es hatten sich Fehler in die Regeln des Turing-Programms und ihre Ausführung eingeschlichen. Die korrigierte Grafik können Sie hier als PDF herunterladen.

Alan Turing hatte eigentlich keine Rechenmaschine im Kopf, als er die nach ihm benannte Maschine ersann. Der Mathematiker wollte ein Problem lösen, das seine Disziplin seit 36 Jahren umtrieb: Lassen sich alle mathematischen Fragen entscheiden, indem man sie stumpfsinnig ausrechnet? So hieß denn auch seine bahnbrechende Arbeit von 1936 On Computable Numbers, with an Application to the Entscheidungsproblem .

Die Maschine – inzwischen sind konkrete Exemplare gebaut worden – besteht aus wenigen mechanischen Elementen: einem theoretisch endlosen Papierstreifen und einem Schreib-, Lese- und Löschkopf, der auf diesem Streifen Symbole manipulieren kann. Außerdem gibt es einen Transportmechanismus, der das Band um jeweils einen Schritt nach links oder rechts bewegen kann.

In Turings ursprünglicher Arbeit sind es menschliche computers, also "Rechner", die diese Maschine bedienen. Sie handeln entsprechend dem "Programm", das nichts weiter ist als ein Satz von Regeln: Die Maschine kann eine gewisse Zahl von "Zuständen" haben, und für jeden dieser Zustände und jedes Symbol aus dem "Alphabet" der Maschine gibt es eine Verhaltensregel. Zum Beispiel: "Ist die Maschine im Zustand A und steht im aktuellen Feld das Symbol 1, dann ersetze es durch das Symbol 0, gehe einen Schritt nach rechts und wechsle in Zustand B."

Eine Turing-Maschine kann beliebig viele Zustände haben und ein beliebig großes Alphabet. Wir verwenden eine minimale Maschine mit zwei Zuständen und drei Symbolen, die auf den Mathematiker Stephen Wolfram zurückgeht. Sie ist zwar klein, aber universell – das heißt, sie kann im Prinzip alles das, was auch die größten Computer der Welt können. Sie ist nur ein bisschen langsamer.