Universelle Turingmaschine

Eine universelle Turingmaschine (UTM) ist in der Informatik eine Turingmaschine, die eine beliebige Turingmaschine auf beliebiger Eingabe simuliert. Die universelle Maschine erreicht dies im Wesentlichen dadurch, dass sie sowohl die Beschreibung der zu simulierenden Maschine als auch die Eingabe an diese Maschine von ihrem eigenen Band liest. Alan Turing stellte die Idee einer solchen Maschine in den Jahren 1936 bis 1937 vor. Dieses Prinzip gilt als Ursprung der Idee eines speicherprogrammierten Computers, den John von Neumann 1946 für das "Electronic Computing Instrument" verwendete, das heute von Neumanns Namen trägt: die von-Neumann-Architektur.

In Bezug auf die Rechenkomplexität muss eine universelle Turingmaschine mit mehreren Bändern nur um einen logarithmischen Faktor langsamer sein als die Maschinen, die sie simuliert.

Einführung

Jede Turingmaschine berechnet aus den Eingabestrings über ihr Alphabet eine bestimmte feste, partiell berechenbare Funktion. In diesem Sinne verhält sie sich wie ein Computer mit einem festen Programm. Wir können jedoch die Aktionstabelle einer beliebigen Turingmaschine in einer Zeichenkette kodieren. So können wir eine Turingmaschine konstruieren, die auf ihrem Band eine Zeichenkette erwartet, die eine Aktionstabelle beschreibt, gefolgt von einer Zeichenkette, die das Eingabeband beschreibt, und die das Band berechnet, das die kodierte Turingmaschine berechnet hätte. Turing hat eine solche Konstruktion in seinem Aufsatz aus dem Jahr 1936 sehr detailliert beschrieben:

"Es ist möglich, eine einzige Maschine zu erfinden, mit der man jede beliebige berechenbare Folge berechnen kann. Wenn diese Maschine U mit einem Band versorgt wird, auf dessen Anfang die S.D ["Standardbeschreibung" einer Aktionstabelle] irgendeiner Rechenmaschine M geschrieben steht, dann wird U die gleiche Sequenz berechnen wie M."

Computer mit gespeichertem Programm

Davis argumentiert überzeugend, dass Turings Konzeption dessen, was heute als "speicherprogrammierter Computer" bekannt ist, nämlich die "Aktionstabelle" – die Anweisungen für die Maschine – im selben "Speicher" wie die Eingabedaten zu platzieren, John von Neumanns Konzeption des ersten amerikanischen Computers mit diskreten Symbolen (im Gegensatz zu analogen) – dem EDVAC – stark beeinflusst hat. Davis zitiert das Time-Magazine dahingehend, dass "jeder, der auf einer Tastatur tippt ... an einer Inkarnation einer Turingmaschine arbeitet", und dass "John von Neumann auf der Arbeit von Alan Turing [aufbaute]" (Davis 2000:193 zitiert das Time-Magazine vom 29. März 1999).

Davis argumentiert, dass Turings Computer Automatic Computing Engine (ACE) die Konzepte der Mikroprogrammierung (Microcode) und der RISC-Prozessoren "vorweggenommen" hat (Davis 2000:188). Knuth zitiert Turings Arbeit am ACE-Computer als Entwurf von "Hardware zur Erleichterung der Verknüpfung von Subroutinen" (Knuth 1973:225); Davis verweist auf diese Arbeit auch als Turings Verwendung eines Hardware-"Stacks" (Davis 2000:237 Fußnote 18).

Während die Turingmaschine die Konstruktion von Computern förderte, förderte die UTM die Entwicklung der jungen Computerwissenschaften. Ein früher, wenn nicht der allererste Assembler wurde "von einem jungen Heißsporn-Programmierer" für den EDVAC vorgeschlagen (Davis 2000:192). Von Neumanns "erstes ernsthaftes Programm ... [war] einfach, um Daten effizient zu sortieren" (Davis 2000:184). Knuth stellt fest, dass die im Programm selbst und nicht in speziellen Registern eingebettete Subroutinenrückgabe auf von Neumann und Goldstine zurückzuführen ist. Knuth stellt außerdem fest, dass

"Die erste interpretierende Routine kann als die "Universal Turing Machine" bezeichnet werden ... Interpretierende Routinen im herkömmlichen Sinne wurden von John Mauchly in seinen Vorlesungen an der Moore School im Jahr 1946 erwähnt ... Turing nahm auch an dieser Entwicklung teil; interpretierende Systeme für den Pilot ACE Computer wurden unter seiner Leitung geschrieben" (Knuth 1973:226).

