How many symbols in the alphabet should be considered in Turing calculation model?

With paper and pen, you have mastered the multiplication table and carry method, and actually calculated 328*975 with pen. You don't need to think more, you just need to use a pen to operate mechanically on paper, which is a feature of mathematics. Another example is the solution of a simple one-dimensional linear equation. The process can be solidified into five steps: removing 1 denominator according to the nature of the equation, removing two brackets according to the multiplication and distribution law, shifting three terms according to the nature of the equation, merging four similar terms according to the multiplication and distribution law, and converting five coefficients into 1. The operation of machinery is determined by the form, and appropriate symbols make the form clearer and easier to understand.

In 1930s, alan mathison turing (1912.6-1954.6), a British mathematician, made a detailed investigation on the process of people's calculation with pen on paper, and put forward the concept of turing machine. Turing machine is an abstract computer model, and its basic principle is not complicated.

The mechanical part of Turing machine includes:

Paper tape input consists of 1 (used for input and output, keyword: infinite length):

Think of it as an infinite paper tape, which is divided into cells, and each cell records a character A in a character table.

2 read/write heads

The read-write head can move left and right on the paper tape, and its function is:

Read the characters in the current cell,

Erases the characters in the current cell.

Writes a character to the current cell.

The read-write head can only operate on one unit at any time.

The controller in the figure can be decomposed into the following logical components:

Three letters.

The alphabet includes characters that can be input into the paper tape box and characters that can be written into the box by the read-write head. For example, the character sets are {" 1 ","0 ","+",=" and ︺}.

4 state set

Turing machine is in any state at any moment, and all states form a state set {s0, s 1, s2, s3, s4, s5}, which includes

Starting State s0: This state is always present at the beginning of every operation.

Shutdown state s5: Turing machine enters this state, and the machine stops running. In this state, the characters left by the paper tape are the calculation results.

5 control rules

The read-write head reads the characters of the current unit, and combined with the current machine state, it can decide:

One: the new state of Turing machine

Two: Turing machine response operation

Erase: Erases the contents of the current cell.

Write: writes a character in the character set to the current cell.

Move: left or right

The operation of turing machine can be abstracted as: ((current state, current reading)->; (new status, current writing, moving direction)). Let's construct a simple example, which is the addition of binary bits. Design seven states:,

S0: initial state

S 1: appendix = 1

S2: Addendum =0

S3: Addendum, Addendum = 1

S4: Appendix and addend are inconsistent.

S5: Appendix, Appendix =0

S6: Shutdown state

The character list is {" 1 ","0 "and"+"}.

The erase operation means clearing the cell contents.

The rules that can be formulated are as follows:

This is a simple example. But the examples we can see are too simple, but people don't understand what Turing machine can do. The actual computer you see dealing with complex problems, such as the simulation of the evolution of the universe, weather forecast, etc. Applying the same principle, the difference lies in the order of magnitude of character set, state set and control rules. Turing machine is also powerful because it can construct a universal Turing machine: Turing machines that can simulate other Turing machines. A Turing machine to solve a specific problem, its character set, state set and control rules are always limited, so it has all ((current state, current reading)->; (new state, current writing, moving direction)) can be encoded as a specific input on the paper tape of another Turing machine in a certain way, and at the same time, its running state and position are maintained in a specific cell during simulation, so that the latter Turing machine can run according to the algorithm of the previous Turing machine through reading control. The concept of universal turing machine is the idea of "storable program computer" later. At present, the smallest known universal Turing machine is the Turing machine with 2 characters in the character list and 3 states in the state set, which is simpler than the above example. Theoretically, the capabilities of all computers today can't exceed the smallest universal Turing machine, and the difference is only in efficiency.

The topic of the paper that puts forward Turing machine idea is "On the Application of Digital Computing in Decision-making Problems". Turing's first problem to solve is the computability of numbers, such as pi, whether it can be calculated to any digit. The immediate background of the problem is Hilbert's tenth problem. At the beginning of the new century from 65438 to 0900, the German mathematician Hilbert gave a famous speech on "Mathematical Problems" at the Second International Congress of Mathematicians, and put forward the most difficult problems in 23 mathematical theories. Later, the progress of mathematics in this century is closely related to the solution of these 23 problems. The 10 question is also called the decision question. The original topic is: given a Diophantine equation, all rational numbers and any unknown numbers of the equation, design a process, and determine whether the equation is solvable in rational numbers through finite calculations. The general form of the problem is: Is there a way to determine whether any definable mathematical problem is solvable? It is a strategy to study the computability of numbers, which is a problem with simpler technical details, and Turing proved that this problem is equivalent to a logically determinable problem.

According to Turing's research, the computability of a mathematical problem is equal to the computability of Turing machine of this problem. The countable number is infinitely countable, and the uncountable number is infinitely uncountable. According to modern set theory, the order of the latter is higher than the former. Hilbert's judgment problem can be reduced to whether a general Turing machine can stop another Turing machine without actual simulation. Turing's answer is no, so Hilbert's judgment problem has no solution, which also shows the limitations of Turing machine. A few months before Turing finished his thesis, the American mathematician alonzo Church (alonzo church:1903.6–1995.8) submitted the paper "Explanation on Deterministic Problems", which also proved that there is no solution to deterministic problems. Qiu Qi's method is based on recursive function and λ operation.

Although the basic principle of Turing machine is simple, the problems behind it are profound enough, and many discussions have continued to this day and will continue. These discussions can be summed up in three basic questions: Is the human brain a Turing machine? Is the universe a Turing machine? Can we design a machine that goes beyond the general Turing machine without violating the laws of physics?

Judging from the theme of this book, Turing machine began with describing the calculation process of people using pens on paper. The reading and writing head of Turing machine is equivalent to human eyes and hands. Paper tape input is a problem to be solved. According to the input and the current state, a new state is generated, and applicable rules are matched for writing and moving operations, which is consistent with people's decision-making and operation when calculating on paper with a pen. The atomic operation of Turing machine is: reading a character, deleting a character and writing a character. Writing when a cell has characters can be regarded as modification. In the application of human symbols, the same is true of atomic operation at the physical level of media. There may be some differences, such as deleting is not necessarily clearing, but marking it as invalid, and writing the correct symbol in the next position after modifying it as invalid. This difference has no substantive significance.

Turing machine makes a generalized abstraction of calculation: generalized calculation is a symbolic mechanical operation based on rules. Under this definition, as long as there are certain rules, Turing machine can calculate. This is beyond the concept of calculation in mathematics. In fact, the application of modern computer is not mainly the solution of mathematical expressions, and the symbols of operation are not limited to digital symbols. What other forms of calculation are there? Where did they come from? Turing's theory is not described. Today, it is an open application by default, which is very popular and successful enough. Combining the three problems of Turing machine extension, although calculation originated from mathematics, we can see the trend today that the concept of calculation can be independent of mathematics, and conversely, mathematics can also be regarded as an independent paradigm or a philosophy. What has not changed is that this is still an operation on symbols.