Ist eine Turingmaschine ein Computer?

Ist eine Turingmaschine ein Computer?

Turingmaschine ist kein Computer, Turingmaschine ist nur ein theoretisches Rechenmodell.

Die sogenannte Turing-Maschine bezeichnet eine abstrakte Maschine. Sie verfügt über ein unendlich langes Papierband, das in kleine Quadrate unterteilt ist, wobei jedes Quadrat eine andere Farbe hat. Es gibt einen Maschinenkopf, der sich auf dem Papierband bewegt. Der Maschinenkopf verfügt über eine Reihe interner Zustände sowie einige feste Prozeduren. Zu jedem Zeitpunkt muss der Maschinenkopf ein Informationsquadrat vom aktuellen Papierband lesen, dann die Programmtabelle basierend auf seinem eigenen internen Status durchsuchen, die Informationen entsprechend dem Programm an das Papierbandquadrat ausgeben und seinen eigenen internen Status konvertieren , und dann Einen Zug machen.

Im Jahr 1936 schlug der britische Mathematiker Alan Matheson Turing (1912-1954) ein abstraktes Rechenmodell vor – eine Turingmaschine. Die Turing-Maschine, auch bekannt als Turing-Computer, abstrahiert den Prozess, bei dem Menschen Papier und Stift zur Durchführung mathematischer Operationen verwenden, und ersetzt den Menschen durch eine virtuelle Maschine zur Durchführung mathematischer Operationen.

Grundidee

Turings Grundidee besteht darin, mithilfe von Maschinen den Prozess zu simulieren, bei dem Menschen Papier und Stift zur Durchführung mathematischer Operationen verwenden. Er betrachtete solche Prozesse als die folgenden beiden Einfache Aktionen:

1. Schreiben oder löschen Sie ein bestimmtes Symbol auf dem Papier

2.

In jeder Phase muss die Person über die nächste Aktion entscheiden, die von (1) dem Symbol an einer bestimmten Position auf dem Papier, auf das die Person gerade achtet, und (2) dem aktuellen Zustand der Person abhängt des Denkens.

Um diesen menschlichen Rechenvorgang zu simulieren, konstruierte Turing eine imaginäre Maschine, die aus folgenden Teilen besteht:

1. Ein unendlich langes Papierband. Das Papierband ist nacheinander in kleine Gitter unterteilt, jedes Gitter enthält ein Symbol aus einem begrenzten Alphabet und es gibt ein spezielles Symbol im Alphabet, das den Leerraum darstellt. Die Raster auf dem Papierband sind von links nach rechts mit 0, 1, 2, ... nummeriert, und das rechte Ende des Papierbandes kann unendlich verlängert werden.

2. Ein Lese-/Schreibkopf HEAD. Der Lese-/Schreibkopf kann sich auf dem Papierband nach links und rechts bewegen. Er kann die Symbole auf dem aktuell gezeigten Raster lesen und die Symbole auf dem aktuellen Raster ändern.

3. Eine Reihe von Kontrollregeln TABELLE. Es bestimmt die nächste Aktion des Lese-/Schreibkopfes basierend auf dem aktuellen Zustand der Maschine und dem Symbol auf dem Raster, auf das der aktuelle Lese-/Schreibkopf zeigt, und ändert den Wert des Statusregisters, um die Maschine in einen neuen Zustand zu versetzen .

4. Ein Statusregister. Es wird verwendet, um den aktuellen Zustand der Turing-Maschine zu speichern. Die Anzahl aller möglichen Zustände einer Turing-Maschine ist endlich, und es gibt einen besonderen Zustand, den sogenannten Haltezustand. Siehe Shutdown-Problem.

Beachten Sie, dass jeder Teil dieser Maschine endlich ist, das Papierband jedoch potenziell unendlich lang ist, sodass diese Maschine nur ein ideales Gerät ist. Turing glaubte, dass eine solche Maschine jeden Rechenprozess simulieren könnte, den Menschen ausführen können.

Bei einigen Modellen bewegt sich der Lese-/Schreibkopf entlang eines festen Papierbandes. Der auszuführende Befehl (q1) wird im Schreib-/Lesekopf angezeigt. Das „leere“ Band in diesem Modell besteht ausschließlich aus Nullen. Die schattierten Quadrate, einschließlich der vom Schreib-Lese-Kopf gescannten Leerzeichen, der mit 1, 1, B gekennzeichneten Quadrate und dem Schreib-Lese-Kopf-Symbol, bilden den Systemzustand. (Zeichnung von Minsky (1967) S.121).

Das obige ist der detaillierte Inhalt vonIst eine Turingmaschine ein Computer?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!