Davis erwähnt kurz Betriebssysteme und Compiler als Ergebnisse der Vorstellung von "program-as-data" (Davis 2000:185).

Einige könnten jedoch Probleme mit dieser Einschätzung aufwerfen. Zu dieser Zeit (Mitte der 1940er bis Mitte der 1950er Jahre) beschäftigte sich ein relativ kleiner Kader von Forschern intensiv mit der Architektur der neuen "digitalen Computer". Hao Wang (1954), ein junger Forscher zu dieser Zeit, machte die folgende Beobachtung:

Turings Theorie der berechenbaren Funktionen hat die umfangreiche tatsächliche Konstruktion von Digitalcomputern zwar antizipiert, aber nicht wesentlich beeinflusst. Diese beiden Aspekte von Theorie und Praxis haben sich fast völlig unabhängig voneinander entwickelt. Der Hauptgrund dafür ist sicherlich, dass Logiker an ganz anderen Fragen interessiert sind als die, mit denen sich die angewandten Mathematiker und Elektroingenieure hauptsächlich beschäftigen. Es kann jedoch nicht ausbleiben, dass es ziemlich merkwürdig ist, dass oft dieselben Konzepte in den beiden Entwicklungen mit sehr unterschiedlichen Begriffen ausgedrückt werden." (Wang 1954, 1957:63)

Wang hoffte, dass seine Arbeit "die beiden Ansätze verbinden würde". In der Tat, Minsky bestätigt dies: "dass die erste Formulierung der Turingmaschinentheorie in computerähnlichen Modellen in Wang (1957) erscheint" (Minsky 1967:200). Minsky fährt fort, die Turing-Äquivalenz einer Gegenmaschine zu demonstrieren.

In Bezug auf die Reduktion von Computern auf einfache Turing-äquivalente Modelle (und umgekehrt) ist Minskys Bezeichnung von Wang als "erste Formulierung" umstritten. Während sowohl Minskys Aufsatz von 1961 als auch Wangs Aufsatz von 1957 von Shepherdson und Sturgis (1963) zitiert werden, zitieren sie auch die Arbeiten der europäischen Mathematiker Kaphenst (1959), Ershov (1959) und Péter (1958) und fassen sie in einigen Details zusammen. Die Namen der Mathematiker Hermes (1954, 1955, 1961) und Kaphenst (1959) erscheinen sowohl in den Bibliographien von Sheperdson-Sturgis (1963) als auch von Elgot-Robinson (1961). Zwei weitere Namen von Bedeutung sind die kanadischen Forscher Melzak (1961) und Lambek (1961). Für vieles mehr siehe Turingmaschinen-Äquivalente; Referenzen finden sich unter Registermaschine.

Mathematische Theorie

Mit dieser Kodierung von Aktionstabellen als Zeichenketten wird es für Turingmaschinen prinzipiell möglich, Fragen über das Verhalten anderer Turingmaschinen zu beantworten. Die meisten dieser Fragen sind jedoch unentscheidbar, das heißt die betreffende Funktion kann nicht mechanisch berechnet werden. Zum Beispiel wurde das Problem, ob eine beliebige Turingmaschine bei einer bestimmten Eingabe oder bei allen Eingaben anhält, bekannt als das Halteproblem, in Turings Originalarbeit als allgemein unentscheidbar gezeigt. Der Satz von Rice zeigt, dass jede nicht-triviale Frage über die Ausgabe einer Turingmaschine unentscheidbar ist.

Eine universelle Turingmaschine kann jede rekursive Funktion berechnen, jede rekursive Sprache entscheiden und jede rekursiv aufzählbare Sprache akzeptieren. Nach der Church-Turing-These sind die von einer universellen Turingmaschine lösbaren Probleme genau die Probleme, die von einem Algorithmus oder einer effektiven Berechnungsmethode lösbar sind, für jede vernünftige Definition dieser Begriffe. Aus diesen Gründen dient eine universelle Turingmaschine als Standard, mit dem man Rechensysteme vergleichen kann, und ein System, das eine universelle Turingmaschine simulieren kann, wird Turing-vollständig genannt.

Eine abstrakte Version der universellen Turingmaschine ist die universelle Funktion, eine berechenbare Funktion, die zur Berechnung jeder anderen berechenbaren Funktion verwendet werden kann. Das UTM-Theorem beweist die Existenz einer solchen Funktion.

Effizienz

