Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what is a definite Turing machine and an indeterminate Turing machine". In daily operation, I believe that many people have doubts about what is a definite Turing machine and an indeterminate Turing machine. The editor consulted all kinds of data and sorted out a simple and easy-to-use operation method. I hope it will be helpful to answer the doubts about "what is a definite Turing machine and an indeterminate Turing machine". Next, please follow the editor to study!

Turing machine

The Turing machine is a mathematical computing model that defines an abstract machine that manipulates the symbols on the tape according to the rule table. Although the model is simple, a Turing machine that simulates the logic of the algorithm can be built in any given computer algorithm.

To put it simply, a Turing machine is an abstract machine that simulates the operation of algorithms. It is defined as follows:

There is an infinite length of tape, which is divided into one cell after another, and the tape is used to write letters and symbols.

A magnetic head for reading and writing magnetic tape, which is responsible for controlling the writing and left-to-right movement of the heap tape.

A status register that stores the state of the Turing machine.

A list of instructions that instructs the machine to perform specific operations according to the current state of the machine and the current symbols on the tape. For example, erase or write a symbol, move the head to the left or right.

You can see that the whole Turing machine basically simulates the execution steps of the program.

Although the Turing machine can represent any calculation program, but because its extremely simple design is actually not suitable for calculation, the modern computers in the real world are the optimal design of the Turing machine.

Turing completeness refers to the ability of an instruction system to simulate a Turing machine. In theory, Turing's complete programming language can express all the tasks that a computer can accomplish. If you ignore the limited memory limitations, almost all programming languages are Turing complete.

The shortcomings of Turing machine

Although Turing machines can represent any computing task, Turing machines are too simple to be used well in some complex models. For example, in the RASP random storage model in modern computers, because RASP can reference other registers in registers, it can be optimized based on memory index, which can not be realized in Turing machines.

Another limitation of Turing machines is that they are not good at concurrency modeling. In addition, because in the early days, the use of computers was usually limited to batch processing, that is, non-interactive tasks, each task generated output data from a given input data. Therefore, the Turing machine also has some limitations in describing modern interactive applications.

Equivalent Turing machine

Because the Turing machine is a hypothetical device, it provides a theoretical basis for the concept of computer algorithms. And because the Turing machine model is relatively simple, the description of complex problems is relatively weak, so there are many Turing machine equivalent models, although these models are not necessarily more powerful than Turing machine, but these models really exist, and they can be used to solve specific problems more easily.

Determine the Turing machine

In deterministic Turing machines (DTM), its control rules stipulate that no more than one action can be performed in any given case.

The deterministic Turing machine has a transition function that specifies three things for a given state and symbol under the tape head:

To write the symbol of the tape, the direction in which the head should be moved (left, right, or neither), and the subsequent state of limited control.

For example, an X on the tape of state 3 might cause DTM to write Y on the tape, move the head one position to the right, and then switch to state 5.

Uncertain Turing machine

In theoretical computer science, non-deterministic Turing machine (NTM) is a theoretical computing model, and its control rules specify multiple possible actions in some given cases. That is, the next state of NTM is not entirely determined by its actions and the current symbols it sees (unlike deterministic Turing machines).

For example, the X on the tape of state 3 might allow NTM:

Enter Y, move to the right, then switch to state 5 or write an X, move to the left, and stay in state 3.

So the question is, how do you choose the next step for an uncertain Turing machine? In fact, NTM is lucky enough that it always chooses the step that ultimately points to the state of acceptance.

You can think of many branches of NTM as many copies, each of which follows a possible transformation. DTM follows a single "computation path", while NTM is a "computation tree". If at least one branch in the tree causes the acceptance state, then NTM accepts the input state.

Let's take a look at the decision diagram of the two:

It is determined that Turing machines and non-deterministic Turing machines are computationally equivalent, that is, although they usually have different runtimes, any NDTM can be converted to DTM (and vice versa). This can be proved by construction.

At this point, the study of "what is a definite Turing machine and an undetermined Turing machine" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.