Turing Maschine

Ein physisches Turing -Maschinenmodell. Eine echte Turing -Maschine hätte auf beiden Seiten unbegrenztes Klebeband, physische Modelle können jedoch nur eine endliche Menge an Klebeband haben.

Kurs von Automaten

(Klicken auf jede Ebene erhält einen Artikel zu diesem Thema)

A Turing Maschine ist ein mathematisches Berechnungsmodell Beschreibung eines abstrakte Maschine^[1] Das manipuliert Symbole auf einem Bandstreifen gemäß einer Regelnstabelle.^[2] Trotz der Einfachheit des Modells ist es in der Lage, alle implementieren Computeralgorithmus.^[3]

Die Maschine arbeitet auf einem Unendlichen^[4] Speicherband unterteilt in diskret Zellen,^[5] Jeder von ihnen kann ein einzelnes Symbol halten, das aus a gezogen wird endliche Menge von Symbolen, die die genannt werden Alphabet der Maschine. Es hat einen "Kopf", der zu jedem Zeitpunkt im Betrieb der Maschine über einem dieser Zellen positioniert ist und ein "Zustand" aus einem ausgewählt wird endliche Menge von Staaten. Bei jedem Schritt seiner Operation liest der Kopf das Symbol in seiner Zelle. Basierend auf dem Symbol und dem eigenen aktuellen Zustand der Maschine schreibt die Maschine ein Symbol in dieselbe Zelle und bewegt den Kopf einen Schritt nach links oder rechts.^[6] oder haltet die Berechnung an. Die Wahl, welches Ersatzsymbol zu schreiben ist und welche Richtung sich bewegen soll, basiert auf einer endlichen Tabelle, die angibt, was für jede Kombination des aktuellen Zustands und des gelesenen Symbols zu tun ist.

Die Turing -Maschine wurde 1936 von erfunden Alan Turing,^[7][8] Wer nannte es "a-machine" (automatische Maschine).^[9] Es war Turings Doktorand, Berater, Alonzo -Kirche, der später den Begriff "Turing Machine" in einer Bewertung geprägt hat.^[10] Mit diesem Modell konnte Turing zwei Fragen negativ beantworten:

• Gibt es eine Maschine, die bestimmen kann, ob eine willkürliche Maschine auf ihrem Klebeband "kreisförmig" ist (z. B. Einfrieren oder keine Berechnung der Rechenaufgabe)?
• Gibt es eine Maschine, die bestimmen kann, ob eine willkürliche Maschine auf ihrem Band jemals ein bestimmtes Symbol druckt?^[11][12]

Durch die Bereitstellung einer mathematischen Beschreibung eines sehr einfachen Geräts, das willkürliche Berechnungen in der Lage ist, konnte er die Eigenschaften der Berechnung im Allgemeinen nachweisen - und insbesondere insbesondere die Unkomputierbarkeit des Entscheidungsproblem ('Entscheidungsproblem').^[13]

Turing -Maschinen haben die Existenz grundlegender Einschränkungen für die Leistung der mechanischen Berechnung bewiesen.^[14] Während sie willkürliche Berechnungen ausdrücken können, macht sie ihr minimalistisches Design in der Praxis ungeeignet für die Berechnung: reale Welt Computers basieren auf verschiedenen Designs, die im Gegensatz zu Turing -Maschinen verwenden, Arbeitsspeicher.

Vollständigkeit ist die Fähigkeit für ein Anweisungssystem, eine Turing -Maschine zu simulieren. Eine Programmiersprache, die vollständig ist, ist theoretisch in der Lage, alle von Computern erfüllbaren Aufgaben auszudrücken. Fast alle Programmiersprachen sind vollständig abgeschlossen, wenn die Einschränkungen des endlichen Speichers ignoriert werden.

Überblick

Eine Turing -Maschine ist ein allgemeines Beispiel für a Zentrale Verarbeitungseinheit (CPU), die alle von einem Computer durchgeführten Datenmanipulation steuert, wobei die kanonische Maschine sequentielle Speicher zum Speichern von Daten verwendet. Insbesondere ist es eine Maschine (Automat) fähig zu Aufzählung einige willkürliche Teilmenge gültiger Zeichenfolgen von a Alphabet; Diese Saiten sind Teil von a rekursiv aufzählbarer Satz. Eine Turing -Maschine hat ein Band mit unendlicher Länge, auf dem sie Lese- und Schreibvorgänge ausführen kann.

Angenommen a FlugschreiberDie Turing -Maschine kann nicht wissen, ob sie letztendlich eine bestimmte Zeichenfolge der Teilmenge mit einem bestimmten Programm aufzählt. Dies liegt an der Tatsache, dass die Problem stoppen ist unlösbar, was erhebliche Auswirkungen auf die theoretischen Computergrenzen hat.

Die Turing -Maschine kann eine verarbeiten uneingeschränkte Grammatik, was weiter impliziert, dass es in der Lage ist, die Logik erster Ordnung auf unendliche Anzahl von Arten robust zu bewerten. Dies wird berühmt durch denonstriert Lambda -Kalkül.

Eine Turing -Maschine, die in der Lage ist, jede andere Turing -Maschine zu simulieren Universelle Turing -Maschine (UTM oder einfach eine universelle Maschine). Eine mathematisch orientierte Definition mit einer ähnlichen "universellen" Natur wurde von eingeführt von Alonzo -Kirche, dessen Arbeit an Lambda Calculus mit Turing in einer formalen Theorie von verknüpft ist Berechnung bekannt als These der Kirche. Die These besagt, dass Turing -Maschinen tatsächlich den informellen Begriff von erfassen Wirksame Methoden in Logik und Mathematikund liefern ein Modell, durch das man über eine argumentieren kann Algorithmus oder "mechanisches Verfahren". Ihr studieren abstrakte Eigenschaften gibt viele Einblicke in Informatik und Komplexitätstheorie.

Physische Beschreibung

In seinem Aufsatz von 1948 "Intelligent Machinery" schrieb Turing, dass seine Maschine aus:

... eine unbegrenzte Speicherkapazität, die in Form eines unendlichen Bandes in Quadrate erhältlich ist, auf denen jedes Symbol gedruckt werden konnte. Zu jedem Moment gibt es ein Symbol in der Maschine; Es heißt das gescannte Symbol. Die Maschine kann das gescannte Symbol ändern, und ihr Verhalten wird teilweise durch dieses Symbol bestimmt, aber die Symbole auf dem Band an anderer Stelle beeinflussen das Verhalten der Maschine nicht. Das Band kann jedoch durch die Maschine hin und her bewegt werden, wobei dies einer der elementaren Operationen der Maschine ist. Jedes Symbol auf dem Band kann daher schließlich ein Innings haben.^[15]

-Turing 1948, p. 3^[16]

Beschreibung

Der Turing Machine modelliert eine Maschine, die mechanisch auf einem Klebeband arbeitet. Auf diesem Klebeband sind Symbole, die die Maschine mit einem Bandkopf einzeln lesen und schreiben kann. Die Operation wird vollständig durch einen endlichen Satz elementarer Anweisungen bestimmt, wie z. 0, schreiben Sie eine 1 und wechseln Sie zu Zustand 6; " usw. im Originalartikel ("Auf berechnungsbare Zahlen, mit einer Anwendung auf das izschendungproblem", siehe auch Referenzen unten), Turing stellt sich keinen Mechanismus vor, sondern um eine Person, die er den "Computer" nennt, der diese deterministischen mechanischen Regeln sklavisch ausführt (oder wie Turing es "auf verzögerte Weise").

Der Kopf ist immer über einem bestimmten Quadrat des Bandes; Es wird nur ein endlicher Quadrate angezeigt. Die Anweisung, die durchgeführt werden soll (q₄) wird über dem gescannten Quadrat gezeigt. (Zeichnung nach Kleene (1952) S. 375.)

Hier der interne Zustand (q₁) wird im Kopf gezeigt, und die Abbildung beschreibt das Band als unendlich und mit "0" vorgefüllt, wobei das Symbol als leer dient. Der vollständige Zustand des Systems (seine "vollständige Konfiguration") besteht aus dem internen Zustand, nicht-Blank-Symbolen auf dem Band (in dieser Abbildung "11b") und der Position des Kopfes relativ zu den Symbolen, einschließlich Lücken, d. H. "011b ". (Zeichnung nach Minsky (1967) S. 121.)

Explizites besteht eine Turing -Maschine aus:

• A Band in Zellen unterteilt, einer neben dem anderen. Jede Zelle enthält ein Symbol aus einem endlichen Alphabet. Das Alphabet enthält ein spezielles leeres Symbol (hier als '0') und ein oder mehrere andere Symbole. Es wird angenommen, dass das Band willkürlich nach links und rechts ausziehbar ist, so dass die Turing -Maschine immer mit so viel Klebeband geliefert wird, wie es für seine Berechnung benötigt. Es wird angenommen, dass Zellen, die zuvor nicht geschrieben wurden, mit dem leeren Symbol gefüllt sind. In einigen Modellen hat das Band ein linkes Ende mit einem speziellen Symbol; Das Band erstreckt sich oder ist auf unbestimmte Zeit nach rechts erweiterbar.
• A Kopf Das kann Symbole auf das Klebeband lesen und schreiben und das Band links und rechts (und nur eine) Zelle jeweils verschieben. In einigen Modellen bewegt sich der Kopf und das Band ist stationär.
• A Staatsregister Das speichert den Zustand der Turing -Maschine, eines von endlich vieler. Darunter ist das Besondere Staat starten mit dem das Staatsregister initialisiert wird. Diese Staaten, die Turing schreibt, ersetzen die "Geisteszustand", die eine Person, die Berechnungen durchführt, normalerweise in der Lage sein.
• Eine endliche Tisch^[17] von Anweisungen^[18] das, angesichts der Zustand(q_i) Die Maschine ist derzeit in und das Symbol(a_j) Es wird auf dem Band gelesen (Symbol derzeit unter dem Kopf), teilt der Maschine mit der Reihe nach (Für die 5-Tupel-Modelle):

