What Is a Turing Machine?

The so-called Turing machine refers to an abstract machine, which has an infinitely long paper strip, which is divided into small squares one by one, each square has a different color. There is a machine head moving around on the tape. The machine head has a set of internal states and some fixed programs. At each moment, the machine head must read a square of information from the current paper tape, and then look up the program table in conjunction with its internal status, output the information to the paper tape square according to the program, and change its internal status, and Make a move. ^[1]

In 1936, the British mathematician Alan Mathieson Turing (1912--1954) proposed an abstract computing model, the Turing machine. Turing machine, also known as Turing computer, abstracts the process of mathematical operations using paper and pen, and replaces humans with virtual machines for mathematical operations. ^[2]

A Turing machine is a seven-tuple, {Q, , , , q0, qaccept, qreject}, where Q, , are all

For any Turing machine, because its description is limited, we can always encode it into a string in some way. We use <M> to represent the code of Turing machine M. ^[3]

The halting problem is the focus of current logical mathematics and the solution to the third mathematical crisis. The essential question is: given a Turing machine D and an arbitrary language set S, will D eventually stop at each s S. Its meaning is similar to deterministic language. Obviously, any finite S is determinable, and countable S can be stopped. ^[4]

There are many variants of Turing machines, but it can be proven that the computing power of these variants is equivalent, that is, they recognize the same language class. The basic idea to prove that the computing power of the two computing models A and B is equivalent is to use A and B to simulate each other. If A can simulate B and B can simulate A, their computing power is equivalent. Note that we do not consider the efficiency of the calculation for now, but only the theoretical "feasibility" of the calculation. ^[4]

Turing proposed the Turing machine model not to give the design of the computer at the same time, and its significance has the following points: ^[2]

(1) It proves the general computing theory, affirms the possibility of computer implementation, and it gives the main architecture that a computer should have; ^[2]

(2) Turing machine model introduces the concepts of reading, writing, algorithms and programming languages, which greatly breaks through the past computer design concepts; ^[2]

(3) Turing machine model theory is the core theory of the computing discipline, because the ultimate computing power of computers is the computing power of general Turing machines, and many problems can be transformed into a simple model of Turing machines to consider. ^[2]

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