In der Informatik ist eine universale Maschine von Turing (UTM) eine Maschine von Turing, die eine willkürliche Maschine von Turing auf dem willkürlichen Eingang vortäuschen kann. Die universale Maschine erreicht im Wesentlichen das durch das Lesen von beiden die Beschreibung der Maschine, die sowie der Eingang davon von seinem eigenen Band vorzutäuschen ist. Alan Turing hat diese Maschine in 1936-1937 eingeführt. Wie man betrachtet, ist dieses Modell von einigen (zum Beispiel, Martin Davis (2000)) der Ursprung des speicherprogrammierten Computers — verwendet von John von Neumann (1946) für das "Elektronische Recheninstrument", das jetzt den Namen: von von Neumann die Architektur von von Neumann trägt. Es ist auch bekannt als universale Rechenmaschine, universale Maschine, Maschine U, U.

In Bezug auf die rechenbetonte Kompliziertheit ein Mehrband muss universale Maschine von Turing nur durch den logarithmischen Faktor im Vergleich zu den Maschinen langsamer sein, die es vortäuscht.

Einführung

Jede Maschine von Turing schätzt eine bestimmte feste teilweise berechenbare Funktion von den Eingangsschnuren über sein Alphabet. In diesem Sinn benimmt es sich wie ein Computer mit einem festen Programm. Jedoch können wir den Handlungstisch jeder Maschine von Turing in einer Schnur verschlüsseln. So können wir eine Maschine von Turing bauen, die auf seinem Band eine Schnur erwartet, die einen Handlungstisch beschreibt, der von einer Schnur gefolgt ist, die das Eingangsband beschreibt, und das Band schätzt, das die verschlüsselte Maschine von Turing geschätzt hätte. Turing hat solch einen Aufbau im ganzen Detail in seiner 1936-Zeitung beschrieben:

: "Es ist möglich, eine einzelne Maschine zu erfinden, die verwendet werden kann, um jede berechenbare Folge zu schätzen. Wenn diese Maschine U mit einem Band auf dem Anfang geliefert wird, über den der S.D ["Standardbeschreibung" eines Handlungstisches] einer Rechenmaschine M geschrieben wird, dann wird U dieselbe Folge wie M." schätzen

Speicherprogrammierter Computer

Davis macht ein überzeugendes Argument, dass die Vorstellung von Turing dessen, was jetzt als "der speicherprogrammierte Computer bekannt ist", die "Handlungstabelle" - die Instruktionen für die Maschine — in demselben "Gedächtnis" wie die Eingangsdaten zu legen, hat stark die Vorstellung von John von Neumann des ersten getrennten Symbols (im Vergleich mit dem Analogon) Computer — der EDVAC beeinflusst. Davis setzt Time Magazin zu dieser Wirkung, das "jeder an, der gegen eine Tastatur klopft... arbeitet an einer Verkörperung einer Maschine von Turing," und dass "John von Neumann auf der Arbeit von Alan Turing" (Davis 2000:193 [gebaut] hat, Time Magazin vom 29. März 1999 ansetzend).

Davis bringt Argumente vor, dass der Computer von Automatic Computing Engine (ACE) von Turing die Begriffe der Mikroprogrammierung (Mikrocode) und RISC Verarbeiter (Davis 2000:188) "vorausgesehen" hat. Knuth zitiert die Arbeit von Turing am HERVORRAGENDEN Computer als das Entwerfen "der Hardware, um Unterprogramm linkeage" (Knuth 1973:225) zu erleichtern; Davis bringt auch in dieser Arbeit als der Gebrauch von Turing einer Hardware "Stapel" (Davis 2000:237 Fußnote 18) Verweise an.