1. Entweder ein Symbol löschen oder schreiben (ersetzen a_j mit einer_J1).
2. Bewegen Sie den Kopf (der von D beschrieben wird_k und kann Werte haben: 'l' für einen Schritt links links oder 'R' für einen Schritt rechts oder 'N', um am selben Ort zu bleiben).
3. Nehmen Sie dasselbe oder a neuer Staat wie vorgeschrieben (gehen Sie zu Staat Q._I1).

In den 4-Tupel-Modellen, löschen oder schreiben ein Symbol (a_J1) und den Kopf nach links oder rechts bewegen (D._k) werden als separate Anweisungen angegeben. Die Tabelle zeigt, dass die Maschine (IA) ein Symbol löscht oder schreibt oder (ib) Bewegen Sie den Kopf nach links oder rechts, und dann (ii) Nehmen Sie denselben oder einen neuen Staat wie vorgeschrieben, jedoch nicht bei beiden Aktionen (IA) und (IB) in derselben Anweisung an. Wenn in einigen Modellen kein Eintrag in der Tabelle für die aktuelle Kombination von Symbol und Zustand vorhanden ist, wird die Maschine anhalten. Andere Modelle erfordern, dass alle Einträge gefüllt werden.

Jeder Teil der Maschine (d. H. Seine Zustand, Symbolkollektionen und Gebrauchtband zu einem bestimmten Zeitpunkt) und seine Aktionen (wie Druck, Löschung und Bandbewegung) ist endlich, diskret und unterscheidbar; Es ist die unbegrenzte Menge an Klebeband und Laufzeit, die ihm eine unbegrenzte Menge an verleiht Lagerraum.

Formale Definition

Folgen Hopcroft & Ullman (1979, p. 148) Harvtxt -Fehler: Kein Ziel: CitereFhopcroftullman1979 (Hilfe), eine (einköpfige) Turing-Maschine kann formell als 7- definiert werdenTupel ${\ displayStyle m = \ Langle q, \ gamma, b, \ sigma, \ delta, q_ {0}, f \ rangle}$ wo

• ${\ displayStyle \ gamma}$ ist ein endliches, nicht leeres Satz von Band Alphabet Symbole;
• ${\ displayStyle b \ in \ gamma}$ ist der leeres Symbol (Das einzige Symbol, das auf dem Klebeband in jedem Schritt während der Berechnung häufig auftreten kann);
• ${\ displaystyle \ sigma \ subseteq \ gamma \ setminus \ {b \}}$ ist der Satz von EingabymboleDas heißt, der Satz von Symbolen, die im Anfangsbandgehalt angezeigt werden dürfen;
• ${\ displayStyle q}$ ist ein endliches, nicht leeres Satz von Zustände;
• ${\ displayStyle q_ {0} \ in q}$ ist der Ausgangszustand;
• ${\ displayStyle f \ subseteq q}$ ist der Satz von letzte Zustände oder Staaten akzeptieren. Der anfängliche Bandinhalt soll sein akzeptiert durch ${\ displayStyle m}$ Wenn es irgendwann in einem Zustand anhält ${\ displayStyle f}$.
• ${\ displaystyle \ delta: (q \ setminus f) \ times \ gamma \ nicht \ bis Q \ Times \ gamma \ times \ {l, r \}}$ ist ein Teilfunktion genannt Übergangsfunktion, wobei l links verändert ist, ist R die rechte Verschiebung. Wenn ${\ displayStyle \ Delta}$ ist nicht am aktuellen Status und dem aktuellen Bandsymbol definiert, dann hält die Maschine an;^[19] Intuitiv gibt die Übergangsfunktion den nächsten Status an, das aus dem aktuellen Zustand transportiert wurde, welches Symbol das vom Kopf gezeigte aktuelle Symbol und die nächste Kopfbewegung überschreiben kann.

3-Staatenbeschäftigter Biber. Schwarze Ikonen repräsentieren den Standort und den Zustand des Kopfes; Quadratfarben repräsentieren 1s (orange) und 0s (weiß); Die Zeit verläuft vertikal von oben bis zur HALT Geben Sie unten an.

Darüber hinaus kann die Turing -Maschine auch einen Ablehnungszustand haben, um die Ablehnung expliziter zu gestalten. In diesem Fall gibt es drei Möglichkeiten: Akzeptieren, Ablehnen und Laufen für immer. Eine andere Möglichkeit besteht darin, die Endwerte auf dem Band als Ausgabe zu betrachten. Wenn jedoch der einzige Ausgang der endgültige Zustand ist, in dem die Maschine endet (oder nie anhält), kann die Maschine eine längere Zeichenfolge effektiv ausgeben, indem sie eine Ganzzahl aufnimmt, die ihm mitteilt, welches Bit der String -Ausgabe ist.

Eine relativ ungewöhnliche Variante ermöglicht "keine Verschiebung", beispielsweise N als drittes Element des Anweisungssatzes ${\ displayStyle \ {l, r \}}$.

Das 7-tupel für den 3-Staaten Beschäftigter Biber Sieht so aus (siehe mehr über diesen vielbeschäftigten Biber bei Beispiele für Maschine):

• $oder$ (Zustände);
• ${\ displayStyle \ gamma = \ {0,1 \}}$ (Band Alphabet Symbole);
• ${\ displayStyle b = 0}$ (leeres Symbol);
• ${\ displayStyle \ sigma = \ {1 \}}$ (Eingabesymbole);
• ${\ displayStyle q_ {0} = {\ mbox {a}}}$ (Ausgangszustand);
• ${\ displayStyle f = \ {{\ mbox {halt}} \}}$ (letzte Zustände);
• ${\ displayStyle \ delta =}$ Siehe Zustandstabelle unten (Übergangsfunktion).

Anfangs sind alle Bandzellen mit markiert mit ${\ displayStyle 0}$.

Zusätzliche Details zur Visualisierung oder Implementierung von Turing -Maschinen erforderlich

In den Worten von Van Emde Boas (1990), p. 6: "Das set-theoretische Objekt [seine formale Beschreibung von sieben Tupeln ähnlich wie die oben genannten] enthält nur teilweise Informationen darüber, wie sich die Maschine verhalten wird und wie seine Berechnungen aussehen werden."

Zum Beispiel,

• Es muss viele Entscheidungen darüber geben, wie die Symbole tatsächlich aussehen, und eine fehlsichere Art zum Lesen und Schreiben von Symbolen auf unbestimmte Zeit.
• Die Verschiebung nach links und der Verschiebung rechts kann den Klebebandkopf über das Klebeband verschieben, aber wenn Sie tatsächlich eine Turing -Maschine bauen, ist es praktischer, stattdessen das Band stattdessen unter dem Kopf hin und her zu rutschen.
• Das Klebeband kann endlich sein und nach Bedarf automatisch mit Lücken erweitert werden (was der mathematischen Definition am nächsten ist), aber es ist häufiger, es als unendlich an einem oder beiden Enden zu dehnen und mit Blanks vorgefüllt zu werden, außer auf dem Explizit gegebenes endliches Fragment Der Klebebandkopf ist eingeschaltet. (Dies ist in der Praxis natürlich nicht implementierbar.) Das Band kann nicht Länge festhalten, da dies nicht der angegebenen Definition entsprechen und den Berechnungsbereich ernsthaft begrenzen würde, der die Maschine auf die von a ausführen kann linear begrenzter Automaten Wenn das Band proportional zur Eingangsgröße war, oder Finite-State-Maschine Wenn es streng festgelegt war.

Alternative Definitionen

Definitionen in der Literatur unterscheiden sich manchmal geringfügig, um Argumente oder Beweise zu erleichtern oder klarer zu machen, aber dies wird immer so geschehen, dass die resultierende Maschine die gleiche Rechenleistung hat. Zum Beispiel könnte der Satz von geändert werden von ${\ displayStyle \ {l, r \}}$ zu ${\ displayStyle \ {l, r, n \}}$, wo N ("Keine" oder "No-Operation") würde es der Maschine ermöglichen, in derselben Bandzelle zu bleiben, anstatt sich nach links oder rechts zu bewegen. Dies würde die Rechenleistung der Maschine nicht erhöhen.

Die häufigste Konvention repräsentiert jede "Turing-Anweisung" in einer "Turing-Tabelle" durch eine von neun 5-Tupel, gemäß der Konvention von Turing/Davis (Turing (1936) in Das unentscheidbare, p. 126-127 und Davis (2000) p. 152):

(Definition 1): (q_i, S_j, S_k/E/n, l/r/n, q_m)

( aktuellen Zustand q_i , Symbol gescannt S_j , Drucksymbol S_k/löschen E/keiner N , MOVE_TAPE_one_Square links L/Rechts R/keiner N , neuer Staat q_m )

