Universelle Turingmaschine

Grundidee und Funktionsweise

Eine universelle Turingmaschine (UTM) ist eine Turingmaschine, die jede beliebige Turingmaschine auf jeder beliebigen Eingabe simulieren kann. Dazu liest sie von ihrem eigenen Band sowohl eine kodierte Beschreibung der zu simulierenden Maschine als auch deren Eingabe. Alan Turing stellte diese Idee 1936 bis 1937 vor.

Eine gewöhnliche Turingmaschine berechnet eine bestimmte feste, partiell berechenbare Funktion: Für manche Eingaben liefert sie ein Ergebnis, bei anderen hält sie möglicherweise nie an. Ihre Aktionstabelle legt dabei das Verhalten ähnlich wie ein festes Programm fest. Diese Tabelle lässt sich jedoch als Zeichenkette kodieren. Eine UTM erhält dann zunächst diese Maschinenbeschreibung und anschließend eine Beschreibung des Eingabebandes. Sie führt genau die Berechnung aus, welche die kodierte Maschine mit dieser Eingabe ausführen würde.

Der entscheidende Gedanke ist somit, Programm und Daten in derselben Form zu speichern und zu verarbeiten. Die UTM ist kein Modell für nur eine bestimmte Aufgabe, sondern eine einzige Maschine, die durch unterschiedliche kodierte Programme alle algorithmisch berechenbaren Aufgaben übernehmen kann.

Berechenbarkeit und Grenzen

Da Aktionstabellen als Zeichenketten dargestellt werden können, können Turingmaschinen auch Berechnungen über andere Turingmaschinen ausführen. Die meisten allgemeinen Fragen über deren Verhalten sind allerdings unentscheidbar: Es gibt keinen Algorithmus, der sie für jede mögliche Maschine und Eingabe korrekt beantwortet.

Das wichtigste Beispiel ist das Halteproblem. Es fragt, ob eine beliebige Turingmaschine bei einer bestimmten Eingabe beziehungsweise bei allen Eingaben anhält. Turing zeigte bereits in seiner Originalarbeit, dass dieses Problem im Allgemeinen unentscheidbar ist. Der Satz von Rice verallgemeinert diese Grenze: Jede nicht-triviale Frage über die von einer Turingmaschine berechnete Ausgabe ist unentscheidbar.

Eine UTM kann jede rekursive Funktion berechnen, jede rekursive Sprache entscheiden und jede rekursiv aufzählbare Sprache akzeptieren. Eine Sprache wird entschieden, wenn die Maschine für jede Eingabe anhält und korrekt über deren Zugehörigkeit entscheidet. Bei einer rekursiv aufzählbaren Sprache muss sie dagegen nur die zur Sprache gehörenden Eingaben akzeptieren; bei anderen Eingaben darf sie endlos weiterrechnen.

Nach der Church-Turing-These sind die durch eine UTM lösbaren Probleme genau diejenigen, die sich mit einem Algorithmus oder einer effektiven Berechnungsmethode lösen lassen, sofern diese Begriffe vernünftig definiert werden. Deshalb dient die UTM als Vergleichsmaßstab für Rechensysteme. Ein System heißt Turing-vollständig, wenn es eine universelle Turingmaschine simulieren kann. Die abstrakte Entsprechung der UTM ist die universelle Funktion: eine berechenbare Funktion, mit der jede andere berechenbare Funktion berechnet werden kann. Das UTM-Theorem beweist die Existenz einer solchen Funktion.

Bedeutung für gespeicherte Programme

Das Prinzip der UTM gilt als Ursprung der Idee des speicherprogrammierten Computers: Maschinenanweisungen und Eingabedaten liegen im selben Speicher. John von Neumann verwendete dieses Prinzip 1946 für das „Electronic Computing Instrument“; damit ist die heute so bezeichnete Von-Neumann-Architektur verbunden.

Martin Davis vertritt die Auffassung, Turings Konzeption habe von Neumanns Arbeit am EDVAC, einem frühen amerikanischen Digitalcomputer, stark beeinflusst. Davis zufolge nahm Turings Automatic Computing Engine (ACE) außerdem Mikroprogrammierung und RISC-Prozessoren vorweg. Donald Knuth beschreibt Turings ACE-Arbeit als einen Hardwareentwurf, der die Verknüpfung von Subroutinen erleichterte. Interpretierende Routinen können ebenfalls als praktische Entsprechung der universellen Maschine verstanden werden: Ein Programm liest und führt ein anderes Programm aus. Davis nennt auch Betriebssysteme und Compiler als Folgen der Vorstellung von „program-as-data“, also des Programms als Daten.

Wie unmittelbar Turings Theorie die tatsächliche Computerentwicklung beeinflusste, ist jedoch umstritten. Hao Wang schrieb 1954, Theorie und praktische Konstruktion digitaler Computer hätten sich fast völlig unabhängig entwickelt, weil Logiker andere Fragen verfolgten als angewandte Mathematiker und Elektroingenieure. Auch die Behauptung, Wang habe als Erster die Turingmaschinentheorie in computerähnlichen Modellen formuliert, ist umstritten; hierzu existierten weitere Arbeiten, unter anderem von Kaphenst, Ershov, Péter und Hermes.

Kodierung und Effizienz

Ohne Verlust der Allgemeinheit kann die Eingabe einer Turingmaschine über dem binären Alphabet {0, 1} dargestellt werden, weil sich jedes endliche Alphabet binär kodieren lässt. Auch die Übergangsfunktion, welche das Verhalten einer Maschine M festlegt, kann als binäre Zeichenkette gespeichert werden. Aus ihrer Tabelle lassen sich unter anderem Alphabetgröße, Bandanzahl und Zustandsraum ableiten. Zustände und Symbole können über ihre Position identifiziert werden; beispielsweise können die ersten beiden Zustände vereinbarungsgemäß Start- und Stoppzustand sein.