Ohne Verlust der Allgemeingültigkeit kann angenommen werden, dass die Eingabe einer Turingmaschine im Alphabet {0, 1} liegt; jedes andere endliche Alphabet kann über {0, 1} kodiert werden. Das Verhalten einer Turingmaschine M wird durch ihre Übergangsfunktion bestimmt. Diese Funktion kann ebenfalls einfach als String über dem Alphabet {0, 1} kodiert werden. Die Größe des Alphabets von M, die Anzahl seiner Bänder und die Größe des Zustandsraums können aus der Tabelle der Übergangsfunktion abgeleitet werden. Die unterschiedenen Zustände und Symbole können durch ihre Position identifiziert werden, zum Beispiel können die ersten beiden Zustände per Konvention die Start- und Stopp-Zustände sein. Folglich kann jede Turingmaschine als String über dem Alphabet {0, 1} kodiert werden. Zusätzlich stellen wir fest, dass jede ungültige Kodierung auf eine triviale Turingmaschine abbildet, die sofort anhält, und dass jede Turingmaschine eine unendliche Anzahl von Kodierungen haben kann, indem die Kodierung mit einer beliebigen Anzahl von (sagen wir) 1en am Ende aufgefüllt wird, so wie Kommentare in einer Programmiersprache funktionieren. Es sollte keine Überraschung sein, dass wir diese Kodierung angesichts der Existenz einer Gödelzahl und der rechnerischen Äquivalenz zwischen Turingmaschinen und μ-rekursiven Funktionen erreichen können. In ähnlicher Weise assoziiert unsere Konstruktion zu jeder binären Zeichenkette α eine Turingmaschine Mα.

Ausgehend von der obigen Kodierung zeigten F. C. Hennie und R. E. Stearns 1966, dass bei einer Turingmaschine Mα, die auf der Eingabe x innerhalb von N Schritten anhält, eine universelle Turingmaschine mit mehreren Bändern existiert, die auf den Eingaben α, x (die auf verschiedenen Bändern gegeben sind) in CN log N anhält, wobei C eine maschinenspezifische Konstante ist, die nicht von der Länge der Eingabe x abhängt, wohl aber von der Alphabetgröße von M, der Anzahl der Bänder und der Anzahl der Zustände. Effektiv handelt es sich hierbei um eine ${\displaystyle {\mathcal {O}}\left(N\log {N}\right)}$ Simulation, die Donald Knuths O-Notation verwendet. Das entsprechende Ergebnis für Raumkomplexität anstelle von Zeitkomplexität ist, dass wir auf eine Weise simulieren können, die in jedem Stadium der Berechnung höchstens CN-Zellen verwendet, eine ${\displaystyle {\mathcal {O}}(N)}$ Simulation.

Kleinste Maschinen

Als Alan Turing auf die Idee einer Universalmaschine kam, hatte er das einfachste Rechenmodell im Sinn, das leistungsfähig genug ist, um alle möglichen Funktionen zu berechnen, die berechnet werden können. Claude Shannon stellte 1956 erstmals explizit die Frage nach der kleinstmöglichen universellen Turingmaschine. Er zeigte, dass zwei Symbole ausreichend sind, solange genügend Zustände verwendet werden (oder umgekehrt), und dass es immer möglich ist, Zustände gegen Symbole auszutauschen. Er zeigte auch, dass es keine universelle Turingmaschine mit nur einem Zustand geben kann.

Marvin Minsky entdeckte 1962 eine universelle Turingmaschine mit sieben Zuständen und vier Symbolen, die Zwei-Tag-Systeme verwendet. Weitere kleine universelle Turingmaschinen wurden seitdem von Yurii Rogozhin und anderen gefunden, indem sie diesen Ansatz der Tag-System-Simulation erweiterten. Wenn wir mit (m, n) die Klasse der UTMs mit m Zuständen und n Symbolen bezeichnen, sind die folgenden Tupel gefunden worden: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), und (2, 18). Rogozhins (4, 6)-Maschine verwendet nur 22 Anweisungen, und es ist keine Standard-UTM mit geringerer Beschreibungskomplexität bekannt.

Eine Verallgemeinerung des Standardmodells der Turingmaschine lässt jedoch noch kleinere UTMs zu. Eine solche Verallgemeinerung besteht darin, ein unendlich wiederholtes Wort auf einer oder beiden Seiten der Turingmaschinen-Eingabe zuzulassen, wodurch die Definition der Universalität erweitert wird und als "halbschwache" beziehungsweise "schwache" Universalität bekannt ist. Kleine schwach universelle Turingmaschinen, die den zellulären Automaten der Regel 110 simulieren, wurden für die (6, 2), (3, 3) und (2, 4) Zustand-Symbol-Paare gegeben. Der Beweis der Universalität für Wolframs 2-Zustands-3-Symbol-Turing-Automat erweitert den Begriff der schwachen Universalität weiter, indem er bestimmte nicht-periodische Anfangskonfigurationen zulässt. Andere Varianten des Standard-Turingmaschinenmodells, die kleine UTMs ergeben, sind Maschinen mit mehreren Bändern oder Bändern mehrerer Dimensionen und Maschinen, die mit einem endlichen Automaten gekoppelt sind.

