Alan Turings Rechenmaschine

Ein Computer, zumindest ein herkömmlicher seriell arbeitender Digitalrechner, kann genau genommen nicht viel: Er geht von einem Zustand in einen anderen über, transformiert Nullen in Einsen und umgekehrt, und der ganze Trick des Programmierens liegt darin, ihn diese elementaren Prozessen oft genug und vor allem in der richtigen Reihenfolge abarbeiten zu lassen, was er dann mit hoher Geschwindigkeit und Präzision auch tut. Dabei weiß der Computer nichts von dem, was er berechnet. Er kennt die Bedeutung seiner Daten nicht, und die Rede davon, dass »der Computer rechnet«, ist im Grunde eine anthropomorphistische Deutung des Zuschauers oder Benutzers. Der Computer transformiert Muster, die für ihn bedeutungslos sind, und er kann nur auf Unterschiede in der Struktur, nicht in der Bedeutung seiner Daten zugreifen. Um die bunte und bisweilen wenig geordnete Welt kognitiver Prozesse auf diese simplen Vorgänge abbilden zu können, muss man sie entsprechend formalisieren.

Die Idee, das menschliche Denken als einen formalisierbaren Prozess aufzufassen, bei dem es nicht auf die Inhalte, sondern nur auf die Struktur ankommt, kann man bis zur Syllogistik, der Argumentationslehre, des griechischen Philosophen Aristoteles zurückverfolgen. Er unterschied dort verschiedene Verfahren, auf korrekte Art aus gegebenen Prämissen Schlussfolgerungen zu ziehen. Sein berühmtestes Beispiel ist das folgende: Aus den Sätzen »Sokrates ist ein Mensch« und »Alle Menschen sind sterblich« folgt »Sokrates ist sterblich«. Dem liegt ein |31|Muster zugrunde, das für alle Sätze ungeachtet ihres Inhalts gilt: Aus »A ist B« und »Alle B sind C« folgt »A ist C«. Alle Schlüsse dieser Form, die auf wahren Prämissen beruhen, liefern wahre Ergebnisse – ungeachtet ihres Inhalts. Solche formalen Prozeduren sind von Nutzen, wenn man es mit so komplexen Argumenten zu tun hat, dass man intuitiv, durch Nachdenken über den Inhalt des Behaupteten, nicht mehr entscheiden kann, ob ein Argument gültig ist oder einen Trugschluss darstellt.

Der Gedanke, man könne die Richtigkeit von Sätzen durch ein mechanisches Verfahren objektiv beweisen, faszinierte auch den Philosophen Raimundus Lullus. Er arbeitetet im 13. Jahrhundert auf Mallorca an einer Denkmaschine, die mithilfe drehbarer Drei- und Vierecke den Sarazenen die Wahrheit der christlichen Lehre dartun sollte (Flasch 1986, S. 389). Gottfried Wilhelm Leibniz, der im 17. Jahrhundert an Lullus’ Arbeiten anknüpfte, hatte keine missionarischen Absichten, dafür aber die Hoffnung, durch seine cogitatio symbolica Meinungsverschiedenheiten, Streit, vielleicht sogar Kriege vermeiden zu können. Die cogitatio ist eine Denkmethode nach dem Vorbild des Rechnens. Die Richtigkeit von beliebigen Aussagen sollte mittels eines rein formalen Verfahrens überprüfbar sein, so dass Meinungsverschiedenheiten durch ein objektives Verfahren beigelegt werden könnten (Krämer 1991, S. 2).

Leibniz’ Idee war, dass man Denken als einen Prozess der »Verknüpfung und Substitution von Zeichen« verstehen könne. Zeichen stehen für das, worüber Menschen nachdenken, »Verknüpfung und Substitution« stehen für das, was beim Nachdenken mit diesen Zeichen geschieht. Ließen sich diese Prozesse ausbuchstabieren und in die Form eines präzisen Algorithmus bringen, müsste der Denkende sich nur blind an diese Regeln halten, und er könnte gar nicht anders, als beim Nachdenken richtige Ergebnisse zu erzielen.

»Verknüpfung und Substitution« bezeichnet man in Bezug |32|auf Computer heute als Datenverarbeitung oder als Berechnung. Bis Mitte der 1930er Jahre war allerdings alles andere als klar, was Rechnen genau bedeuten sollte und was als berechenbar zu betrachten war. Den Begriff der Berechenbarkeit präzise bestimmt zu haben, ist das Verdienst des englischen Mathematikers Alan Turing. Als Rechnen gelten seit Turing Prozesse, wie sie in einer Turingmaschine ausgeführt werden, als berechenbar gilt, was in einer Turingmaschine berechnet werden kann. Eine Turingmaschine ist kein echtes Gerät, es ist das Konzept einer Rechenmaschine, die mit einfachsten Mitteln Funktionen berechnen kann. Die von Turing und dem Mathematiker Alonso Church formulierte Church-Turing-These besagt, dass es für jede berechenbare Funktion eine Turingmaschine gibt, die diese auch berechnen kann.

