Turing: Die Universalmaschine

1937 veröffentlichte Alan Turing (1912–1954) einen zunächst wenig beachteten Aufsatz zu einem Problem der mathematischen Grundlagenforschung und – über den ursprünglichen Kontext hinaus – mit einer nachhaltigen Langzeitwirkung für die Informatik, Philosophie und Psychologie. 

Das Problem hatte David Hilbert der Fachwelt aufgegeben (und es war eine nur auf die Mathematik bezogene und somit etwas bescheidenere Fassung der "ars iudicandi" von Leibniz): Läßt sich ein allgemeines, eindeutiges und endliches Entscheidungsverfahren – in heutiger Terminologie kurz: ein Algorithmus – dafür finden, ob eine beliebige (...) mathematische Aussage beweisbar (...) ist oder nicht? 

Turing bewies – wie kurz vorher schon Alonzo Church – in seinem Aufsatz, daß es kein solches Verfahren geben kann. 

Noch folgenreicher als dieses Resultat waren aber für ein Nachdenken über das Denken die dabei von ihm benutzten Mittel. Der Nachweis, daß es kein solches Verfahren geben kann, daß also alle denkmöglichen Verfahren versagen werden, erfordert als generelle, allgemeingültige Aussage eine präzise Definition dieser Verfahren. 

Intuitiv war klar, worum es ging: Nach endlich vielen Schritten sollte durch die eindeutige und zwangsläufige Anwendung genau definierter Regeln, ohne weiteres Nachdenken, Intuition, Phantasie, also ganz mechanisch, ein eindeutiges Ergebnis vorliegen, berechnet worden sein. Um diese intuitive Vorstellung zu präzisieren, überlegte Turing, auf welche elementaren Operationen das allgemeine Vorgehen eines menschlichen Rechners (engl.: computer) reduziert werden kann, der (durch regelgeleitete Symbolmanipulation wie z. B. schriftliches Dividieren) Zahlen oder Formeln berechnet:

"Rechnungen werden für gewöhnlich in der Weise ausgeführt, daß bestimmte Symbole auf ein Stück Papier geschrieben werden. Wir wollen annehmen, daß dieses Stück Papier kariert ist, wie das Rechenheft eines Kindes. 

Beim elementaren Rechnen wird zuweilen die Zweidimensionalität des Papiers ausgenutzt. Aber diese Verwendungsart ist keineswegs unvermeidlich, und ich denke, man wird sich darüber einig sein, daß die Zweidimensionalität des Papiers für die Rechnung nicht wesentlich ist. Ich gehe daher davon aus, daß die Rechnung auf eindimensionalem Papier ausgeführt wird, d. h. auf einem durch Felder unterteiltem Band. [ . . . ] 

Das Verhalten des Rechnenden wird zu jedem Zeitpunkt durch die wahrgenommenen Symbole und durch seinen momentanen "Geisteszustand" bestimmt. [ . . . ] 

Wir stellen uns die vom Rechnenden durchgeführten Operationen in "einfache Operationen" aufgeteilt vor, die so elementar sind, daß es schwer fällt, sie sich noch weiter aufgespalten vorzustellen. 

Jede dieser Operationen besteht in irgendeiner Veränderung im physikalischen System, das vom Rechnenden und seinem Band gebildet wird. 

Wir kennen den Zustand des Systems, wenn wir die Symbolfolge auf dem Band, die Symbole, die vom Rechnenden (gegebenenfalls mittels eines besonderen Befehls) wahrgenommen werden, und den Geisteszustand kennen. 

Wir nehmen an, daß in einer einfachen Operation nicht mehr als ein Symbol verändert wird. Alle anderen Veränderungen können auf einfache Veränderungen dieser Art zurückgeführt werden. [ . . . ] 

Die einfachen Operationen müssen neben diesen Symbolveränderungen auch Distributionswechsel der wahrgenommenen Felder umfassen. [ . . . ] Es ist möglich, daß einige dieser Veränderungen notwendig eine Veränderung des Geisteszustands implizieren.

Als allgemeinste einfache Operationen müssen daher die beiden folgenden gelten: (A) Eine mögliche Symbolveränderung . . . zusammen mit einer möglichen Veränderung des Geisteszustands. (B) Eine mögliche Veränderung . . .wahrgenommener Felder zusammen mit einer möglichen Veränderung des Geisteszustandes. 