Maschinen ohne interne Zustände

Wenn Sie mehrere Köpfe an der Turingmaschine zulassen, dann können Sie eine Turingmaschine ohne interne Zustände haben. Die "Zustände" sind als Teil des Bandes kodiert. Betrachten Sie zum Beispiel ein Band mit sechs Farben: 0, 1, 2, 0A, 1A, 2A. Betrachten Sie ein Band wie 0,0,1,2,2A,0,2,1, auf dem sich eine dreiköpfige Turingmaschine über dem Tripel (2,2A,0) befindet. Die Regeln konvertieren dann jedes Tripel in ein anderes Tripel und verschieben die drei Köpfe nach links oder rechts. Zum Beispiel könnten die Regeln (2,2A,0) in (2,1,0) umwandeln und den Kopf nach links verschieben. In diesem Beispiel verhält sich die Maschine also wie eine dreiköpfige Turingmaschine mit den internen Zuständen A und B (dargestellt durch keinen Buchstaben). Der Fall für eine zweiköpfige Turingmaschine ist sehr ähnlich. So kann eine zweiköpfige Turingmaschine universell mit sechs Farben sein. Es ist nicht bekannt, was die kleinste Anzahl von Farben ist, die für eine mehrköpfige Turingmaschine benötigt wird, oder ob eine zweifarbige Universal-Turingmaschine mit mehreren Köpfen möglich ist. Es bedeutet auch, dass Umschreibregeln Turing-vollständig sind, da die Tripelregeln äquivalent zu Umschreibregeln sind. Erweitert man das Band auf zwei Dimensionen mit einem Kopf, der einen Buchstaben und seine acht Nachbarn abtastet, werden nur zwei Farben benötigt, da zum Beispiel eine Farbe in einem vertikalen Tripelmuster wie 110 kodiert werden kann.

Beispiel für Universal-Maschinen-Codierung

Für diejenigen, die sich der Herausforderung stellen wollen, eine UTM genau nach Turings Vorgaben zu entwerfen, sei auf den Artikel von Davies in Copeland (2004:103ff) verwiesen. Davies korrigiert die Fehler im Original und zeigt, wie ein Probelauf aussehen würde. Er behauptet, eine (etwas vereinfachte) Simulation erfolgreich durchgeführt zu haben.

Das folgende Beispiel ist aus Turing (1936) entnommen. Mehr zu diesem Beispiel finden Sie auf der Seite Turingmaschinen-Beispiele.

Turing verwendete sieben Symbole { A, C, D, R, L, N, ; }, um jedes 5-Tupel zu kodieren; wie im Artikel Turingmaschine beschrieben, sind seine 5-Tupel nur von den Typen N1, N2 und N3. Die Nummer jeder "m-Konfiguration" (Anweisung, Zustand) wird durch "D", gefolgt von einer unären Folge von A's, dargestellt, zum Beispiel "q3" = DAAA. In ähnlicher Weise kodiert er die Symbole blank als "D", das Symbol "0" als "DC", das Symbol "1" als DCC usw. Die Symbole "R", "L" und "N" bleiben wie sie sind.

Nach der Kodierung wird dann jedes 5-Tupel in der Reihenfolge wie in der folgenden Tabelle gezeigt zu einem String "zusammengesetzt":

Schließlich werden die Codes für alle vier 5-Tupel zu einem Code aneinandergereiht, der mit ";" beginnt und durch ";" getrennt ist, zum Beispiel:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAA;DAAAADDRDA

Diesen Code platzierte er auf abwechselnden Quadraten – den "F-Quadraten" – und ließ die "E-Quadrate" (die löschbaren) leer. Die endgültige Montage des Codes auf dem Band für die U-Maschine besteht darin, dass zwei Sonderzeichen ("e") hintereinander platziert werden, dann der Code auf abwechselnden Quadraten und zuletzt das Doppelpunkt-Symbol "::" (Leerstellen werden hier zur Verdeutlichung mit "." dargestellt):

ee.;.D.A.D.D.C.R.D.A.A.;.D.A.A.D.R.D.A.A.A.;.D.A.A.A.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.R.D.A.::......