Damit lässt sich jeder binären Zeichenkette α eine Turingmaschine Mα zuordnen. Ungültige Kodierungen können auf eine triviale Maschine abgebildet werden, die sofort anhält. Umgekehrt darf eine Maschine unendlich viele Kodierungen besitzen, etwa indem man beliebig viele bedeutungslose 1en anhängt, vergleichbar mit Kommentaren in einer Programmiersprache.

F. C. Hennie und R. E. Stearns zeigten 1966: Hält Mα mit Eingabe x nach N Schritten, so gibt es eine universelle Mehrband-Turingmaschine, die die getrennt auf Bändern gegebenen Eingaben α und x in höchstens C·N·log N Schritten simuliert. C ist eine maschinenspezifische Konstante. Sie hängt nicht von der Länge von x ab, wohl aber von Alphabetgröße, Bandanzahl und Zustandsanzahl der simulierten Maschine. Die Zeitkomplexität beträgt damit O(N log N); die universelle Mehrbandmaschine ist nur um einen logarithmischen Faktor langsamer. Für die Raumkomplexität ist eine Simulation mit höchstens C·N Bandzellen, also O(N), möglich.

Kleine und zustandslose Universalmaschinen

Claude Shannon fragte 1956 ausdrücklich nach der kleinstmöglichen UTM. Er zeigte, dass zwei Symbole ausreichen, wenn genügend Zustände vorhanden sind, und umgekehrt Zustände gegen Symbole ausgetauscht werden können. Eine universelle Turingmaschine mit nur einem Zustand ist jedoch unmöglich.

Marvin Minsky fand 1962 mithilfe von Zwei-Tag-Systemen eine universelle Maschine mit sieben Zuständen und vier Symbolen. Spätere Konstruktionen von Yurii Rogozhin und anderen umfassen für m Zustände und n Symbole die Paare (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) und (2, 18). Rogozhins (4, 6)-Maschine benötigt 22 Anweisungen; eine Standard-UTM mit geringerer Beschreibungskomplexität ist nicht bekannt.

Verallgemeinerte Modelle erlauben kleinere Maschinen. Bei halbschwacher oder schwacher Universalität darf auf einer oder beiden Seiten der Eingabe ein unendlich wiederholtes Wort stehen. Für die Simulation des zellulären Automaten Regel 110 wurden schwach universelle Maschinen mit den Paaren (6, 2), (3, 3) und (2, 4) angegeben. Der Universalitätsbeweis für Wolframs 2-Zustands-3-Symbol-Automaten lässt sogar bestimmte nichtperiodische Anfangskonfigurationen zu.

Mit mehreren Schreib-Lese-Köpfen ist eine Maschine ohne interne Zustände möglich, weil die Zustandsinformation auf dem Band kodiert wird. Bei sechs Farben 0, 1, 2, 0A, 1A und 2A können drei Köpfe gemeinsam ein Tripel lesen, dieses nach einer Regel verändern und sich nach links oder rechts bewegen. Auch eine zweiköpfige Maschine kann mit sechs Farben universell sein. Unbekannt ist, wie wenige Farben Mehrkopfmaschinen mindestens benötigen und ob eine zweifarbige universelle Mehrkopf-Turingmaschine möglich ist. Da die Tripelregeln Umschreibregeln entsprechen, sind auch Umschreibregeln Turing-vollständig. Auf einem zweidimensionalen Band, bei dem ein Kopf ein Feld und seine acht Nachbarn abtastet, genügen zwei Farben.

Konkrete Maschinenkodierung und Programmierung

In Turings Beispiel wird jedes 5-Tupel einer Aktionstabelle mit den sieben Symbolen {A, C, D, R, L, N, ;} kodiert. Eine m-Konfiguration, also eine Anweisung beziehungsweise ein Zustand, erhält eine Nummer aus „D“ und einer unären Folge von A: q3 wird zu DAAA. Das leere Bandsymbol wird als D, 0 als DC und 1 als DCC dargestellt; R, L und N bleiben unverändert.

Ein 5-Tupel setzt nacheinander die Codes für aktuelle m-Konfiguration, gelesenes Bandsymbol, Druckoperation, Bandbewegung und folgende m-Konfiguration zusammen. Beispielsweise wird q1, blank, P0, R, q2 als DADDCRDAA kodiert. Die Codes aller Tupel werden durch Semikolons getrennt aneinandergereiht. Für vier Beispielanweisungen ergibt sich:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAA;DAAAADDRDA

Turing legte den Code auf abwechselnde „F-Quadrate“ des Bandes und ließ die löschbaren „E-Quadrate“ dazwischen frei. Marker wie u, v, x, y und z wurden auf den E-Quadraten verschoben, um während der Dekodierung die aktuelle Anweisung, Konfiguration und andere Positionen festzuhalten. Die vollständige Aktionstabelle dieser Universalmaschine ist sehr aufwendig. Davies korrigierte später Fehler in Turings Original und beschrieb einen Probelauf; andere Darstellungen verwenden einfachere binäre Kodierungen. Asperti und Ricciotti konstruierten eine Mehrband-UTM modular aus Elementarmaschinen mit einfacher Semantik und bewiesen ihre Korrektheit formal mit dem Matita-Beweisassistenten.

Turingmaschinen können außerdem über höhere Programmiersprachen programmiert werden, die anschließend in eine Turingmaschine übersetzt werden. Genannte Beispiele sind Laconic und Turing Machine Descriptor.