Da die Turing Maschine den Aufbau von Computern förderte, förderte der UTM die Entwicklung der Vogelinformatiken. Ein früher, wenn nicht das allererste, Monteur wurde "von einem jungen tollen Programmierer" für den EDVAC (Davis 2000:192) vorgeschlagen. Das "erste ernste Programm von Von Neumann sollte einfach... Daten effizient" (Davis 2000:184) sortieren. Knuth bemerkt, dass die Unterprogramm-Rückkehr, die im Programm selbst aber nicht in speziellen Registern eingebettet ist, von Neumann und Goldstine zuzuschreibend ist. Knuth setzt außerdem das fest

: "Wie man sagen kann, ist die erste interpretierende Routine die "Universale Turing Maschine"... Interpretierende Routinen im herkömmlichen Sinn wurden von John Mauchly in seinen Vorträgen in der Schule von Moore 1946 erwähnt... Turing hat an dieser Entwicklung auch teilgenommen; interpretierende Systeme für den HERVORRAGENDEN Versuchscomputer wurden unter seiner Richtung" (Knuth 1973:226) geschrieben.

Davis erwähnt kurz Betriebssysteme und Bearbeiter als Ergebnisse des Begriffs des Programms als die Daten (Davis 2000:185).

Einige könnten jedoch Themen mit dieser Bewertung aufbringen. Zurzeit (Mitte der 1940er Jahre zur Mitte der 1950er Jahre) ein relativ kleiner Kader von Forschern wurden mit der Architektur der neuen "Digitalcomputer" vertraut beteiligt. Hao Wang (1954), ein junger Forscher in dieser Zeit, hat die folgende Beobachtung gemacht:

Die:Turing'S-Theorie von berechenbaren Funktionen hat zurückdatiert, aber hat den umfassenden wirklichen Aufbau von Digitalcomputern nicht sehr beeinflusst. Diese zwei Aspekte der Theorie und Praxis sind fast völlig unabhängig von einander entwickelt worden. Der Hauptgrund besteht zweifellos darin, dass sich Logiker für Fragen interessieren, die von denjenigen radikal verschieden sind, mit denen die angewandten Mathematiker und Elektroingenieure in erster Linie betroffen werden. Es kann jedoch nicht scheitern, dasjenige als ziemlich sonderbar zu schlagen, dass häufig dieselben Konzepte durch sehr verschiedene Begriffe in den zwei Entwicklungen ausgedrückt werden." (Wang 1954, 1957:63)

Wang hat gehofft, dass sein Papier die zwei Annäherungen "verbinden würde." Tatsächlich bestätigt Minsky das: "Dass die erste Formulierung der Turing-Maschinentheorie in computerähnlichen Modellen in Wang (1957)" (Minsky 1967:200) erscheint. Minsky setzt fort, Gleichwertigkeit von Turing einer Gegenmaschine zu demonstrieren.

In Bezug auf die Verminderung von Computern zu einfachem Turing gleichwertige Modelle (und umgekehrt) ist die Benennung von Minsky von Wang als gemacht "die erste Formulierung" für die Debatte offen. Während sowohl das Papier von Minsky von 1961 als auch das Papier von Wang von 1957 von Shepherdson und Sturgis (1963) zitiert werden, zitieren sie auch und fassen in einem zusammen berichten über die Arbeit von europäischen Mathematikern Kaphenst (1959), Ershov (1959), und Péter (1958) ausführlich. Die Namen von Mathematikern Hermes (1954, 1955, 1961) und Kaphenst (1959) erscheinen in den Bibliografien sowohl von Sheperdson-Sturgis (1963) als auch von Elgot-Robinson (1961). Zwei andere wichtige Namen sind kanadische Forscher Melzak (1961) und Lambek (1961). Dafür sieh viel mehr Maschinenentsprechungen von Turing; Verweisungen können an der Register-Maschine gefunden werden.

Mathematische Theorie