Andere Autoren (Minsky (1967) S. 119, Hopcroft und Ullman (1979) S. 158, Stone (1972), S. 9) verabschiedet eine andere Konvention mit neuem Staat q_m unmittelbar nach dem gescannten Symbol s gelistet_j:

(Definition 2): (q_i, S_j, q_m, S_k/E/n, l/r/n)

( aktuellen Zustand q_i , Symbol gescannt S_j , neuer Staat q_m , Drucksymbol S_k/löschen E/keiner N , MOVE_TAPE_one_Square links L/Rechts R/keiner N )

Für den Rest dieses Artikels wird "Definition 1" (die Turing/Davis -Übereinkommen) verwendet.

In der folgenden Tabelle erlaubte Turings ursprüngliches Modell nur die ersten drei Zeilen, die er N1, N2, N3 bezeichnete (vgl. Turing in Das unentscheidbare, p. 126). Er erlaubte das Löschen des "gescannten Quadrats", indem er ein 0. Symbol s benannte₀ = "löschen" oder "leer" usw. Erließ er jedoch nicht, dass er nicht gedruckt wird, daher enthält jede Anweisungslinie "Drucksymbol s"_k"oder" Erase "(vgl. Fußnote 12 in Post (1947), Das unentscheidbare, p. 300). Die Abkürzungen sind Turings (Das unentscheidbare, p. 119). Nach Turings Originalpapier in den Jahren 1936–1937 ermöglichten maschinelle Modelle allen neun möglichen Arten von Fünf-Tupel:

Jede Turing-Tabelle (Liste der Anweisungen) kann aus den oben genannten neun 5-Tupeln erstellt werden. Aus technischen Gründen können die drei nicht gedruckten oder "N" -Heanweisungen (4, 5, 6) normalerweise abgegeben werden. Beispiele siehe Beispiele für Maschine.

Weniger häufig werden die Verwendung von 4-Tupel auftreten: Diese stellen eine weitere Zerstörung der Turing-Anweisungen dar (vgl. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-sigal-weyuker (1994)); Sehen Sie auch mehr bei Post -Turing -Maschine.

Der Staat"

Das Wort "Zustand", das im Kontext von Turing -Maschinen verwendet wird, kann eine Quelle der Verwirrung sein, da es zwei Dinge bedeuten kann. Die meisten Kommentatoren nach Turing haben "Status" verwendet, um den Namen/Bezeichner der aktuellen Anweisung zu bedeuten - d. H. Der Inhalt des Staatsregisters. Turing (1936) machte jedoch eine starke Unterscheidung zwischen einer Aufzeichnung dessen, was er als "M-Konfiguration" der Maschine bezeichnete, und dem "Zustand des Fortschritts der Maschine" durch die Berechnung-den aktuellen Zustand des Gesamtsystems. Was Turing "die Zustandsformel" nannte alle Die Symbole auf dem Band:

Somit wird der Fortschrittszustand der Berechnung in jeder Phase vollständig durch die Anweisungen von Anweisungen und die Symbole auf dem Band bestimmt. Das heißt, das Systemzustand kann durch eine einzelne Expression (Sequenz von Symbolen) beschrieben werden, die aus den Symbolen auf dem Klebeband besteht, gefolgt von δ (das nicht an anderer Stelle erscheinen soll) und dann durch die Anweisungen. Dieser Ausdruck wird als "Zustandsformel" bezeichnet.

-Das unentscheidbare, S. 139–140, Hervorhebung hinzugefügt

Zu Beginn seiner Arbeit trug Turing dies noch weiter: Er gibt ein Beispiel, in dem er ein Symbol für die aktuelle "M-Konfiguration"-das Befehlsetikett-auf dem gescannten Quadrat zusammen mit allen Symbolen auf dem Band (das Label der Anweisung-platziert hat.Das unentscheidbare, p. 121); Dies nennt er "das Vollständige Konfiguration"(Das unentscheidbare, p. 118). Um die "vollständige Konfiguration" in einer Zeile zu drucken, legt er die staatliche/m-Konfiguration in die links des gescannten Symbols.

Eine Variante davon ist in Kleene (1952) zu sehen, wo Kleene zeigt, wie man das schreibt Gödel -Nummer der "Situation" einer Maschine: Er platziert das Symbol "M-Configuration" q₄ über dem gescannten Quadrat in ungefähr der Mitte der 6 Nicht-Blank-Quadrate auf dem Band (siehe die Turing-Tape-Figur in diesem Artikel) und legt es in die Rechts des gescannten Platzes. Aber Kleene bezieht sich auf "q₄"selbst als" der Maschinenzustand "(Kleene, S. 374-375). Hopcroft und Ullman nennen dies zusammengesetzt als" Instantane Beschreibung "und folgen Sie der Turing-Konvention, den" aktuellen Zustand "zu setzen (Anweisungsmarken, M-Konfiguration), zum links des gescannten Symbols (S. 149), dh die momentane Beschreibung ist die Zusammensetzung von Nicht-Blank-Symbolen links, den Zustand der Maschine, das vom Kopf gescannte aktuelle Symbol und die Nicht-Blank-Symbole nach rechts .

Beispiel: Gesamtzustand des 2-staatlichen 2-symbolsbeschäftigten Bibers nach 3 "Bewegungen" (Aus dem Beispiel "Lauf" in der Abbildung unten):

1A1

Das bedeutet: Nach drei Bewegungen hat das Band ... 000110000 ... darauf scannt der Kopf nach rechts 1 und der Zustand ist A. Leerzeichen (in diesem Fall, die durch "0" s dargestellt werden) können Teil des Gesamtzustands sein, wie hier gezeigt: B01; Das Band hat eine einzelne 1 darauf, aber der Kopf scannt die 0 ("leer") links und der Zustand ist B.

"Status" im Kontext von Turing -Maschinen sollte klargestellt werden, welche beschrieben wird: die aktuelle Anweisung oder die Liste der Symbole auf dem Band zusammen mit der aktuellen Anweisung oder der Liste der Symbole auf dem Band zusammen mit der aktuellen Anweisung links vom gescannten Symbol oder rechts vom gescannten Symbol platziert.

Turings Biograf Andrew Hodges (1983: 107) hat diese Verwirrung bemerkt und diskutiert.

Diagramme "Staat"

Die Turing-Maschine "3-Staatenbeschäftigter Biber" in a Finite-State-Darstellung. Jeder Kreis repräsentiert einen "Zustand" der Tabelle-eine "M-Konfiguration" oder "Anweisung". "Richtung" eines Zustands Überleitung wird durch einen Pfeil gezeigt. Das Etikett (z. 0/p, r) In der Nähe des ausgehenden Zustands (am "Schwanz" des Pfeils) gibt das gescannte Symbol an, das einen bestimmten Übergang verursacht (z. 0) gefolgt von einem Schrägstrich /, gefolgt von den nachfolgenden "Verhaltensweisen" der Maschine, z. "P drucken"Dann bewegen Sie Band"R Rechts"Es gibt kein allgemein anerkanntes Format. Die gezeigte Konvention ist nach McClusky (1965), Booth (1967), Hill und Peterson (1974).

Rechts: Die obige Tabelle, die als "Zustandsübergangs" -Diagramm ausgedrückt wird.

Normalerweise werden große Tische besser als Tische gelassen (Stand, S. 74). Sie werden leichter von Computer in tabellarischer Form simuliert (Booth, S. 74). Bestimmte Konzepte - e.g. Maschinen mit "Reset" -Staaten und Maschinen mit sich wiederholenden Mustern (vgl. Hill und Peterson S. 244ff) - können leichter gesehen werden, wenn sie als Zeichnung angesehen werden.

Ob eine Zeichnung eine Verbesserung in ihrer Tabelle darstellt, muss vom Leser für den jeweiligen Kontext entschieden werden.

Die Entwicklung der berechtigten Biberberechnung beginnt oben und geht nach unten.

Der Leser sollte erneut gewarnt werden, dass solche Diagramme einen Schnappschuss ihres in der Zeit eingefrorenen Tisches darstellen. nicht Der Kurs ("Trajektorie") einer Berechnung durch Zeit und Raum. Während die geschäftige Bibermaschine jedes Mal, wenn es "ausgeführt" "ausführt", immer demselben Zustandsstromschutzgebiet folgt, gilt dies nicht für die "Kopier" -Maschine, die mit variablen Eingabe-Parametern versorgt werden kann.

Das Diagramm "Fortschritt der Berechnung" zeigt den Fortschritt des dreistaatlichen Beschälters von Beaver (Anweisungen) (Anweisungen) durch ihre Berechnung von Anfang bis Ende. Auf ganz rechts befindet sich die Turing "Complete Configuration" (Kleene "Situation", Hopcroft -ullman "Instantaneous Beschreibung") bei jedem Schritt. Wenn die Maschine gestoppt und gelöscht werden sollte, um sowohl das "Statusregister" als auch das gesamte Klebeband zu leer, könnten diese "Konfigurationen" verwendet werden, um eine Berechnung überall in ihrem Fortschritt wieder aufzunehmen (vgl. Turing (1936). Das unentscheidbare, S. 139–140).

Äquivalente Modelle