Die Aktionstabelle (Zustandsübergangstabelle) der U-Maschine ist für die Dekodierung der Symbole zuständig. Turings Aktionstabelle behält ihren Platz mit den Markern "u", "v", "x", "y", "z" im Auge, indem sie diese in "E-Quadraten" rechts vom "markierten Symbol" platziert – zum Beispiel zur Markierung der aktuellen Anweisung wird z rechts von ";" platziert x behält den Platz in Bezug auf die aktuelle "m-Konfiguration" DAA. Die Aktionstabelle der U-Maschine pendelt diese Symbole umher (löscht sie und platziert sie an anderen Stellen), während die Berechnung fortschreitet:

ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.AxD.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.D.R.D.A.::......

Turings Aktionstabelle für seine U-Maschine ist sehr aufwendig.

Eine Reihe anderer Kommentatoren (vor allem Penrose 1989) geben Beispiele für die Kodierung von Anweisungen für die Universalmaschine. Wie Penrose verwenden die meisten Kommentatoren nur binäre Symbole, das heißt nur Symbole { 0, 1 }, oder { blank, mark | }. Penrose geht weiter und schreibt seinen gesamten U-Maschinen-Code aus (Penrose 1989:71-73). Er behauptet, dass es sich wirklich um einen U-Maschinen-Code handelt, eine enorme Zahl, die sich über fast 2 volle Seiten mit 1en und 0en erstreckt. Für Leser, die an einfacheren Kodierungen für die Post-Turing-Maschine interessiert sind, mag die Diskussion von Davis in Steen (Steen 1980:251ff) nützlich sein.

Asperti und Ricciotti beschrieben eine UTM mit mehreren Bändern, die durch das Zusammensetzen von Elementarmaschinen mit sehr einfacher Semantik definiert wurde, anstatt explizit ihre vollständige Aktionstabelle anzugeben. Dieser Ansatz war ausreichend modular, um die Korrektheit der Maschine mit dem Matita-Beweisassistenten formal zu beweisen.

Programmierung von Turingmaschinen

Verschiedene höhere Sprachen sind so konzipiert, dass sie in eine Turingmaschine kompiliert werden können. Beispiele hierfür sind Laconic und Turing Machine Descriptor.

Literatur

• A. M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. s2-42, Nr. 1, 1937, ISSN 0024-6115, S. 230–265. doi:10.1112/plms/s2-42.1.230.
• B. Jack Copeland: The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life Plus the Secrets of Eni: Seminal ... Artificial Life Plus the Secrets of Enigma. Hrsg.: Oxford University Press. 2004, ISBN 978-0-19-825079-1, S. 113 ff. 
• F. C. Hennie, R. E. Stearns: Two-Tape Simulation of Multitape Turing Machines. In: Journal of the ACM. 13, Nr. 4, 1966, ISSN 0004-5411, S. 533–546. doi:10.1145/321356.321362.
• Arora, Sanjeev; Barak, Boaz: Complexity Theory: A Modern Approach. Hrsg.: Cambridge University Press. 2009, ISBN 978-0-521-42426-4, S. 19–21 und 29–32. 
• Andrea Asperti, Wilmer Ricciotti: A formalization of multi-tape Turing machines. In: Theoretical Computer Science. 603, 2015, ISSN 0304-3975, S. 23–42. doi:10.1016/j.tcs.2015.07.013.
• Manfred Kudlek, Yurii Rogozhin: A Universal Turing Machine with 3 States and 9 Symbols. In: Springer. 2295, 2002, ISSN 0302-9743, S. 311–318. doi:10.1007/3-540-46011-X_27.
• M. L. Minsky: Size and structure of universal Turing machines using tag systems. In: American Mathematical Society. 5, 1962, ISSN 2324-707X, S. 229–238. doi:10.1090/pspum/005/0142452.
• Turlough Neary, Damien Woods: Four Small Universal Turing Machines. In: Fundamenta Informaticae. 91, Nr. 1, 2009, ISSN 0169-2968, S. 123–144. doi:10.3233/FI-2009-0036.
• Yurii Rogozhin: Small universal Turing machines. In: Theoretical Computer Science. 168, Nr. 2, 1996, ISSN 0304-3975, S. 215–240. doi:10.1016/S0304-3975(96)00077-1.
• A. M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. s2-42, Nr. 1, 1937, ISSN 0024-6115, S. 230–265. doi:10.1112/plms/s2-42.1.230.
• A. M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. In: Proceedings of the London Mathematical Society. s2-43, Nr. 1, 1938, ISSN 0024-6115, S. 544–546. doi:10.1112/plms/s2-43.6.544.