Mit dieser Verschlüsselung von Handlungstischen als Schnuren wird es möglich im Prinzip für Maschinen von Turing, auf Fragen über das Verhalten anderer Maschinen von Turing zu antworten. Die meisten dieser Fragen sind jedoch unentscheidbar, bedeutend, dass die fragliche Funktion mechanisch nicht berechnet werden kann. Zum Beispiel, wie man zeigte, war das Problem der Bestimmung, ob eine willkürliche Maschine von Turing auf einem besonderen Eingang, oder auf allen Eingängen hinken wird, die als das Stockende Problem bekannt sind, im Allgemeinen in der ursprünglichen Zeitung von Turing, unentscheidbar. Der Lehrsatz von Reis zeigt, dass jede nichttriviale Frage über die Produktion einer Maschine von Turing unentscheidbar ist.

Eine universale Maschine von Turing kann jede rekursive Funktion berechnen, jede rekursive Sprache entscheiden, und irgendwelchen rekursiv enumerable Sprache akzeptieren. Gemäß der Kirch-Turing-These sind die durch eine universale Maschine von Turing lösbaren Probleme genau jene Probleme, die durch einen Algorithmus oder eine wirksame Methode der Berechnung für jede angemessene Definition jener Begriffe lösbar sind. Aus diesen Gründen dient eine universale Maschine von Turing als ein Standard, gegen den man rechenbetonte Systeme vergleicht, und ein System, das eine universale Maschine von Turing vortäuschen kann, abgeschlossenen Turing genannt wird.

Eine abstrakte Version der universalen Maschine von Turing ist die universale Funktion, eine berechenbare Funktion, die verwendet werden kann, um jede andere berechenbare Funktion zu berechnen. Der utm Lehrsatz beweist die Existenz solch einer Funktion.

Leistungsfähigkeit

Ohne Verlust der Allgemeinheit, wie man annehmen kann, ist der Eingang der Maschine von Turing im Alphabet {0, 1}; jedes andere begrenzte Alphabet kann über {0, 1} verschlüsselt werden. Das Verhalten einer Maschine von Turing M wird durch seine Übergang-Funktion bestimmt. Diese Funktion kann als eine Schnur über das Alphabet {0, 1} ebenso leicht verschlüsselt werden. Die Größe des Alphabetes der M, der Zahl von Bändern, die es, und die Größe des Zustandraums hat, kann aus dem Übergang-Funktionstisch abgeleitet werden. Die ausgezeichneten Staaten und Symbole können durch ihre Position identifiziert werden, z.B können die ersten zwei Staaten durch die Tagung, der Anfang und die Halt-Staaten sein. Folglich kann jede Maschine von Turing als eine Schnur über das Alphabet {0, 1} verschlüsselt werden. Zusätzlich berufen wir diese jede ungültige Verschlüsselung Karten zu einer trivialen Maschine von Turing ein, die sofort hinkt, und dass jede Maschine von Turing eine unendliche Zahl von encodings durch das Polstern der Verschlüsselung mit einer beliebigen Zahl dessen haben kann (sagen) 1's am Ende gerade wie die Anmerkungsarbeit auf einer Programmiersprache. Es sollte keine Überraschung sein, dass wir diese Verschlüsselung gegeben die Existenz einer Zahl von Gödel und rechenbetonter Gleichwertigkeit zwischen Maschinen von Turing und μ-Recursive-Funktionen erreichen können. Ähnlich verkehrt unser Aufbau zu jeder binären Schnur α, eine Maschine von Turing M.

Von der obengenannten Verschlüsselung 1966 anfangend, haben F. C. Hennie und R. E. Stearns gezeigt, dass gegeben eine Maschine von Turing M, die auf dem Eingang x innerhalb von N-Schritten hinkt, dann dort ein Mehrband universale Maschine von Turing besteht, die auf Eingängen α hinkt, x (gegeben auf verschiedenen Bändern) in CN loggen N, wo C eine maschinenspezifische Konstante ist, die von der Länge des Eingangs x nicht abhängt, aber wirklich von der Alphabet-Größe der M, Zahl von Bändern und Zahl von Staaten abhängt. Effektiv ist das ein O (N loggen N) Simulation.

Kleinste Maschinen