Viele Maschinen, von denen angenommen wird, dass sie mehr Rechenfunktion haben als eine einfache universelle Turing -Maschine, können nicht mehr Strom haben (Hopcroft und Ullman S. 159, vgl. Minsky (1967)). Sie könnten möglicherweise schneller berechnen oder weniger Speicher verwenden, oder deren Anweisungssatz kann kleiner sein, aber sie können jedoch nicht stärker berechnen (d. H. Materiellere Funktionen). (Das These der Kirche und tätige These hypothetisiert Dies gilt für jede Art von Maschine: alles, was "berechnet" werden kann, kann von einer Turing -Maschine berechnet werden.)

Eine Turing-Maschine entspricht einem Einzelstapel Pushdown -Automaten (PDA), das durch Entspannen der zuletzt rein, zuerst raus (LIFO) Anforderung seines Stapels. Darüber hinaus entspricht eine Turing-Maschine einer Zwei-Stapel-PDA mit Standard-LIFO-Semantik, indem ein Stapel verwendet wird, um das Band links vom Kopf und den anderen Stapel für das Band rechts zu modellieren.

Im anderen extrem werden einige sehr einfache Modelle als sein Turing-äquivalent, d.h.

Gemeinsame äquivalente Modelle sind die Multitape-Turing-Maschine, Multi-Spur-Turing-MaschineMaschinen mit Eingang und Ausgabe und die nicht deterministisch Turing Maschine (NDTM) im Gegensatz zu der deterministisch Turing Machine (DTM), für die die Aktionstabelle höchstens einen Eintrag für jede Kombination aus Symbol und Zustand hat.

Schreibgeschützte, rechtlebende Turing-Maschinen sind äquivalent zu Dfas (ebenso gut wie NFAs durch Konvertierung mit der NDFA zu DFA -Konvertierungsalgorithmus).

Für praktische und didaktische Absichten das Äquivalent Registrieren Sie Maschine kann als übliches verwendet werden Montage Programmiersprache.

Eine relevante Frage ist, ob das durch konkrete Programmiersprachen dargestellte Berechnungsmodell ein äquivalent ist. Während die Berechnung eines realen Computers auf endlichen Zuständen basiert und daher nicht in der Lage ist, eine Turing -Maschine zu simulieren, haben die Programmiersprachen selbst nicht unbedingt diese Einschränkung. Kirner et al., 2009 haben gezeigt, dass unter den allgemeinen Programmiersprachen einige vollständig sind, während andere dies nicht tun. Zum Beispiel, Ansi c ist nicht äquivalent, da alle Instanziationen von ANSI C (verschiedene Instanziationen möglich sind, da der Standard bestimmte Verhaltensweisen aus Legacy-Gründen absichtlich undefiniert lässt) ein endliches Raumgedächtnis implizieren. Dies liegt daran, dass die Größe der Speicherreferenzdatentypen genannt wird Zeiger, ist in der Sprache zugänglich. Andere Programmiersprachen mögen jedoch Pascal Haben Sie diese Funktion nicht, mit der sie grundsätzlich vollständig abgeschlossen werden können. Es ist nur grundsätzlich vollständig abgeschlossen, als Speicherzuweisung In einer Programmiersprache dürfen die Programmiersprache bei der Ignorierung fehlgeschlagener Speicherzuweisungen abgeschlossen sein, aber die kompilierten Programme, die auf einem realen Computer ausführen, kann dies nicht.

Wahl C-Maschinen, Oracle O-Maschinen

Zu Beginn seines Papiers (1936) unterscheidet Turing zwischen einer "automatischen Maschine" - IST "Bewegung ... vollständig durch die Konfiguration bestimmt" und eine "Auswahlmaschine":

... deren Bewegung nur teilweise durch die Konfiguration bestimmt wird. Wenn eine solche Maschine eine dieser mehrdeutigen Konfigurationen erreicht, kann sie erst dann weitergehen, bis eine beliebige Auswahl von einem externen Bediener getroffen wurde. Dies wäre der Fall, wenn wir Maschinen verwenden würden, um mit axiomatischen Systemen umzugehen.

-Das unentscheidbare, p. 118

Turing (1936) arbeitet nur in einer Fußnote, in der er beschreibt, wie man eine A-Maschine verwendet, um "alle nachweisbaren Formeln des [Hilbert] -Kalculus zu finden", anstatt eine Auswahlmaschine zu verwenden. Er "vermutet [s], dass die Auswahl immer zwischen zwei Möglichkeiten von 0 und 1 liegt. Jeder Beweis wird dann durch eine Folge von Auswahl₁, ich₂, ..., ich_n (ich₁ = 0 oder 1, ich₂ = 0 oder 1, ..., ich_n = 0 oder 1) und daher die Zahl 2ⁿ + i₁2^N-1 + i₂2^N-2 + ... + i_n bestimmt den Beweis vollständig. Die automatische Maschine führt nacheinander Beweis 1, Proof 2, Proof 3, ... "(Fußnote ‡, Das unentscheidbare, p. 138)

Dies ist in der Tat die Technik, mit der eine deterministische (d. H. A-) Turing-Maschine verwendet werden kann, um die Wirkung von a nachzuahmen Nichtdeterministische Turing -Maschine; Turing löste die Angelegenheit in einer Fußnote und scheint sie von weiteren Betrachtungen abzulehnen.

Ein Oracle Machine oder O-Machine ist eine Turing-A-Maschine, die im Zustand der Berechnung pausiert. "o"Während es, seine Berechnung abzuschließen, wartet es" die Entscheidung "des" Orakels " - eine nicht näher bezeichnete Entität", abgesehen davon, dass es keine Maschine sein kann "(Turing (1939). Das unentscheidbare, p. 166–168).

Universelle Turing -Maschinen

Eine Implementierung einer Turing -Maschine

Wie Turing schrieb Das unentscheidbare, p. 128 (Kursivschrift hinzugefügt):

Es ist möglich, a zu erfinden Einzelmaschine mit deren Berechnung verwendet werden kann irgendein berechnungsbare Sequenz. Wenn diese Maschine U wird mit dem Klebeband geliefert, auf dessen Anfang die Quintuole geschrieben wird, die durch Semikolonen einer Computermaschine getrennt ist M, dann U berechnet die gleiche Sequenz wie M.

Dieser Befund ist nun für selbstverständlich, aber zu der Zeit (1936) wurde es als erstaunlich angesehen. Das Modell der Berechnung, das Turing seine "universelle Maschine" nannte - " -"U"Kurz gesagt - wird von einigen (vgl. Davis (2000)) als grundlegender theoretischer Durchbruch angesehen, der zum Begriff der Begriffe des Computerprotokollcomputer.

Turings Papier ... enthält im Wesentlichen die Erfindung des modernen Computers und einige der damit verbundenen Programmierechniken.

-Minsky (1967), p. 104

Bezüglich Rechenkomplexität, eine universelle Turing-Maschine mit mehreren Tätern muss nur langsamer sein logarithmisch Faktor im Vergleich zu den Maschinen, die es simuliert. Dieses Ergebnis wurde 1966 von F. C. Hennie und erzielt R. E. Stearns. (Arora und Barak, 2009, Theorem 1.9)

Vergleich mit echten Maschinen

Eine Turing -Maschinen -Realisierung mit Verwendung Lego Stücke

Es wird oft geglaubt^{[Nach wem?]} Diese Turing -Maschinen sind im Gegensatz zu einfacheren Automaten so leistungsstark wie echte Maschinen und können jeden Vorgang ausführen, den ein echtes Programm kann. Was in dieser Aussage vernachlässigt wird, ist das, weil eine echte Maschine nur eine begrenzte Anzahl von haben kann Konfigurationen, es ist nichts als ein Finite-State-MaschineWährend eine Turing -Maschine eine unbegrenzte Menge an Speicherplatz für ihre Berechnungen bietet.

Es gibt eine Reihe von Möglichkeiten, um zu erklären, warum Turing -Maschinen nützliche Modelle realer Computer sind:

• Alles, was ein echter Computer berechnen kann, kann auch eine Turing -Maschine berechnen. Zum Beispiel: "Eine Turing-Maschine kann jede Art von Unterroutine simulieren, die in Programmiersprachen enthalten sind, einschließlich rekursiger Verfahren und der bekannten Parameter-Passing-Mechanismen" (Hopcroft und Ullman, S. 157). Eine ausreichend große FSA kann auch jeden wirklichen Computer modellieren und IO nicht berücksichtigen. Somit gilt auch eine Erklärung zu den Einschränkungen von Turing -Maschinen für reale Computer.
• Der Unterschied liegt nur mit der Fähigkeit einer Turing -Maschine, eine unbegrenzte Datenmenge zu manipulieren. Angesichts einer begrenzten Zeit kann eine Turing -Maschine (wie eine echte Maschine) jedoch nur eine begrenzte Datenmenge manipulieren.
• Wie eine Turing -Maschine kann ein echter Computer den Speicherplatz bei Bedarf vergrößern, indem mehr Festplatten oder andere Speichermedien erfasst werden.
• Beschreibungen realer Maschinenprogramme unter Verwendung einfacherer abstrakter Modelle sind häufig viel komplexer als Beschreibungen mit Turing -Maschinen. Beispielsweise kann eine Turing -Maschine, die einen Algorithmus beschreibt, einige hundert Zustände aufweist, während das äquivalente deterministische endliche Automat (DFA) auf einer bestimmten realen Maschine über Gradrillionen verfügt. Dies macht die DFA -Darstellung zu analysieren.
• Turing -Maschinen beschreiben Algorithmen, die unabhängig davon sind, wie viel Speicher sie verwenden. Es gibt eine Grenze für den Speicher, der von jeder aktuellen Maschine besessen ist, aber diese Grenze kann sich mit der Zeit willkürlich erhöhen. Turing -Maschinen ermöglichen es uns, Aussagen zu Algorithmen zu machen, die (theoretisch) für immer greifen, unabhängig von Fortschritten in konventionell Computermaschinenarchitektur.
• Turing -Maschinen vereinfachen die Anweisung der Algorithmen. Algorithmen, die mit Turing-äquivalenten abstrakten Maschinen ausgeführt werden, sind in der Regel allgemeiner als ihre Gegenstücke, die auf realen Maschinen ausgeführt werden, da sie Datentypen zur Verfügung stehen und sich nie mit unerwarteten Bedingungen befassen (einschließlich, aber nicht beschränkt auf das Laufen aus dem Gedächtnis).

