Was ist die Grundidee der Turingmaschine?

Die Grundidee einer Turing-Maschine besteht darin, mithilfe einer Maschine den Prozess zu simulieren, bei dem Menschen mathematische Operationen mit Stift und Papier ausführen. Dieser Vorgang kann als zwei einfache Aktionen angesehen werden: 1. Schreiben oder Löschen eines bestimmten Symbols auf dem Papier. 2. Verschieben der Aufmerksamkeit von einer Position auf dem Papier zu einer anderen.

Die Betriebsumgebung dieses Artikels: Windows 7-System, Dell G3-Computer.

Turingmaschine bezeichnet eine abstrakte Maschine. Sie hat ein unendlich langes Papierband, das in kleine Quadrate unterteilt ist, jedes Quadrat hat eine andere Farbe. 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.

Turings Grundidee besteht darin, mithilfe von Maschinen den Prozess zu simulieren, bei dem Menschen Papier und Stift verwenden, um mathematische Operationen durchzuführen:

1 Ein bestimmtes Symbol auf Papier schreiben oder löschen ;

2. Lenken Sie Ihre Aufmerksamkeit von einer Position auf dem Papier zur anderen.

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 Denkzustand der Person abhängt.

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 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 markierten 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 einfach ein ideales Gerät ist. Turing glaubte, dass eine solche Maschine jeden Rechenprozess simulieren könnte, den Menschen ausführen können.

Wenn Sie mehr über das Erlernen des Programmierens erfahren möchten, achten Sie bitte auf die Spalte „PHP-Schulung“!

Das obige ist der detaillierte Inhalt vonWas ist die Grundidee der Turingmaschine?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!