What kind of machine is a Turing machine?

Turing machine is an abstract machine and an abstract computing model. The Turing machine proved the universal computing theory and affirmed the possibility of computer implementation. At the same time, it gave the main architecture that a computer should have. However, the "Turing machine" is just an imaginary "computer" and does not consider the hardware status at all. The focus of consideration is logical structure.

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

Turing machine is an abstract machine and an abstract computing model. It has an infinitely long paper tape, which is divided into small squares, each square has a different color. There is a machine head that moves around on the paper tape. The machine head has a set of internal states, as well as some fixed procedures. At each moment, the machine head must read a square of information from the current paper tape, then search the program table based on its own internal state, output the information to the paper tape square according to the program, and convert its own internal state, and then Make a move.

In 1936, British mathematician Alan Matheson Turing (1912-1954) proposed an abstract computing model-Turing machine (Turing machine) machine). Turing machine, also known as Turing computer, abstracts the process of people using paper and pencil to perform mathematical operations, and replaces humans with mathematical operations by a virtual machine.

The universal Turing machine shows people such a process: the program and its input can be saved on the storage tape first, and the Turing machine runs the program step by step until the result is given, and the result is also saved on the storage tape. More importantly, the main components of modern computers can be vaguely seen, especially the main components of von Neumann's theory.

The Turing machine proved the universal computing theory and affirmed the possibility of computer implementation. At the same time, it gave the main architecture that a computer should have. However, the "Turing machine" is just an imaginary "computer" and does not consider the hardware at all. State, the focus of consideration is the logical structure, while the computer already has entities.

The significance of Turing machine

Turing proposed the model of Turing machine not to give the design of the computer at the same time. Its significance is as follows:

(1) It proves the universal computing theory and affirms the possibility of computer implementation. At the same time, it gives the main architecture that a computer should have;

(2) The Turing machine model introduces reading and writing and The concepts of algorithms and programming languages ​​have greatly broken through the design concepts of computing machines in the past;

(3) The Turing machine model theory is the core theory of the computing discipline, because the ultimate computing power of computers is the universal graph Due to the computing power of a Turing machine, many problems can be considered by transforming it into a simple model called a Turing machine.

The universal Turing machine shows people such a process: the program and its input can be saved on the storage tape first, and the Turing machine runs the program step by step until the result is given, and the result is also saved on the storage tape. More importantly, the main components of modern computers can be vaguely seen, especially the main components of von Neumann's theory.

Recommended free video tutorials: "Programming Video"

The above is the detailed content of What kind of machine is a Turing machine?. For more information, please follow other related articles on the PHP Chinese website!