WikiDer > Turingmaschine

In dem Informatik ist der Turing Maschine ein Rechenmodell und Berechenbarkeit, entwickelt von der MathematikerAlan M. Turing in seinem berühmten Artikel "On berechenbare Zahlen, mit einer Anwendung auf das Entscheidungsproblem" von 1936-37.

Die Turingmaschine ist ein extrem einfacher Mechanismus, der Symbole manipuliert und trotz dieser Einfachheit kann man die Logik aller möglichen verwenden Computer simulieren. Obwohl technisch machbar (solange wir beliebige Bandmengen liefern können), sind diese Maschinen nicht für die praktische Computertechnik gedacht, sondern als Gedankenexperiment an den Grenzen mechanischer Berechnungen; Sie sind also nicht wirklich gebaut.

Der Turing-Mechanismus

Die Turingmaschine ist im Grunde ein sehr einfaches Gerät, das nicht mehr kann, als zwei verschiedene Werte in einem Schritt einzustellen. Dieser Mechanismus ist wahrscheinlich in der Lage, jede beschreibbare Berechnung durchzuführen.

Das Konzept

Eine Turingmaschine besteht aus zwei Teilen:

1. Ein halb-unendliches Band (mit einem Anfang, aber von unendlicher Länge, also ohne Ende), unterteilt in unendlich viele Zellen. Es wurde jedoch immer nur ein endlicher Teil dieses Bandes beschrieben.
2. Ein Gerät mit einem Schreib-/Lesekopf (a endliche Automaten genannt), die das Band lesen und beschreiben kann.

Die Turing-Maschine

Der aktive Teil der Maschine ist die endliche Zustandsmaschine. Diese Maschine befindet sich immer in einem bestimmten Zustand. Dieser Zustand ist einer von endlichen Sammlung von Zuständen und der Automat kann nach bestimmten Regeln von einem Zustand zum nächsten übergehen.

Die Zustandsmaschine wiederholt (möglicherweise unendlich oft) den folgenden Zyklus:

