In einer im Mai 1936 bei der London Mathematical Society eingereichten und 1937 publizierten Arbeit definiert und erläutert Alan M. Turing (1912–1954) seine Idee der allgemeinen Symbole verarbeitenden Maschinen und begründet mit diesen rechnenden Maschinen („computing machines“) die bis heute darauf fußende Theorie der Berechenbarkeit („computability“). Mit diesen, ab dato nach ihm benannten speziellen Turing-Maschinen (TMn, Singular TM) und der in seinem Aufsatz detailliert beschriebenen „universal computing machine“ (dt. Universellen Turing-Maschine, UTM) sowie mit dem Einsatz eines Diagonalverfahrens, das an Georg Cantor (1845–1918) angelehnt ist (vgl. Wiener/Bonik/Hödicke, Einführung Turing-Maschinen, Kapitel 16 und 17), beweist Turing, dass das „Entscheidungsproblem“ in David Hilberts (1862–1943) formalistischem Programm zu einer mathematischen Logik keine Lösung haben kann. Hilbert hatte in den 1920er Jahren die schlichte Aussagenlogik durch einen „Funktionenkalkül“ dahingehend erweitert (Hilbert/Ackermann, Grundzüge der theoretischen Logik, Kapitel 3), dass sie neben den logischen Grundverknüpfungen, den Variablen für Aussagen und Gegenständen auch „Funktionenvariablen“ enthält. Mit dieser Formalisierung zur „Neubegründung der Mathematik“ sollte „jede mathematische Aussage zu einer konkret aufweisbaren und streng ableitbaren Formel“ werden (Hilbert, Grundlagen der Mathematik, S. 3). Drei hauptsächliche meta-mathematische Probleme ließen sich dadurch formulieren, womit Hilbert nach der „Widerspruchsfreiheit“ und „Vollständigkeit“ solcher „Axiomensysteme“ fragen konnte. Das dritte, das „Entscheidungsproblem im Funktionenkalkül“ (Hilbert/Ackermann, Grundzüge der theoretischen Logik, Kapitel 3, § 11) war von „grundsätzlicher Wichtigkeit“, da es die vollständige „logische Entwickelbarkeit“ der „Formeln“ aus „endlich vielen Axiomen“ garantieren sollte. Dieses Problem in Hilberts Spezifikation wäre gelöst, wenn ein Verfahren gefunden würde, das „bei einem vorgelegten logischen Ausdruck durch endlich viele Operationen die Entscheidung über die Allgemeingültigkeit bzw. Erfüllbarkeit erlaubt“. D.h., dass durch einen Formalismus abgeleitet werden kann, ob eine beliebig vorgelegte Formel eine „richtige Behauptung darstellt oder nicht“. Hilbert ging es in seiner „Beweistheorie“ darum, „das inhaltliche Schließen durch ein äußeres Handeln nach Regeln“ zu ersetzten (Hilbert, Grundlagen der Mathematik, S. 4). Acht Jahre blieb das Problem ungelöst, bis es von Turing mit seiner UTM und schon kurz vor ihm von Alonzo Church (1903–1995) mit seinem Lambda-Kalkül (1935/36) negativ entschieden wurde. Turing hat aufgezeigt, daß es kein allgemeines Verfahren gibt, um zu entscheiden, ob eine gegebene Formel 𝔄 des Funktionenkalküls K beweisbar ist, d.h., daß es keine Maschine geben kann, die, wird sie mit irgendeinem 𝔄 dieser Formeln gespeist, irgendwann sagen wird, ob 𝔄 beweisbar ist. Bereits 1931 konnte Kurt Gödel (1906–1978) mit seinem „Unvollständigkeitssatz“ nachweisen, dass Hilberts Funktionenkalkül und jedes andere widerspruchsfreie formale System, jede Logik, die mächtig genug ist, um zahlentheoretische (arithmetische) Aussagen darzustellen bzw. zu errechnen, „unvollständig“ ist (vgl. Wiener/Bonik/Hödicke, Einführung Turing-Maschinen, Kapitel 18). In diese Kategorie gehörte auch das bis dahin umfangreichste formallogische System, die Principia Mathematica von Bertrand Russell (1872–1970) und Alfred North Whitehead (1861–1947). Obwohl Hilbert, Gödel und Turing große „Zahlenklassen“ angeben konnten, die widerspruchsfrei, vollständig und auch entscheidbar waren (durch TMn berechenbar), durfte man nun nicht mehr davon ausgehen, dass eine formalistisch abgeschossene „Beweistheorie“ aus finiten Axiomen entwickelt werden konnte, die universalen Ansprüchen genügt. Und dennoch hatte Turing mit seiner UTM einen universellen Beschreibungsrahmen vorgelegt, mit dem jedes mechanische Verfahren operativ durchgeführt bzw. „simuliert“ werden konnte. Das Definieren von berechenbaren Zahlenklassen, das Finden von Beweisen für äquivalente Definitionen und die Intuition des Mathematikers waren für Turing die drei Grundlagen, um den „Umfang der berechenbaren Zahlen“ zu ermitteln. Ungewöhnlich war allerdings, wie Turing die intuitive Arbeit eines menschlichen Rechners, der mit Symbolen auf Papier (Bandfeldern) interagiert, selbst als ein physikalisches System interpretierte. Die einfachen Operationen eines Rechnenden auf einem linearen Band umfassen nur vier Aktionen: (a) Verändern des Symbols auf einem der wahrgenommenen Bandfelder; (b) verändern des Wahrnehmungsfokus auf ein benachbartes Bandfeld und zwei mögliche Veränderungen des Zustandes im Denken („state of mind“): (A) eine mögliche Veränderung von (a) zusammen mit einer möglichen Änderung des Zustandes im Denken; (B) eine mögliche Veränderung von (b) zusammen mit einer möglichen Änderung des Zustandes im Denken. Turing konstatiert, dass ein „Mann“, der gerade eine reelle Zahl berechnet, mit seinen „rechnenden Maschinen“ verglichen werden kann. Sein Gedankenspiel war: Wenn ein Rechnender auf einem Band mit Symbolen arbeitet, ist es nicht notwendig von seinem physikalischen Gedanken-Zustand („state of mind“) auszugehen. Es kann ein eindeutigeres physikalisches Gegenstück angegeben werden. Da der Rechnende seine Arbeit jederzeit unterbrechen und zu einem späteren Zeitpunkt fortsetzen kann, kann er einen Zettel mit Anweisungen (in irgendeiner standardisierten Form) festhalten, um an der entsprechenden Stelle später fortzufahren. Diesen Zettel mit Anweisungen können wir als Zustandsformel („state formula“) und als Gegenstück zum „state of mind“ interpretieren. Unterbricht der Rechnende nach jeder Operation seine Aktion und hält die Übergänge in einer Zustandsformel fest, so können wir aus diesen Zustandsformeln eine Maschine konstruieren (TM-Tabellen), die die gewünschte Zahl berechnet. Turings ingeniöse Idee war, dass konstruierte – wie auch immer im Denken hervorgebrachte – Verfahren, beispielsweise zur Berechnung reeller Zahlen, in seine elementar-operativen Maschinen transformierbar (formalisierbar) sind. Der Gedanke war neu und lenkte den Aspekt der mathematischen „Beweistheorie“ auf die generelleren Fragen nach der Art der Interaktion physikalischer Symbol-Systeme. Zusammen mit der auch von Church zum Ausdruck gebrachten „effektiven Rechenbarkeit“ („effective calculability“) bildete dieser Aspekt die Grundlage für die Church-Turing-These: Jedes effektive Verfahren kann als Tabelle einer TM beschrieben werden (vgl. Wiener/Bonik/Hödicke, Einführung Turing-Maschinen, Kapitel 11). Wiener fügte noch hinzu, „aber nur was klar verstanden ist, kann formalisiert werden (oder ist es eben schon, je nach Redeweise)“ (1990: 109). Turing hatte im Anhang seiner Arbeit einen Beweis der Äquivalenz zwischen seiner „Berechenbarkeit“ (durch TMn) und Churchs „effektiver Rechenbarkeit“ im Lambda-Kalkül geliefert. Und es fanden sich weitere, unabhängig davon entwickelte äquivalente Verfahren, z.B. die Normal-Systeme (Emil L. Post, 1897–1954) und die Normalalgorithmen (A. A. Markow, 1903–1979), was die Hypothese bekräftigten konnte, dass kein effektives Verfahren, kein algorithmischer Prozess oder arithmetischer Formalismus denkbar ist, der in Bezug auf die „Berechenbarkeit“ im Universum der reellen Zahlen mächtiger wäre als die Turing-Maschine. Aber die nach Turings Forderung „einfachen Operationen“, die so elementar sein müssen, „dass es schwer fallen sollte, sie noch weiter zu zerlegen“, durften, trotz der getroffenen Einschränkungen in ihren Freiheitsgraden, nicht den universellen Charakter und die Mächtigkeit in ihrer Berechenbarkeit verlieren. Denn die Turing-Maschinen (TMn) operieren, in Anlehnung an die beschriebenen Aktionen des Rechnenden, in diskreten Schritten. Jede zu betrachtende spezielle Maschine wird von einem eindimensionalen Band („tape“) versorgt, das durch sie hindurchläuft und in einzelne Felder („squares“) aufgeteilt ist, von denen jedes ein Zeichen („symbol“) tragen kann. An dieser Schnittstelle findet die Interaktion mit der Umgebung statt. Und da zu jedem gegebenen Zeitpunkt nur ein einzelnes Feld „abgetastet“ werden kann und nur ein Zeichen „gescannt“ werden kann – wenn sich auf dem Feld ein Zeichen befindet – so arbeitet die Maschine in ihrer Abfolge auch sequenziell. Alle Zustände („configurations“) der Maschine – es sind nur endlich viele zugelassen – und das durch sie eindeutig bestimmte Verhalten („behaviour“), aufgrund dessen ihre Arbeitsweise auch als deterministisch bezeichnet wird, können umfassend in einer TM-Tabelle („table“) festgehalten werden. In jeder Zeile der TM-Tabelle steht in geordneter Abfolge an erster Stelle die Zustandsnummer, gefolgt von dem möglichen Zeichen, das auf dem Band gelesen werden kann. Dieses Argumenten-Paar determiniert – wenn das entsprechende Zeichen gescannt wurde – das weitere Verhalten, die drei möglichen Operationen der Maschine. So steht an dritter Stelle das Zeichen, das – nach dem eventuellen Löschen des vorgefundenen Zeichens – auf das Band zurückgeschrieben werden soll, gefolgt von der eventuellen Bewegungsanweisung für die Maschine, die um ein Bandfeld nach rechts („R“) oder links („L“) gehen kann. An fünfter und letzter Stelle in jeder Zeile steht die Nummer des Folgezustandes, d.h. die Zeilennummer der Tabelle, in die nach Ausführung der Operationen gesprungen werden soll. Steht dort z.B. die gleiche Nummer wie an der ersten Stelle der Zeile, so verbleibt die Maschine im nämlichen Zustand bis sie das nächste Zeichen scannt und mit dem aktuellen Zustand kombiniert. Steht an letzter Stelle als Folgezustand eine Null, so bleibt die Maschine in einem „Selbst-Stopp“ auf dem Band stehen. Die größere Mächtigkeit der TMn gegenüber finiten Maschinen ergibt sich aus dem Nach-rechts- und Nach-links-Gehen. Mithilfe dieser Bewegungen kann die TM Zeichen lesen und weiterverwerten, die sie selbst auf das Band geschrieben hat (vgl. Wiener/Bonik/Hödicke, Einführung Turing-Maschinen, Kapitel 1 und 2).
Zur Universellen Turing-Maschine (UTM): Ist erst einmal eine Konvention zur Beschreibung des Verhaltens einer TM in den TM-Tabellen festgelegt, so lassen sich die einzelnen Operationen der TM, Zug um Zug auf einem Band (einer „Zeichenkette“, ZK), den gesamten „Lauf“ über bis zu ihrem eventuellen Selbst-Stopp mit einfachsten Mitteln (Bleistift und Papier) nachvollziehen. Und da dieses „Imitieren“ eines Laufs für jede beliebige TM (aus der potenziell unendlichen Menge der TMn) auf jeder beliebigen ZK (aus der potenziell unendlichen Menge der ZKn) ein effektives Verfahren ist, so lässt es sich auch als UTM formalisieren. „Allgemeine Gültigkeit der Church-Turing-These vorausgesetzt, existiert also eine TM, die dieses Verfahren verkörpert“ (Wiener/Bonik/Hödicke, Einführung Turing-Maschinen, Kapitel 12). Turing beschreibt nun in seinem Aufsatz eine spezielle TM, die genau dieses Verfahren der UTM verkörpert. Es ist nicht schwer, sich eine praktische Umsetzung dieser UTM vorzustellen: Schreibe eine beliebige TM-Tabelle Zeile für Zeile nacheinander auf das lineare Band, damit die Zeichen der TM-Tabelle von einer UTM gelesen und verarbeitet werden können. Schreibe daneben, auf das gleiche Band, vielleicht getrennt durch ein Zeichen als Marker, die Zeichenkette, auf der die nun linear angeordnete TM-Tabelle rechnen soll. Und zuletzt „programmiere“ in einer weiteren TM-Tabelle die Zustände und Operationen, die notwendig sind, um die auf dem linearen Band befindliche TM-Tabelle auf die neben ihr auf dem Band befindliche ZK anzuwenden. Man kann sich die Programmierung der UTM auch in Turings Gedankenspiel vorstellen. D.h., da du bereits weißt, wie du die TM-Tabelle – nun auf dem Band linear angeordnet – auf die danebenstehende ZK anzuwenden hast, so halte bei jeder deiner Operationen inne und notiere deine Schritte verallgemeinernd in einer TM-Tabelle, das Resultat ist eine UTM. Der große Vorteil der UTM als Werkzeug zur Untersuchung von Gegenstandsbereichen, beispielsweise in der Zahlentheorie, ist nun, dass eine bestimmte TM oder ganze Klassen bzw. Mengen von TMn, die auf Mengen von ZKn arbeiten, thematisiert werden können. In diesem Zusammenhang wird auch das bekannte „Halteproblem“ für TMn sehr wichtig, also die Frage, ob eine vorgelegte TM auf einer bestimmten ZK jemals halten wird (vgl. Wiener/Bonik/Hödicke, Einführung Turing-Maschinen, Kapitel 14 und 15). Die Feststellung, dass es rekursiv (durch eine TM) aufzählbare Mengen gibt, deren Komplement nicht rekursiv aufzählbar ist – z.B. die Menge der haltenden TMn auf der Menge der ZKn – führt direkt auf den Weg zu Gödels „Unvollständigkeitssatz“ (vgl. ebd., Kapitel 17 und 18). Geht man letztlich von Wieners Bemerkung zur Church-Turing-These aus, so ist nicht nur ein klares Verständnis in einer TM-Tabelle formalisierbar, sondern auch jede klare Auffassung oder jedes effektive Verstehen bereits als Strukturierung seines Gegenstandsbereichs im Sinne einer Turing-Maschine verkörpert. So gelangt man zu Wieners Strukturdefinition: Eine Struktur einer Zeichenkette ist eine Turing-Maschine, welche diese Zeichenkette generiert oder akzeptiert (vgl. Wiener, „Form and Contenc“, S. 635 f.). Ob der „Apparat“, der dieses Verständnis hervorgebracht hat, allerdings selbst wiederum ein effektives Verfahren ist, d.h. in einer TM-Tabelle formalisiert werden kann, ist bis heute nicht geklärt. Klar scheint allerdings: Ist er es nicht, werden wir ihn, aus den dargelegten Gründen, nie klar verstehen. – Michael Schwarz
Literatur / Quellen:
- Gödel, Kurt: „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“. In: Monatshefte für Mathematik und Physik 38 (1931), H. 1, S. 173–198.
- Hilbert, David/Ackermann, Wilhelm: Grundzüge der theoretischen Logik, Berlin: Springer 1928.
- Hilbert, David: Die Grundlagen der Mathematik, Wiesbaden: Springer 1928.
- Turing, Alan M.: „On Computable Numbers, with an Application to the Entscheidungsproblem“. In: Proceedings of the London Mathematical Society 42 (1937), H. 1, S. 230–265.
- Wiener, Oswald: „Form and Content in Thinking Turing Machines“. In: The Universal Turing Machine, hg. von Rolf Herken, Oxford: Oxford University Press 1988, S. 631–657.
- Wiener, Oswald: Probleme der Künstlichen Intelligenz, Berlin: Merve 1990.
- Wiener, Oswald/Bonik, Manuel/Hödicke, Robert: Eine elementare Einführung in die Theorie der Turing-Maschinen, Wien: Springer 1998.