Eine weitere Realisierung von Turing Machine

Einschränkungen

Computerkomplexitätstheorie

Eine Einschränkung von Turing -Maschinen besteht darin, dass sie die Stärken einer bestimmten Anordnung nicht gut modellieren. Zum Beispiel sind moderne Computer des gespeicherten Programms tatsächlich Fälle einer spezifischeren Form von abstrakte Maschine bekannt als Zufälliger Zugriff gespeicherte Produktmaschine oder Raspe Machine Model. Wie die universelle Turing-Maschine speichert das RASP sein "Programm" in "Speicher" extern zu den "Anweisungen" der Finite-State-Maschine. Im Gegensatz zur universellen Turing -Maschine hat die Raspe eine unendliche Anzahl unterscheidbarer, nummerierter, aber unbegrenzter "Register" - Memory "Zellen", die jede ganze Zahl enthalten können (vgl. Elgot und Robinson (1964), Hartmanis (1971) und insbesondere Cook -Rechow (1973); Referenzen bei Zufallszugriffsmaschine). Die Finite-State-Maschine des RASP ist mit der Fähigkeit zur indirekten Adressierung ausgestattet (z. B. kann der Inhalt eines Registers als Adresse verwendet werden, um ein anderes Register anzugeben). Somit kann das "Programm" des RASP jedes Register in der Registersequenz ansprechen. Das Ergebnis dieser Unterscheidung besteht darin, dass es Rechenoptimierungen gibt, die basierend auf den Speicherindizes durchgeführt werden können, die in einer allgemeinen Turing -Maschine nicht möglich sind. Wenn also Turing -Maschinen als Grundlage für die Begrenzungslaufzeiten verwendet werden, kann an bestimmten Algorithmen der Laufzeiten eine "falsch untere Grenze" nachgewiesen werden (aufgrund der falschen Vereinfachung einer Turing -Maschine). Ein Beispiel dafür ist binäre Suche, ein Algorithmus, der gezeigt werden kann, dass er schneller funktioniert, wenn das RASP -Modell der Berechnung und nicht das Turing -Maschinenmodell verwendet wird.

Parallelität

Eine weitere Einschränkung von Turing -Maschinen besteht darin, dass sie die Parallelität nicht gut modellieren. Zum Beispiel gibt es eine Grenze der Ganzzahl, die von einer immer halbierenden nicht-deterministischen Turing-Maschine berechnet werden kann, die mit einem leeren Klebeband beginnt. (Siehe Artikel über Unbefragter Nichtdeterminismus.) Im Gegensatz dazu gibt es immer hälfte gleichzeitige Systeme ohne Eingaben, die eine Ganzzahl von unbegrenzter Größe berechnen können. (Ein Vorgang kann mit lokalem Speicher erstellt werden, der mit einer Anzahl von 0 initialisiert wird, die sich gleichzeitig sowohl einen Stopp als auch eine Go -Nachricht sendet. Wenn er eine Go -Nachricht erhält, erhöht er seine Anzahl um 1 und sendet sich selbst eine Go -Nachricht. Es erhält eine Stop -Nachricht, es wird mit einer unbegrenzten Zahl in der lokalen Lagerung gestellt.)

Interaktion

In den frühen Berechnungstagen war der Computergebrauch normalerweise beschränkt auf Stapelverarbeitung, d.h., nicht interaktive Aufgaben, die jeweils Ausgabedaten aus angegebenen Eingabedaten erstellen. Die Computerabilitätstheorie, die die Berechnung von Funktionen von Eingaben zu Ausgängen untersucht und für die Turing -Maschinen erfunden wurden, spiegelt diese Praxis wider.

Seit den 1970er Jahren, interaktiv Die Verwendung von Computern wurde viel häufiger. Im Prinzip ist es möglich, dies zu modellieren, indem ein externer Agent aus dem Band gelesen und gleichzeitig mit einem Turing -Computer darauf geschrieben wird, aber dies stimmt selten wie die Interaktion tatsächlich entspricht. Daher bei der Beschreibung der Interaktivität Alternativen wie z. E/O -Automaten werden normalerweise bevorzugt.

Geschichte

Sie wurden 1936 von beschrieben von Alan Turing.

Historischer Hintergrund: Computermaschinerie

Robin Gandy (1919–1995) - ein Student von Alan Turing (1912–1954) und sein lebenslanger Freund - transportiert die Abstammung des Begriffs der "Berechnung von Maschine" zurück zu Charles Babbage (circa 1834) und schlägt tatsächlich "Babbage's Thesis" vor:

Dass die gesamte Entwicklung und Operationen der Analyse jetzt von Maschinen ausgeführt werden können.

-(Kursivschrift in Babbage, zitiert von Gandy, S. 54)

Gandys Analyse von Babbage's analytischer Motor Beschreibt die folgenden fünf Operationen (vgl. S. 52–53):

• Die arithmetischen Funktionen +, -, ×, wobei - die "richtige" Subtraktion anzeigt x − y = 0 wenn y ≥ x.
• Jede Abfolge von Operationen ist eine Operation.
• Iteration einer Operation (Wiederholung n -mal ein Operation P).
• Bedingte Iteration (Wiederholung n -mal eine Operation P, die vom "Erfolg" des Tests T abhängig ist).
• Bedingte Übertragung (d. H. Bedingte "gehe zu").

Gandy stellt fest, dass "die Funktionen, die durch (1), (2) und (4) berechnet werden können, genau diejenigen sind, die sind Rechenbar. "(S. 53). Er zitiert andere Vorschläge für" universelle Berechnungsmaschinen ", einschließlich der von denen von Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937). Jedoch:

… Der Schwerpunkt liegt auf der Programmierung einer festen iterbaren Abfolge von arithmetischen Operationen. Die grundlegende Bedeutung der bedingten Iteration und der bedingten Übertragung für eine allgemeine Theorie der Berechnung von Maschinen wird nicht erkannt…

-Gandy p. 55

Das entscheidungsproblem (das "Entscheidungsproblem"): Hilberts zehnte Frage von 1900

Hinsichtlich Hilberts Probleme posiert vom berühmten Mathematiker David Hilbert Im Jahr 1900 schwebte ein Aspekt des Problems Nr. 10 fast 30 Jahre lang, bevor er genau gerahmt wurde. Hilberts ursprünglicher Ausdruck für Nr. 10 lautet wie folgt:

10. Bestimmung der Lösbarkeit einer diophantinischen Gleichung. Angenommen Diophantinengleichung mit einer beliebigen Anzahl unbekannter Mengen und mit rationalen integralen Koeffizienten: einen Prozess zu entwickeln, nach dem er in einer begrenzten Anzahl von Operationen bestimmt werden kann, ob die Gleichung in rationalen Ganzzahlen löslich ist. Das entscheidungsproblem [Entscheidungsproblem für Logik erster Ordnung] wird gelöst, wenn wir ein Verfahren kennen, das es einem bestimmten logischen Ausdruck ermöglicht, durch endlich viele Operationen seine Gültigkeit oder Erfüllbarkeit zu entscheiden. Das Inent -Idung -Problem muss als Hauptproblem der mathematischen Logik angesehen werden.

-Zitiert mit dieser Übersetzung und dem ursprünglichen Deutsch in Derhowitz und Gurevich, 2008

Bis 1922 dieser Begriff von "Entscheidungsproblem"hatte ein bisschen entwickelt und H. Behann erklärte das

... Die allgemeine Form des Inentscheidungsproblems ist wie folgt:

Es ist ein recht eindeutiges allgemein anwendbares Rezept erforderlich, mit dem man sich in einer begrenzten Anzahl von Schritten entscheiden kann. Die Wahrheit oder Falschheit einer bestimmten rein logischen Behauptung ...

-Gandy p. 57, zitiert Behmann

Behmann bemerkt, dass ... das allgemeine Problem dem Problem der Entscheidung entspricht, welche mathematischen Aussagen wahr sind.

-Ebenda.

Wenn man in der Lage wäre, das Inentschen -Problem zu lösen, hätte man ein "Verfahren zur Lösung vieler (oder sogar aller) mathematischen Probleme".

-Ebenda., p. 92

Durch den Internationalen Kongress der Mathematiker von 1928 hat Hilbert "seine Fragen genau gestellt. Erstens war Mathematik Komplett ... Zweitens war Mathematik konsistent ... und drittens war Mathematik entschlossen? "(Hodges S. 91, Hawking S. 1121). Die ersten beiden Fragen wurden 1930 von 1930 beantwortet Kurt Gödel Bei demselben Treffen, bei dem Hilbert seine Altersvorsorge hielt (sehr zum Leidwesen von Hilbert); Der dritte-der Inentscheidungsproblem-hatte bis Mitte der 1930er Jahre zu warten.