1. (in einem Zustand P): Lesen Sie, was sich auf dem Band befindet, wo sich jetzt der Schreib-/Lesekopf befindet – nennen Sie dieses Bandzeichen K.
2. (noch im Zustand P): Schlagen Sie die Kombination (Q, K', D) für die Kombination (P, K) in der Liste der Zustandsübergänge nach.
3. (noch im Zustand P): Schreiben Sie K' auf das Band anstelle von K; bewegen Sie den Schreib-/Lesekopf eine Position in Richtung D (links oder rechts); gehe zu Zustand Q.
4. (im Zustand Q):

Wenn Q ein akzeptierender Zustand ist, ist die Berechnung abgeschlossen und Sie sind gut – dann hören Sie auf;

Wenn Q ein negativer Zustand ist, können die Berechnungen nicht fortgesetzt werden und es ist falsch -- stop;

Q nimmt weder an noch lehnt sie ab – fang wieder vorne an.

Eine Berechnung durch eine Turingmaschine beginnt immer in einem speziell bezeichneten Zustand (dem Anfangszustand) mit dem Lesekopf am Bandanfang.

Als Rechenbeispiel zeigen wir die Addition zweier Zahlen. Diese Nummern sind von Anfang an (links) auf dem Band. Jede Zahl besteht aus einer Reihe von Zeichen '1' (z. B. ist 3 '111'). Die beiden separaten Zahlen werden durch ein '0'-Zeichen getrennt. Es gibt nichts anderes auf dem Band ('Leerzeichen'). Wir starten in einem Anfangszustand Qb. Ein Programm zum Addieren dieser Zahlen sieht so aus:

Wiederholen Sie dies, bis wir uns im akzeptierenden oder ablehnenden Zustand befinden:

1. Lesen Sie anstelle der Überschrift den Charakter der Band.
2. Ist der Zustand Qb:
   - Wenn dieses Zeichen eine '0' oder '1' ist, schreibe stattdessen eine '1', bewege den Kopf nach rechts und bleibe im Zustand Qb.
   - Wenn dieses Zeichen 'leer' ist, schreiben Sie stattdessen ein 'leeres' Zeichen, verschieben Sie die Überschrift nach links und gehen Sie zum Zustand Q0.
   Ist die Bedingung Q0:
   - Wenn dieses Zeichen eine '1' ist, schreiben Sie stattdessen ein 'leeres' Zeichen, verschieben Sie die Überschrift nach links und gehen Sie in den akzeptierenden Zustand.
   - Wenn dieses Zeichen eine '0' oder 'leer' ist, schreiben Sie stattdessen ein 'leeres' Zeichen und gehen Sie in den Ablehnungszustand.

Wie unten gezeigt, ist dies eine korrekte Ergänzung.

2 3 = 5

Der Formalismus

Formal ist eine Turingmaschine TM a Tupel von 7 Elementen:

TM = (${displaystyle {mathcal {Q}}}$, ${Anzeigestil Sigma }$, ${Anzeigestil Gamma }$, ${Anzeigestil-Delta}$, ${displaystyle q_{0}}$, ${displaystyle q_{a}}$, ${displaystyle q_{r}}$) mit

1. ${displaystyle {mathcal {Q}}}$ ein Sammlung Zustände
2. ${Anzeigestil Sigma }$ ein Sammlung Zeichen, zusammen es Eingabealphabet -- die Eingabe für die Berechnung besteht aus diesen Zeichen
3. ${displaystyle Gamma = Sigma Tasse {/_}}$ es Band-Alphabet, alle auf dem Band erlaubten Zeichen – dies ist das Eingabealphabet plus das spezielle Leerzeichen
4. ${displaystyle delta :{mathcal {Q}}imes Gamma Mapto {mathcal {Q}}imes Gamma imes {L,R}}$, die Übergangsfunktion, die die Zustandsübergänge, Schreibvorgänge und Kopfbewegungen des endlichen Automaten beschreibt
5. ${displaystyle q_{0}in {mathcal {Q}}}$, der Anfangszustand
6. ${displaystyle q_{a}in {mathcal {Q}}}$, der akzeptierende Staat
7. ${displaystyle q_{r}in {mathcal {Q}}}$, der ablehnende Staat

Dieses Tupel fasst den gesamten Automaten zusammen. Die oben beschriebenen Bewegungen des endlichen Automaten sind in der Übergangsfunktion${Anzeigestil-Delta}$.

Diese Maschine (die Grundmaschine TM) ist die einfachste TM-Variante, die es gibt. Das Band ist Standard, einseitig unendlich (aus der Kopfposition läuft das Band nur in eine Richtung unendlich weiter) und es ist deterministisch: für jedes Paar (Zustand, Bandsymbol) erlaubt der Übergang nur ein Tripel als Reaktion auf den Automaten. Existiert dieses Tripel nicht, bleibt die Maschine hängen und die Berechnung ist fehlgeschlagen (alternativ kann es auch zwingend sein, jedes mögliche Paar in die Beschreibung aufzunehmen, wobei die "falschen" Paare alle einen Zustandsübergang in den ablehnenden Zustand verursachen).

Beachten Sie, dass die Beschreibung keine Informationen über die Startposition der Überschrift enthält: Standardmäßig wird der Anfang verwendet.

Als Beispiel geben wir die Formalisierung unseres "zusätzlichen Automaten" von oben. Diese Maschine ist

${displaystyle TM_{ }=}$

(${displaystyle {mathcal {Q}}={q_{b},q_{0},q_{a},q_{r}}}$,

${Displaystil Sigma ={'0','1'}}$,

${displaystyle Gamma = Sigma Tasse {/_}}$,

${displaystyle delta ={ egin{matrix}(q_{b},'1')mapto (q_{b},'1',R)/(q_{b},'0')mapto (q_{b}, '1',R)/(q_{b},'/_')mapto (q_{0},'/_',L)/(q_{0},'1')mapto (q_{a}, '/_',L)/(q_{0},'0')mapto (q_{r},'/_',L)/(q_{0},'/_')mapto (q_{r} ,'/_',L)end{array}}}$

${displaystyle q_{b}}$,

${displaystyle q_{a}}$,

${displaystyle q_{r}}$)

Beachten Sie, dass wir nichts darüber sagen, was auf dem Band sein soll oder wie oder was dies bedeutet (das wird die Maschine sowieso nicht verstehen). Für die Berechnung kommt es lediglich darauf an, dass die Maschine in einer bestimmten Weise auf die Eingabe reagiert, sofern die Eingabe aus dem Eingabealphabet besteht.

Bedeutung der Turingmaschine

Seit der Einführung der Turing-Maschine im Jahr 1936 besteht der Verdacht (unbeweisbar), dass die Turing-Maschine ein perfektes Modell von . ist Berechenbarkeit ist. Das heißt, alles, was mechanisch berechnet werden kann, kann von einer Turing-Maschine berechnet werden – und was von einer Turing-Maschine nicht berechnet werden kann, ist mechanisch nicht berechenbar.

Mechanisch berechenbar ist normalerweise algorithmisch berechenbar erwähnt. Ein Problem P ist algorithmisch berechenbar, wenn es a Algorithmus, ein Schritt-für-Schritt-Plan, der das Problem löst. Wenn es eine Turingmaschine gibt, die ein Problem löst, dann existiert ein solcher Algorithmus. Und umgekehrt.

Was bedeutet es, wenn eine Turingmaschine ein Problem löst? Ein Problem P wird durch eine Turingmaschine gelöst, wenn es eine Turingmaschine TM mit P beschlossen: Für jede Instanz von P (jede Eingabe, die ein Beispiel für Problem P ist) endet das TM im akzeptierenden oder verweigernden Zustand. Eine solche Turingmaschine TM heißt a Entscheidungsträger für Problem p.

Außerdem kennen wir auch den Begriff a Erkenner für P. Dies ist eine Turingmaschine, die zwar nicht bei jeder Instanz von P abstürzt, aber auch für diese Instanz nicht den akzeptierenden oder ablehnenden Zustand erreichen muss. Ein Erkenner kann daher auch eine unendlich lange Berechnung durchführen. Wir nennen dies im Allgemeinen keine Lösung von P.

Die Existenz der Turing-Maschine als Modell bedeutet, dass Mathematiker darüber nachdenken können, was berechnet werden kann und was nicht und wie schwierig Klassen von Problemen zu lösen sind (dies wird als Komplexität eines Problems).

Seit 1936 ist bewiesen, dass es Probleme gibt, die Turing nicht lösbar sind (dafür kann es keinen Entscheidungsträger geben). Ein Beispiel ist es Halteproblem oder Stoppproblem. Es ist auch bewiesen, dass es Probleme gibt, die nicht erkennbar sind (dafür kann es keinen Erkenner geben).

Beachten Sie übrigens, dass nur weil ein Problem nicht Turing-lösbar ist, nicht bedeutet, dass Instanzen dieses Problems keine Lösungen haben. Es bedeutet, dass es keine Turingmaschine gibt, die alle Fälle des Problems lösen kann.

Varianten der Grundmaschine und ihre Ausdruckskraft

Seit 1936 haben Forscher viele verschiedene Varianten des Turing-Modells der Berechenbarkeit untersucht und was ihre Anpassungen für die Entscheidungskraft der neuen Maschinen bedeuteten.

Bei den meisten Varianten ändert sich die Entscheidungskraft nicht, da diese Varianten auf einer "normalen" Turingmaschine simuliert werden können. Beispiele sind Multiband- (und Kopf-) Turing-Maschinen, Single-Band- (und Mehrkopf-) Turing-Maschinen (die parallelen Maschinen, die simuliert werden können, indem jedes Band zu einem eigenen Abschnitt des Bandes auf einer "normalen" Maschine bewegt wird) , Maschinen mit mehrseitigen Endlosbändern (stellen Sie den Eingang in die Mitte des "normalen" Bandes und lassen Sie die Turingmaschine das Band zum Eingang vorspulen) und mehr von diesen Änderungen.

Eine nicht leistungsstärkere, aber besonders wirkungsmächtige Variante ist die nichtdeterministische Turingmaschine (die Funktion ${Anzeigestil-Delta}$ dann verbinde jedes Paar (Zustand, Vorzeichen) mit einem oder mehr Tripel (Zustand, Vorzeichen, Richtung). Diese nicht-deterministische Maschine (NDTM) kann durch Drücken der "normalen" Turing-Maschine simuliert werden alles möglich Parallele NDTM-Berechnungen. Wenn eine der möglichen Berechnungen von NDTM in einem akzeptierenden Zustand endet, trifft die "normale" Maschine darauf. Dies macht die "normale" Maschine extrem langsamer als die NDTM: Eine TM, die einer NDTM entspricht, hat für die gleiche Eingabe wie diese NDTM, bestehend aus n Zeichen, ${Displaystil 2^{2^{n}}}$ so viele Schritte wie die NDTM benötigt, um die Berechnung durchzuführen.

Eine weitere Variante der Turing-Maschine ist der Enumerator: Dies ist eine Turing-Maschine mit einem "Drucker", der als "Beweis" der Berechnung Ausgabestrings erzeugen kann.

Eine andere Variante ist die mit endlicher Bindung. Das ist kaum noch eine Turing-Maschine: Eine solche Maschine entspricht völlig einem Standard endliche Automaten.

Schließlich ist die Variante erwähnenswert, bei der die Maschine zwar unendlich ist, die Maschine aber nur das Stück verwenden darf, auf dem die Eingabe geschrieben wurde. Dieses Gerät beschreibt eine Klasse von Problemen und formale Sprachen bekannt als kontextsensitive Sprachen.

Die Turingmaschine und der Von-Neumann-Zyklus

Die Turing-Maschine beeinflusste direkt die Entwicklung des Computer und der Informatik.

Zu Beginn war das Turing-Modell eine Inspiration für die MathematikerJohn von Neumann, der nach einer Möglichkeit suchte, den ersten zu machen Computers nutzbar zu machen. Als Ergebnis von Turings Maschine entwickelte er die Von Neumann-Zyklus, ein Zyklus von Operationen, der es einem elektronischen Gerät ermöglicht, genau das zu tun, was eine Turing-Maschine tut.

Darüber hinaus ist die Turing-Maschine der Beginn einer Zweigniederlassung von Mathematik und Informatik das aus formalen Spezifikationen eines Problems ein Programm ableitet, das das Problem löst. Diese Lösungsstrategie (entwickelt von Tony Hoare, Edsger Dijkstraße und andere) verwendet Prädikatsrechnung die Schritte zu berechnen, die erforderlich sind, um einen Turing-Automaten von einem Zustand in den nächsten zu bringen (aber nicht direkt die Schritte zu berechnen, die vom Anfangszustand zum akzeptierenden Zustand führen – dieses Problem ist nicht durch Turing lösbar).

Siehe auch

• Turing-Vollständigkeit