Die tatsächlich durchgeführte Operation wird . . . durch den Geisteszustand des Rechnenden und durch die wahrgenommenen Symbole bestimmt. Insbesondere bestimmen sie den Geisteszustand des Rechnenden, nachdem die Operation ausgeführt worden ist".

Turing präzisierte nun den Begriff der "mechanischen" Berechenbarkeit, indem er eine automatische Maschine ersann, die analog zum so beschriebenen Vorgehen eines menschlichen Rechners arbeitet. 

Eine Maschine, "die nur über eine endliche Zahl von Zuständen q1, q2, . . . , qR verfügt" und die durch ein beidseitig beliebig verlängerbares "Band" versorgt wird, "das (analog zum Papier) durch sie hindurchläuft und in Sektionen (,Felder‘ genannt) aufgeteilt ist, von denen jedes ein ,Symbol‘ tragen kann" (aus einer endlichen Menge). Die Maschine verfügt über einen Lese- und Schreibkopf, durch den jeweils ein Feld bearbeitet und das dort vorhandene Symbol erkannt und durch ein anderes (oder gleiches) ersetzt werden kann. "Die Maschine kann auch das Feld ändern, das sie abtastet, aber nur durch Verschieben um eine Stelle nach rechts oder links. Zuzüglich zu jeder dieser Operationen kann der [Maschinen-] Zustand geändert werden." 

Ein typischer Arbeitsschritt einer solchen "Turingmaschine" besteht also im Drucken eines Symbols Si, einer Bewegung nach links oder rechts und dem Übergang in einen neuen Zustand qj (ein möglicher Zustand ist, daß die Maschine ihre Arbeit beendet). Wenn nun in einer sogenannten "Maschinentafel" für jede mögliche Kombination von Zustand der Maschine und auf dem Band vorgefundenem Symbol ein solcher Arbeitsschritt festgelegt wird (etwa q4 S2 : S5 Lq3 dafür, daß die Maschine, wenn sie im Zustand q4 auf dem aktuellen Feld das Symbol S2 vorfindet, dort das Symbol S5 druckt, mit dem Lesekopf ein Feld nach links rückt und in den Zustand q3 übergeht), ist eine spezielle Turingmaschine und damit ein eindeutiger automatischer Ablauf definiert, durch den die ursprüngliche Bandinschrift verändert wird und der möglicherweise nach endlich vielen Schritten stoppt. 

Wenn das der Fall ist, so Turings Vorschlag, soll die dann durch die Bandinschrift repräsentierte Zahl oder Formel "berechenbar" heißen, und er zeigte, als negative Lösung des Entscheidungsproblems, daß es genau beschreibbare Probleme gibt, die in diesem Sinne nicht berechenbar sind. Weiter konnte er nachweisen, daß einige Turingmaschinen bei geeigneter "Programmierung" durch eine entsprechende Bandbeschriftung die Arbeit jeder beliebigen Turing-Maschine übernehmen können ("universelle Turingmaschinen"). 

Seine These: Alles, was man vernünftigerweise als "berechenbar" (computable) bezeichnen kann, ist durch eine (und damit wirklich durch eine) Turing-Maschine berechenbar. 

Turing hat eine Maschine völlig neuer Art ersonnen. Eine Maschine, die nicht die physischen Kräfte der Menschen steigert, sondern eine informationsverarbeitende Maschine, mit diskreten Zuständen und für diskrete Symbole, tauglich für jede denkbare Berechnung, kurz: den digitalen Universalcomputer. 

Turing mag bei der Konzeption seiner Maschine (Papierband, Schreib- und Lesekopf) von Fernschreibern und Schreibmaschinen (auch hier wird ja je nach durch Betätigen der "Umschalter-" bzw. "Shift-Taste" hergestellten inneren "Zustand" ein jeweils anderes Zeichen gedruckt) inspiriert gewesen sein, aber er hat nie den Versuch gemacht, seine Maschine in dieser Form auch wirklich zu bauen. Sie diente ihm nur zur präzisen Darstellung einer logischen Funktion, die durch ganz unterschiedliche Strukturen physikalisch realisiert werden kann (sei es mechanisch, hydraulisch oder elektronisch, und auch ein "Mensch, ausgestattet mit Papier, Bleistift und Radiergummi sowie strikter Disziplin unterworfen, ist in der Tat eine Universalmaschine").