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 500px|rechts|rahmenlos
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 macht 1954 als junger Forscher 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". Marvin Minsky bestätigte, "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 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 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.