Turing orientierte sich bei der Konzeption der nach ihm benannten Maschine am gewöhnlichen Rechnen mit Bleistift und Papier und an Verbalprotokollen von Berichten, die Menschen während des Lösens von Rechenaufgaben geliefert hatten: »Will man erreichen, daß sich eine Maschine bei einer schwierigen Operation wie ein menschlicher Rechner verhält, muß man ihn fragen, wie er sie ausführt, und die Antwort dann in die Form einer Befehlsliste bringen. Die Aufstellung von Befehlslisten bezeichnet man gewöhnlich als ›programmieren‹.« (Turing 1967, S. 112)

Eine Turingmaschine besteht aus einem unendlich langen Band – deshalb kann sie nicht hergestellt werden –, das in gleich große Felder unterteilt ist, und einem Schreib-Lesekopf, der über diesem Band angebracht ist. Der Schreib-Lesekopf muss in der Lage sein, das Band um jeweils ein Feld nach rechts oder links zu bewegen und zu stoppen. Außerdem muss er die auf dem Band aufgedruckten Zeichen erkennen, löschen oder selbst drucken können. Nun fehlt noch eine Kontrolleinheit, die den Schreib-Lese-Kopf steuert. Auf den Feldern des Speicherbandes sind entweder Zeichen eines vorgegebenen Alphabets |33|aufgedruckt oder sie sind leer. Im einfachsten Fall enthält das »Alphabet« gerade ein Zeichen, etwa einen Schrägstrich oder eine Eins. Dann operiert die Turingmaschine mit einem Unärcode, im Unterschied zu dem bei Computern gängigen Binärcode, der zwei Zeichen umfasst. Eine so genannte Maschinentafel bestimmt, wie sich die Turingmaschine verhalten soll. Sie enthält für jeden Zustand, den die Maschine einnehmen kann, und für jedes Zeichen, das auf dem Speicherband stehen kann, Anweisungen, was zu tun ist. Dass die Maschine unterschiedliche logische Zustände annehmen kann, ist erforderlich, damit sie je nach Bedarf auf unterschiedliche Weise auf das Vorliegen desselben Zeichens reagieren kann, eine »1« also entweder löschen oder ignorieren kann. Befindet sich die Maschine im Zustand 1, besagt die Maschinentafel zum Beispiel: »Wenn das Feld, über dem der Lesekopf steht, leer ist, drucke eine ›1‹ und bleibe im Zustand 1. Steht auf dem Feld eine ›1‹, dann gehe ein Feld nach rechts und gehe in den Zustand 2 über.« Befindet sich die Maschine in Zustand 2, besagt die Maschinentafel: »Ist das Feld leer, stoppe und gehe in Zustand 1 über, steht auf dem Feld eine ›1‹, lösche sie und bleibe in Zustand zwei.« Die Maschinentafel enthält also das Programm der Turingmaschine.

Eine Turingmaschine mit der genannten Maschinentafel ist eine so genannte Nachfolgemaschine, das heißt, sie berechnet den Nachfolger jeder Zahl, die Funktion n+1. Dazu beginnt sie im Zustand 1 auf dem ersten leeren Feld rechts neben einer Reihe von Einsen, die im Unärcode die Zahl codieren, deren Nachfolger es zu finden gilt, und druckt auf dieses Feld eine »1«. Dann geht sie, immer noch im Zustand 1, ein Feld nach rechts und wechselt in den Zustand 2. Findet sie das Feld, über dem der Lesekopf nun steht, leer vor, bleibt sie stehen und geht in der Zustand 1 über. Damit ist die Aufgabe erledigt: Die Kette der Einsen ist um eine weitere »1« verlängert worden und damit der Nachfolger der gegebenen Zahl im Unärcode dargestellt|34|. Findet die Maschine dagegen eine »1« auf dem betreffenden Feld vor, löscht sie diese zuerst und bleibt dann stehen (nach Beckermann 1998, S. 159f.)

Eine solche Turingmaschine ist auf eine einzige Art der Berechnung spezialisiert, denn sie muss für jede Art von Berechnung, die sie ausführt, mit einer eigenen Maschinentafel versehen werden. Turing erdachte aber auch eine universelle Rechenmaschine, die jede dieser speziellen Turingmaschinen simulieren kann. Dazu erhalten die einzelnen Turingmaschinen Codenummern, die an die Stelle der jeweiligen Maschinentafeln treten und das Verhalten der universellen Turingmaschine zusammen mit dem zu berechnenden Argument festlegen. Das Faszinierende an der Idee der universellen Turingmaschine besteht darin, dass es nur einer wohl definierten Menge an Symbolen und einer ebenso wohl definierten Menge an Anweisungen (Algorithmen) bedarf, um jeden durch diese Elemente darstellbaren Vorgang in einer Maschine nachzubilden: Denken, soweit es sich an die Regeln der Logik hält, Sätze, sofern sie grammatisch korrekt sind, Berechnungen, soweit sie korrekt verlaufen.

Die Bedeutung der Turingmaschine für die Kognitionswissenschaft erschließt sich im Zusammenhang mit der von Allen Newell und Herbert Simon formulierten Hypothese der physikalischen Symbolsysteme (PSSH, Physical Symbol System Hypothesis;...