Das Problem war, dass eine Antwort zunächst eine genaue Definition von "eindeutig allgemein anwendbares Rezept" erforderte, den Princeton Professor Alonzo -Kirche würde kommen, um anzurufen "Wirksame Berechnbarkeit", und 1928 gab es keine solche Definition. Aber in den nächsten 6 bis 7 Jahren Emil Post entwickelte seine Definition eines Arbeiters, der von Raum zu Raum schriftlich und löscht Markierungen gemäß einer Liste von Anweisungen (Post 1936), ebenso wie Kirche und seine beiden Studenten Stephen Kleene und J. B. Rosser Mithilfe des Lambda-Calculus der Kirche und des Gödel's Rekursionstheorie (1934). Die Zeitung der Kirche (veröffentlicht am 15. April 1936) zeigte, dass das entscheidungsproblem in der Tat "unentscheidbar" war und Turing um fast ein Jahr auf den Punsch schlug (Turings Papier reichte am 28. Mai 1936, veröffentlicht im Januar 1937). In der Zwischenzeit reichte Emil Post im Herbst 1936 ein kurzes Papier ein, so dass Turing zumindest Vorrang vor Post hatte. Während Kirchenschreiber Turings Papier war, hatte Turing Zeit, die Papier der Kirche zu studieren und einen Anhang hinzuzufügen, in dem er einen Beweis skizzierte, den der Lambda-Calculus der Kirche und seine Maschinen dieselben Funktionen berechnen würden.

Aber was die Kirche getan hatte, war etwas etwas anderes und in gewissem Sinne schwächer. ... Die Turing -Konstruktion war direkter und lieferte ein Argument aus den ersten Prinzipien, wodurch die Lücke in der Demonstration der Kirche geschlossen wurde.

-Hodges p. 112

Und Post hatte nur eine Definition von vorgeschlagen Berechnbarkeit und kritisierte die "Definition" der Kirche, hatte aber nichts bewiesen.

Alan Turings A-Maschine

Im Frühjahr 1935 Turing als junger Meisterstudent bei King's College, Cambridge, nahm die Herausforderung an; Er war durch die Vorlesungen des Logikers angeregt worden M. H. A. Newman "Und gelernt von ihnen von Gödels Arbeit und dem entscheidungsproblem ... Newman verwendete das Wort" mechanisch "... in seinem Nachruf von Turing 1955 schreibt Newman:

Zu der Frage "Was ist ein" mechanischer "Prozess?" Turing erwiderte die charakteristische Antwort „etwas, das von einer Maschine erledigt werden kann“ und er stellte die hochtechnische Aufgabe zur Analyse des allgemeinen Begriffs einer Computermaschine ein.

-Gandy, p. 74

Gandy gibt an:

Ich nehme an, aber ich weiß nicht, dass Turing von Beginn seiner Arbeit als sein Ziel ein Beweis für die Unentschlossenheit des Inentscheidungproblems hatte. Er erzählte mir, dass die "Hauptidee" der Zeitung zu ihm kam, als er im Sommer 1935 in Grantchester Meadows lag. und so a diagonales Argument Unlöslichkeit zu beweisen.

-Ebenda., p. 76

Während Gandy glaubte, dass Newmans obige Aussage "irreführend" ist, wird diese Meinung nicht von allen geteilt. Turing hatte ein lebenslanges Interesse an Maschinen: "Alan hatte davon geträumt, als Junge Schreibmaschinen zu erfinden; [seine Mutter] Frau Turing hatte eine Schreibmaschine; und er hätte durchaus beginnen können, indem er sich fragte, was mit einer Schreibmaschine als" mechanische "gemeint war. (Hodges S. 96). Während seiner Zeit in Princeton baute Turing einen boolean-logischen Multiplikator (siehe unten). Seine Doktorarbeit mit dem Titel "Logiksysteme, die auf Ordnern basieren", enthält die folgende Definition von" eine berechnbare Funktion ":

Es wurde oben angegeben, dass "eine Funktion effektiv kalkulierbar ist, wenn ihre Werte durch einen rein mechanischen Prozess gefunden werden können". Wir können diese Aussage buchstäblich annehmen, indem wir durch einen rein mechanischen Prozess verstehen, der von einer Maschine durchgeführt werden kann. Es ist möglich, eine mathematische Beschreibung in einer bestimmten normalen Form der Strukturen dieser Maschinen zu geben. Die Entwicklung dieser Ideen führt zur Definition des Autors für eine berechnungsbare Funktion und zu einer Identifizierung der Berechnung mit effektiver Berechnbarkeit. Es ist nicht schwierig, obwohl etwas mühsam, zu beweisen, dass diese drei Definitionen [der 3. ist der λ-Kalkulus] gleichwertig.

-Turing (1939) in Das unentscheidbare, p. 160

Als Turing nach Großbritannien zurückkehrte, wurde er letztendlich gemeinsam dafür verantwortlich, die deutschen geheimen Codes zu brechen, die von Verschlüsselungsmaschinen genannt "The Rätma" erstellt wurden. Er engagierte sich auch in das Design des Ass (Automatische Computermotor), "[Turings] Ace-Vorschlag wurde effektiv in sich geschlossen, und seine Wurzeln lagen nicht in der Edvac [Die Initiative der USA], aber in seiner eigenen universellen Maschine "(Hodges S. 318). Argumente werden weiterhin über den Ursprung und die Art der von Kleene genannten Art (1952) fortgesetzt. Turings These. Aber was für eine Turing Hat sich bewiesen mit seinem Computer-Maschinen-Modell erscheint in seiner Zeitung "Auf berechnungsbare Zahlen, mit einer Anwendung auf das izschendungproblem"(1937):

[Das] das Hilbert Incdridungsproblem kann keine Lösung haben ... Ich schlage daher vor, zu zeigen, dass es keinen allgemeinen Prozess zur Bestimmung geben kann, ob eine bestimmte Formel U des funktionalen Kalküls k nachweisbar ist, d. H. Dass es keine Maschine geben kann, die. Mit einem U dieser Formeln geliefert, wird Sie schließlich sagen, ob Sie nachweisbar sind.

-aus Turings Papier, wie nachgedruckt in Das unentscheidbare, p. 145

Turings Beispiel (sein zweiter Beweis): Wenn man nach einem allgemeinen Verfahren bittet, um uns mitzuteilen: "Ist diese Maschine jemals gedruckt 0", ist die Frage "unentscheidbar".

1937–1970: Der "digitale Computer", die Geburt von "Informatik"

