What is the basic idea of ​​Turing machine

The basic idea of ​​a Turing machine is to use a machine to simulate the process of people performing mathematical operations with pen and paper. This process can be seen as two simple actions: 1. writing or erasing a certain symbol on the paper; 2. moving attention from one position on the paper to another.

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

Turing machine refers to an abstract machine. It has an infinitely long paper tape. The paper tape 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.

Turing's basic idea is to use machines to simulate the process of people using paper and pen to perform mathematical operations. He regarded such a process as the following two simple actions:

1. Write or erase a certain symbol on the paper;

2. Move your attention from one position on the paper to another.

At each stage, the person has to decide the next action, which depends on (1) the symbol at a certain position on the paper that the person is currently paying attention to and (2) the person's current state of thinking.

In order to simulate this kind of human calculation process, Turing constructed an imaginary machine, which consists of the following parts:

1. An infinitely long paper tape TAPE. The paper tape is divided into small grids one after another, each grid contains a symbol from a limited alphabet, and there is a special symbol in the alphabet to represent white space. The grids on the paper tape are numbered 0, 1, 2,... from left to right, and the right end of the paper tape can be extended infinitely.

2. A read-write head HEAD. The read-write head can move left and right on the paper tape. It can read the symbols on the currently pointed grid and change the symbols on the current grid.

3. A set of control rules TABLE. It determines the next action of the read-write head based on the current state of the machine and the symbol on the grid pointed by the current read-write head, and changes the value of the status register to make the machine enter a new state.

4. A status register. It is used to save the current state of the Turing machine. The number of all possible states of a Turing machine is finite, and there is a special state called the halting state. See shutdown problem.

Note that every part of this machine is finite, but it has a potentially infinite length of paper tape, so this machine is only an ideal device. Turing believed that such a machine could simulate any computational process that humans can perform.

If you want to know more about programming learning, please pay attention to the php training column!

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