Als Alan Turing die Idee von einer universalen Maschine präsentiert hat, hat er das einfachste Rechenmodell im Sinn gehabt, das stark genug ist, um alle möglichen Funktionen zu berechnen, die berechnet werden können. Claude Shannon hat zuerst ausführlich die Frage gestellt, die kleinstmögliche universale Maschine von Turing 1956 zu finden. Er hat gezeigt, dass zwei Symbole genügend waren, so lange genug Staaten (oder umgekehrt) verwendet wurden, und dass es immer möglich war, Staaten durch Symbole auszutauschen.

Marvin Minsky hat eine universale 7-Staaten-4-Symbole-Maschine von Turing 1962 mit 2-Anhängsel-Systemen entdeckt. Andere kleine universale Maschinen von Turing sind von Yurii Rogozhin und anderen durch das Verlängern dieser Annäherung der Anhängsel-Systemsimulation seitdem gefunden worden. Wenn

wir zeigen durch (M, n) die Klasse von UTMs mit der M Staaten und n Symbole an, die die folgenden Tupel gefunden worden sind: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), und (2, 18). Rogozhin (4, 6) Maschine verwendet nur 22 Instruktionen, und kein normaler UTM der kleineren descriptional Kompliziertheit ist bekannt.

Jedoch lässt die Generalisierung des Standardmaschinenmodells von Turing noch kleineren UTMs zu. Eine solche Generalisation soll ein ungeheuer wiederholtes Wort auf einem oder beiden Seiten des Maschineneingangs von Turing erlauben, so die Definition der Allgemeinheit und bekannt als "halbschwache" oder "schwache" Allgemeinheit beziehungsweise erweiternd. Kleine schwach universale Maschinen von Turing, die die Regel 110 Zellautomat vortäuschen, sind für (6, 2), (3, 3), und (2, 4) Zustandsymbol-Paare gegeben worden. Der Beweis der Allgemeinheit für die 2-Staaten-3-Symbole-Maschine von Turing des Wolframs erweitert weiter den Begriff der schwachen Allgemeinheit durch das Erlauben bestimmter nichtperiodischer anfänglicher Konfigurationen. Andere Varianten auf dem Standardmaschinenmodell von Turing, die kleinen UTMs nachgeben, schließen Maschinen mit vielfachen Bändern oder Bändern der vielfachen Dimension, und mit einem begrenzten Automaten verbundene Maschinen ein.

Beispiel des Codierens der universalen Maschine

:For sehen diejenigen, die die Herausforderung übernehmen würden, einen UTM genau als angegebener Turing zu entwerfen, den Artikel von Davies in Copeland (2004:103ff). Davies korrigiert die Fehler im Original und zeigt, wie was eine geführte Probe aussehen würde. Er behauptet, (etwas vereinfacht) Simulation erfolgreich gelaufen zu sein.

Das folgende Beispiel wird von Turing (1936) genommen. Für mehr über dieses Beispiel sieh die Seite Maschinenbeispiele von Turing.

Turing hat sieben Symbole {A, C, D, R, L, N verwendet;}, um jeden 5-Tupel-zu verschlüsseln; wie beschrieben, in der Maschine des Artikels Turing sind seine 5 Tupel nur Typen N1, N2 und N3. Die Zahl jeder "M Konfiguration" (Instruktion, Staat) wird durch "D" vertreten, der von einer unären Schnur von A, d. h. "q3" = DAAA gefolgt ist. Auf eine ähnliche Weise verschlüsselt er das Symbol-Formblatt als "D", das Symbol "0" ist "Gleichstrom", das Symbol "1" als DCC usw. Die Symbole "R", "L", und "N" bleiben, wie ist.

Nach der Verschlüsselung von jedem 5-Tupel-wird dann in eine Schnur in der Ordnung, wie gezeigt, im folgenden Tisch "gesammelt":

Schließlich werden die Codes für alle vier 5 Tupel in einen Code aneinander gereiht, der mit angefangen ist";" und getrennt durch";" d. h.:

:

Dieser Code hat er auf abwechselnden Quadraten — den "F-Quadraten" - das Verlassen der "E-Quadrate" (diejenigen gelegt, die zur Ausradierung verantwortlich sind), leer. Der Endzusammenbau des Codes auf dem Band für die U-Maschine besteht daraus, zwei spezielle Symbole ("e") nacheinander, dann der Code getrennt auf abwechselnden Quadraten, und letzt dem Symbol des doppelten Doppelpunkts zu legen "::" (Formblätter gezeigt hier mit"." für die Klarheit):

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

Der Handlungstisch der U-Maschine (Zustandübergang-Tisch) ist dafür verantwortlich, die Symbole zu decodieren. Der Handlungstisch von Turing geht seinen Platz mit Anschreibern "u", "v", "x", "y", "z" durch das Stellen von ihnen in "E-Quadrate" "rechts vom gekennzeichneten Symbol" - zum Beispiel nach, um die aktuelle Instruktion zu kennzeichnen, wird z rechts von gelegt";" x behält den Platz in Bezug auf die aktuelle "M Konfiguration" DAA. Der Handlungstisch der U-Maschine wird diese Symbole ringsherum hin- und herbewegen (das Auslöschen von ihnen und Stellen von ihnen in verschiedenen Positionen), als die Berechnung fortschreitet:

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

Der Handlungstisch von Turing für seine U-Maschine ist sehr beteiligt.

Mehrere andere Kommentatoren (namentlich Penrose 1989) stellen Beispiele von Weisen zur Verfügung, Instruktionen für die Universale Maschine zu verschlüsseln. Wie Penrose tut, verwenden die meisten Kommentatoren nur binäre Symbole d. h. nur Symbole {0, 1}, oder {Formblatt, Zeichen |}. Penrose geht weiter und schreibt seinen kompletten U-Maschinencode (Penrose 1989:71-73) aus. Er behauptet, dass es aufrichtig ein U-Maschinencode, eine riesige Menge ist, die fast 2 ganze Seiten 1's und 0's abmisst. Für Leser, die für einfacheren encodings für die Post-Turing Maschine interessiert sind, kann die Diskussion von Davis in Steen (Steen 1980:251ff) nützlich sein.

Siehe auch

• Das Wechseln der Turing Maschine
• Von Neumann universaler Konstrukteur ein Versuch, ein Selbstwiederholen Maschine von Turing zu bauen
• Vollständigkeit von Turing

Allgemeine Verweisungen

• Arora, Sanjeev; Barak, Boaz, "Kompliziertheitstheorie: Eine Moderne Annäherung", Universität von Cambridge Presse, 2009, internationale Standardbuchnummer 978-0-521-42426-4, Abschnitt 1.4, "Maschinen als Schnuren und die universale Maschine von Turing" und 1.7, "Beweis des Lehrsatzes 1.9"

Samenpapiere

• F. C. Hennie und R. E. Stearns. Zwei-Bänder-Simulation des Mehrbandes Maschinen von Turing. JACM, 13 (4):533-546, 1966.

Andere Verweisungen

• .
• Goldstine, Herman H., und von Neumann, John, "Planend und von den Problemen für ein Elektronisches Recheninstrument", das Vertreter 1947, Institut für die Fortgeschrittene Studie, Princeton Codierend. Nachgedruckt auf Seiten 92-119 in Glocke, C. Gordon und Newell, Allen (1971), Computerstrukturen: Lesungen und Beispiele, McGraw-Hill Book Company, New York. Internationale Standardbuchnummer 0070043574}.
• Die erste von der Reihe von Knuth von drei Texten.

• (und). Nachgedruckt in der Hrsg. von Martin Davis (1965) Die Unentscheidbare, Rabe-Presse, Hewlett NY Seiten 115-154; mit Korrekturen zum UTM von Turing durch Emil Post vgl Fußnote 11 in Davis 1965:299.