Als Turing 1937 in Princeton an seiner Doktorarbeit arbeitete, baute Turing einen digitalen (booleschen Logik-) Multiplikator von Grund auf neu, wodurch sein eigenes elektromechanisches Multiplikator gemacht wurde Relais (Hodges S. 138). "Alans Aufgabe war es, das logische Design einer Turing-Maschine in einem Netzwerk von Relais-betriebenen Schalter zu verkörpern ..." (Hodges S. 138). Während Turing vielleicht ursprünglich neugierig war und experimentiert hat, ging es in Deutschland in der gleichen Richtung (in der gleichen RichtungKonrad Zuse (1938) und in den Vereinigten Staaten ((Howard Aiken) und George Stibitz (1937); Die Früchte ihrer Arbeit wurden sowohl von der Achse als auch von den alliierten Militärs in verwendet Zweiter Weltkrieg (vgl. Hodges S. 298–299). Anfang bis Mitte der 1950er Jahre Hao Wang und Marvin Minsky reduzierte die Turing -Maschine auf eine einfachere Form (ein Vorläufer für die Post -Turing -Maschine von Martin Davis); Gleichzeitig reduzierten europäische Forscher die Neufertigen elektronischer Computer zu einem computerähnlichen theoretischen Objekt entspricht dem, was heute als "Turing-Maschine" bezeichnet wurde. In den späten 1950er und frühen 1960er Jahren trugen die zufällig parallelen Entwicklungen von Melzak und Lambek (1961), Minsky (1961) sowie Shepherdson und Sturgis (1961) die europäische Arbeit weiter und reduzierten die Turing-Maschine zu einem freundlicheren Computer. abstraktes Modell namens das Zählermaschine; Elgot und Robinson (1964), Hartmanis (1971), Cook und Reckhow (1973) trugen diese Arbeit noch weiter mit dem Registrieren Sie Maschine und Zufallszugriffsmaschine Modelle-aber im Grunde sind alle nur Multitape-Turing-Maschinen mit einem arithmetischen Anweisungssatz.

1970 - Present: Als Berechnungsmodell

Heute sind die Turing-Maschinen der Turing-Maschine weiterhin die Modelle der Wahl für Theoretiker, die Fragen in der untersuchen Theorie der Berechnung. Im Speziellen, Computerkomplexitätstheorie nutzt die Turing -Maschine:

Abhängig von den Objekten manipuliert man gerne in den Berechnungen (Zahlen wie nichtnegative Ganzzahlen oder alphanumerische Zeichenfolgen), zwei Modelle haben eine dominante Position in der maschinenbasierten Komplexitätstheorie erhalten:

die Offline-Multitape-Turing-Maschine..., das das Standardmodell für String-orientierte Berechnung darstellt und die Random Access Machine (RAM) wie von Cook und Reckhow ... den idealisierten Computer im Neumann-Stil vorgestellt.

-Van Emde Boas 1990: 4

Nur im verwandten Analysebereich der Algorithmen wird diese Rolle vom RAM -Modell übernommen.

-Van Emde Boas 1990: 16

Siehe auch

Anmerkungen

1. ^ Minsky 1967: 107 "In seinem Papier von 1936 definierte A. M. Turing die Klasse der abstrakten Maschinen, die jetzt seinen Namen tragen. Eine Turing-Maschine ist eine Finite-State Store (und später wiederherstellen) Sequenzen von Symbolen, "auch Stone 1972: 8, wo sich das Wort" Maschine "in Anführungszeichen befindet.
2. ^ Stone 1972: 8 Staaten "Diese" Maschine "ist ein abstraktes mathematisches Modell", auch vgl. SIPser 2006: 137ff, das das "Turing Machine -Modell" beschreibt. Rogers 1987 (1967): 13 bezieht sich auf "Turings Charakterisierung", Boolos Burgess und Jeffrey 2002: 25 bezieht sich auf eine "spezifische Art von idealisierter Maschine".
3. ^ SIPser 2006: 137 "Eine Turing -Maschine kann alles tun, was ein echter Computer kann".
4. ^ Vgl. SIPser 2002: 137. Auch Rogers 1987 (1967): 13 beschreibt "ein Papierband mit unendlicher Länge in beide Richtungen". Minsky 1967: 118 Staaten "Das Band wird in beide Richtungen als unendlich angesehen". Boolos Burgess und Jeffrey 2002: 25 enthalten die Möglichkeit, dass "an jedem Ende jemanden stationiert sind, der bei Bedarf besonders leere Quadrate hinzufügt".
5. ^ Vgl. Rogers 1987 (1967): 13. Andere Autoren verwenden das Wort "Quadrat", z. Boolos Burgess Jeffrey 2002: 35, Minsky 1967: 117, Penrose 1989: 37.
6. ^ Boolos Burgess Jeffry 2002: 25 veranschaulichen die Maschine als sich entlang des Bandes. Penrose 1989: 36-37 beschreibt sich selbst als "unangenehm" mit einem unendlichen Klebeband, der beobachtet, dass es "schwer zu verändern sein könnte!"; Er "bevorzugen es, das Band als eine externe Umgebung zu betrachten, durch die sich unser endliches Gerät bewegen kann" und nach der Beobachtung, dass die "Bewegung" eine bequeme Methode ist, um sich Dinge vorzustellen ", und schlägt dann vor, dass" das Gerät alles erhält Die Eingabe aus dieser Umgebung. Einige Variationen des Turing -Maschinenmodells ermöglichen es dem Kopf auch, in derselben Position zu bleiben, anstatt sich zu bewegen oder anzuhalten.
7. ^ Hodges, Andrew (2012). Alan Turing: Das Rätsel (Der hundertjährige Ausgabe). Princeton University Press. ISBN 978-0-691-15564-7.
8. ^ Die Idee kam ihm Mitte 1935 (vielleicht sehen Sie mehr im Geschichtsabschnitt), nachdem eine Frage von gestellt wurde M. H. A. Newman In seinen Vorträgen: "Gab es eine eindeutige Methode oder wie Newman einen" mechanischen Prozess ", der auf eine mathematische Aussage angewendet werden konnte und die die Antwort auf die Frage finden würde, ob es nachweisbar war" (Hodges 1983: 93). Turing reichte seine Zeitung am 31. Mai 1936 bei der London Mathematical Society für ihre London ein Verfahren (vgl. Hodges 1983: 112), es wurde jedoch Anfang 1937 veröffentlicht und Offprints waren im Februar 1937 erhältlich (vgl. Hodges 1983: 129).
9. ^ Siehe Fußnote in Davis 2000: 151.
10. ^ Siehe Anmerkung in den gesammelten Werken der Alonzo Church ( Burge, Tyler; Enderton, Herbert, Hrsg. (2019-04-23). Die gesammelten Werke der Alonzo -Kirche. Cambridge, MA, USA: MIT Press. ISBN 978-0-262-02564-5.)
11. ^ Turing 1936 in Das unentscheidbare 1965: 132-134; Turings Definition von "Rundschreiben" findet sich auf Seite 119.
12. ^ Turing, Alan Mathison (1937). "Auf berechnbare Zahlen mit einer Anwendung auf die Entscheidungsproblem". Verfahren der London Mathematical Society. Serie 2. 42 (1): 230–265. doi:10.1112/PLMS/S2-42.1.230. - Nachdruck bei: Turing, Alan. "Auf berechnungsbaren Zahlen mit einer Anwendung auf das Inentschen -Problem". Das Turing Digital Archiv. Abgerufen 9. Juli 2020.
13. ^ Turing 1936 in Das unentscheidbare 1965: 145
14. ^ SIPser 2006: 137 stellt fest, dass "eine Turing -Maschine alles tun kann, was ein echter Computer kann. Trotzdem kann selbst eine Turing -Maschine bestimmte Probleme nicht lösen. In einem sehr realen Sinne liegen diese Probleme außerhalb der theoretischen Berechnungsgrenzen."
15. ^ Siehe die Definition von "Innings" auf Wiktionär
16. ^ BIN. Turing (Juli 1948). Intelligente Maschinen (Bericht). Nationales physisches Labor. Hier: S.3-4
17. ^ Gelegentlich als eine genannt Aktionstabelle oder Übergangsfunktion.
18. ^ Normalerweise Quintuole [5-Tupel]: q_ia_j→ q_I1a_J1d_k, aber manchmal vervierfacht [4-Tupel].
19. ^ S.149; Insbesondere Hopcroft und Ullman gehen davon aus ${\ displayStyle \ Delta}$ ist in allen Staaten von undefiniert von ${\ displayStyle f}$

Verweise

Primärliteratur, Nachdrucke und Zusammenstellungen

• B. Jack Copeland ed. (2004), Die wesentliche Turing: wegweisende Schriften in Computer, Logik, Philosophie, künstlicher Intelligenz und künstliches Leben sowie die Geheimnisse des Rätsels, Clarendon Press (Oxford University Press), Oxford UK, ISBN0-19-825079-7. Enthält die Turing Papers sowie einen Entwurfsbrief an Emil Post Seine Kritik an "Turings Konvention" und Donald W. Davies ' Korrekturen in Turings Universal Computing Machine
• Martin Davis (Hrsg.) (1965), Das unentscheidbare, Raven Press, Hewlett, NY.
• Emil Post (1936), "Finite -Kombinationsprozesse - Formulierung 1", Zeitschrift für symbolische Logik, 1, 103–105, 1936. Nachgedruckt in Das unentscheidbare, S. 289ff.
• Emil Post (1947), "rekursive Unlöslichkeit eines Problems von Thue", Zeitschrift für symbolische Logik, vol. 12, S. 1–11. Nachgedruckt Das unentscheidbare, S. 293ff. Im Anhang dieses Papiers kommentiert und gibt Korrekturen in Turings Papier von 1936–1937 Korrekturen. Sehen Sie sich insbesondere die Fußnoten 11 mit Korrekturen der Universal Computing Machine Coding und Fußnote 14 mit Kommentaren zu Turings erste und zweite Beweise.
• Turing, A.M. (1936). "Auf berechnungsfähigen Zahlen, mit einer Anwendung auf das Inentschen -Problem". Verfahren der London Mathematical Society. 2 (veröffentlicht 1937). 42: 230–265. doi:10.1112/PLMS/S2-42.1.230. (und Turing, A.M. (1938). "Auf berechnungsfähigen Zahlen mit einer Anwendung auf das Inentschen -Problem: Eine Korrektur". Verfahren der London Mathematical Society. 2 (veröffentlicht 1937). 43 (6): 544–6. doi:10.1112/PLMS/S2-43.6.544.). Nachdruck in vielen Sammlungen, z. in Das unentscheidbare, S. 115–154; an vielen Orten im Internet erhältlich.
• Alan Turing, 1948, "Intelligente Maschinerie". Nachgedruckt in "Cybernetics: Key Papers". Ed. C. R. Evans und A.D.J. Robertson. Baltimore: University Park Press, 1968. p. 31. Nachdruck in Turing, A. M. (1996). "Intelligente Maschinerie, eine ketzerische Theorie". Philosophia mathematica. 4 (3): 256–260. doi:10.1093/philmat/4.3.256.
• F. C. Hennie und R. E. Stearns. Zwei-Tape-Simulation von Multitape-Turing-Maschinen. Jacm, 13 (4): 533–546, 1966.

Computerbarkeitstheorie

• Boolos, George; Richard Jeffrey (1999) [1989]. Berechnbarkeit und Logik (3. Aufl.). Cambridge UK: Cambridge University Press. ISBN 0-521-20402-x.
• Boolos, George; John Burgess; Richard Jeffrey (2002). Berechnbarkeit und Logik (4. Aufl.). Cambridge UK: Cambridge University Press. ISBN 0-521-00758-5. Einige Teile wurden von Burgess erheblich umgeschrieben. Präsentation von Turing -Maschinen im Kontext von Lambek "Abacus -Maschinen" (vgl. Registrieren Sie Maschine) und rekursive Funktionenihre Äquivalenz zeigen.
• Taylor L. Booth (1967), Sequentielle Maschinen und Automatentheorie, John Wiley and Sons, Inc., New York. Graduiertenstufe Engineering Text; Bereiche über eine Vielzahl von Themen, Kapitel IX Turing -Maschinen beinhaltet einige Rekursionstheorie.
• Martin Davis (1958). Berechnbarkeit und Unlösbarkeit. McGraw-Hill Book Company, Inc, New York.. Auf den Seiten 12–20 gibt er Beispiele für 5-Tupel-Tabellen für die Addition, die Nachfolgerfunktion, Subtraktion (x ≥ y), die ordnungsgemäße Subtraktion (0 wenn x <y), die Identitätsfunktion und verschiedene Identitätsfunktionen und Multiplikation an.
• Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Berechnbarkeit, Komplexität, Sprachen und Logik: Grundlagen der theoretischen Informatik (2. Aufl.). San Diego: Akademische Presse, Harcourt, Brace & Company. ISBN 0-12-206382-1.
• Hennie, Fredrick (1977). Einführung in die Berechnung. Addison -Wesley, Reading, Mass. QA248.5H4 1977.. Auf den Seiten 90–103 erläutert Hennie die UTM mit Beispielen und Flusscharts, aber keiner tatsächlicher "Code".
• John Hopcroft und Jeffrey Ullman (1979). Einführung in die Automatentheorie, Sprachen und Berechnung (1. Aufl.). Addison -Wesley, Messe Reading. ISBN 0-201-02988-x. Zentriert auf die Fragen der maschinellen Interpretation von "Sprachen", NP-Completness usw.
• Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Einführung in die Automatentheorie, Sprachen und Berechnung (2. Aufl.). Lesenmasse: Addison -Wesley. ISBN 0-201-44124-1.
• Stephen Kleene (1952), Einführung in Metamathematik, North -Holland Publishing Company, Amsterdam Niederlande, 10. Eindruck (mit Korrekturen des 6. Nachdrucks 1971). Text für Absolventen; Der größte Teil von Kapitel XIII. Berechnungsbare Funktionen ist auf Turing Machine -Beweise für die Berechnung der rekursiven Funktionen usw.
• Knuth, Donald E. (1973). Band 1/Grundalgorithmen: Die Kunst der Computerprogrammierung (2. Aufl.). Reading, Mass.: Addison -Wesley Publishing Company.. In Bezug auf die Rolle von Turing -Maschinen bei der Entwicklung der Berechnung (sowohl Hardware als auch Software) siehe 1.4.5 Geschichte und Bibliographie S. 225ff und 2.6 Geschichte und BibliographieS. 456ff.
• Zohar Manna, 1974, Mathematische Berechnungstheorie. Nachdruck, Dover, 2003. ISBN978-0-486-43238-0
• Marvin Minsky, Berechnung: endliche und unendliche Maschinen, Prentice -Hall, Inc., N. J., 1967. Siehe Kapitel 8, Abschnitt 8.2 "Unlösbarkeit des Stoppproblems".
• Christos Papadimitriou (1993). Rechenkomplexität (1. Aufl.). Addison Wesley. ISBN 0-201-53082-1. Kapitel 2: Turing Machines, S. 19–56.
• Hartley Rogers, Jr., Theorie der rekursiven Funktionen und effektiver Berechnbarkeit, The MIT Press, Cambridge MA, Taschenbuchausgabe 1987, Original McGraw-Hill Edition 1967, ISBN0-262-68052-1 (pbk.)
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-x. Kapitel 3: The Church -Turing Thesis, S. 125–149.
• Stone, Harold S. (1972). Einführung in die Computerorganisation und die Datenstrukturen (1. Aufl.). New York: McGraw -Hill Book Company. ISBN 0-07-061726-0.
• Peter van Emde Boas 1990, Maschinenmodelle und Simulationen, S. 3–66, in Jan van Leeuwen, ed., Handbuch der theoretischen Informatik, Band A: Algorithmen und Komplexität, Der MIT Press/Elsevier, [Ort?], ISBN0-444-88071-2 (Band A). QA76.H279 1990.

These der Kirche

• Nachum Derhowitz; Yuri Gurevich (September 2008). "Eine natürliche Axiomatisierung der Berechnung und des Nachweises der These der Kirche" (PDF). Bulletin der symbolischen Logik. 14 (3). Abgerufen 2008-10-15.
• Roger Penrose (1990) [1989]. Der neue Geist des Kaisers (2. Aufl.). Oxford University Press, New York. ISBN 0-19-851973-7.

Kleine Turing -Maschinen

• Rogozhin, Yurii, 1998, "Eine universelle Turing -Maschine mit 22 Zuständen und 2 Symbolen",", Rumänisches Journal für Informationswissenschaft und Technologie, 1 (3), 259–265, 1998. (Umfragen bekannte Ergebnisse über kleine universelle Turing -Maschinen)
• Stephen Wolfram, 2002, Eine neue Art von Wissenschaft, Wolfram Media, ISBN1-57955-008-8
• Brunfiel, Geoff, Student Snags Maths Prize, Natur, 24. Oktober 2007.
• Jim Giles (2007), Der einfachste 'Universal Computer' gewinnt Studenten 25.000 US -Dollar, Neuer Wissenschaftler, 24. Oktober 2007.
• Alex Smith, Universalität von Wolframs 2, 3 Turing -Maschine, Einreichung für den Wolfram 2, 3 Turing Machine Research Prize.
• Vaughan Pratt, 2007, "Einfache Turing -Maschinen, Universalität, Codierungen usw.", FOM -E -Mail -Liste. 29. Oktober 2007.
• Martin Davis, 2007, "Kleinste universelle Maschine", und Definition der universellen Turing -Maschine FOM -E -Mail -Liste. 26. bis 27. Oktober 2007.
• Alasdair Urquhart, 2007 "Kleinste universelle Maschine", FOM -E -Mail -Liste. 26. Oktober 2007.
• Hector Zenil (Wolfram Research), 2007 "kleinste universelle Maschine", FOM -E -Mail -Liste. 29. Oktober 2007.
• Todd Rowland, 2007, "Verwirrung auf Fom", Wolfram Science Message Board, 30. Oktober 2007.
• Olivier und Marc Raynaud, 2014, Ein programmierbarer Prototyp, um Turing -Maschinen zu erreichen"Limous Laboratory of Blaise Pascal University (Clermont-Frand in Frankreich).

Sonstiges

• Martin Davis (2000). Motoren der Logik: Mathematiker und der Ursprung des Computers (1. Aufl.). W. W. Norton & Company, New York. ISBN 978-0-393-32229-3.
• Robin Gandy, "Der Zusammenfluss der Ideen im Jahr 1936", S. 51–102 in Rolf Herken, siehe unten.
• Stephen Hawking (Herausgeber), 2005, Gott schuf die Ganzzahlen: die mathematischen Durchbrüche, die die Geschichte veränderten, Running Press, Philadelphia, ISBN978-0-7624-1922-7. Enthält Turings Papier von 1936–1937 mit kurzer Kommentare und Biographie von Turing wie von Hawking geschrieben.
• Rolf Herken (1995). Die universelle Turing-Maschine-eine Umfrage des halben Jahrhunderts. Springer Verlag. ISBN 978-3-211-82637-9.
• Andrew Hodges, Alan Turing: Das Rätsel, Simon und Schuster, New York. Vgl. Kapitel "Der Geist der Wahrheit" für eine Geschichte und eine Diskussion über seinen Beweis.
• Ivars Peterson (1988). Der mathematische Tourist: Schnappschüsse moderner Mathematik (1. Aufl.). W. H. Freeman und Company, New York. ISBN 978-0-7167-2064-5.
• Roger Penrose, Der neue Geist des Kaisers: über Computer, Köpfe und die Gesetze der Physik, Oxford University Press, Oxford und New York, 1989 (Korrekturen 1990), ISBN0-19-851973-7.
• Paul Strathern (1997). Turing und der Computer - die große Idee. Ankerbücher/Doubleday. ISBN 978-0-385-49243-0.
• Hao Wang"Eine Variante zu Turings Theorie der Computergeräte", Journal of the Association for Computing Machinery (JACM) 4, 63–92 (1957).
• Charles Petzold, Petzold, Charles, Die kommentierte Turing, John Wiley & Sons, Inc., ISBN0-470-22905-5
• Arora, Sanjeev; Barak, Boaz, "Komplexitätstheorie: Ein moderner Ansatz", Cambridge University Press, 2009, ISBN978-0-521-42426-4, Abschnitt 1.4, "Maschinen als Saiten und die universelle Turing-Maschine" und 1.7, "Proof of Satz 1.9"
• Kantorovitz, Isaiah Pinchas (1. Dezember 2005). "Ein Hinweis zur Berechnung der Berechnungsfähigkeit von regelgesteuerten Systemen von Turing Machine". Sigact News. 36 (4): 109–110. doi:10.1145/1107523.1107525. S2CID 31117713.
• Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: "Über Unentscheidbarkeitsergebnisse realer Programmiersprachen"In 15. Kolloquium -Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Paiserl, Österreich, Oktober 2009.

Externe Links

• "Turing Maschine", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Turing Maschine in dem Stanford Encyclopedia of Philosophy
• Turing Machine Kausalnetzwerke von Enrique Zeleny als Teil der Wolfram Demonstrationsprojekt.
• Turing -Maschinen bei Curlie