Is a Turing machine a computer?

Is a Turing machine a computer?

Turing machine is not a computer, Turing machine is just a theoretical computing model.

The so-called 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.

In 1936, British mathematician Alan Turing (1912-1954) proposed an abstract computing model-Turing 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.

Basic idea

Turing’s basic idea is to use machines to simulate the process of people using paper and pen to perform mathematical operations. He regards such processes as the following two types 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 human computing 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.

In some models, the read/write head moves along a fixed paper tape. The command to be performed (q1) is displayed in the read/write head. The "blank" tape in this model is all zeros. The shaded squares, including the blanks scanned by the read-write head, those squares marked 1, 1, B, and the read-write head symbol, constitute the system state. (Drawing by Minsky (1967) p.121).

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