Shulou(Shulou.com)05/31 Report--

This article mainly explains "what is the Turing machine and Turing completeness of block chain". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "what is the Turing machine and Turing completeness of the block chain?"

1 composition of Turing machine

There is a classic picture on the Internet to express the composition of the Turing machine. The picture is as follows:

What does this picture mean? How can such a simple machine / device be the theoretical model of all electronic computers?

I believe you all have such questions after seeing this picture. Below, the author brings us to understand the composition of the Turing machine from shallow to deep.

Turing's basic idea is to use machines to simulate the process of people doing mathematical operations with paper and pencil, which is regarded as the following two simple actions:

To write or erase a symbol on paper.

Move your attention from one position of the paper to another

Logically, the Turing machine consists of four parts:

An infinitely long storage band consisting of continuous storage cells, each of which can store a number or symbol

A read-write head that can move left and right on the storage tape and can read and modify numbers or symbols on the storage cell

Internal state memory, which can record the current state of the Turing machine, and has a special state that is the stop state

Control program instructions, which can determine the next action of the read-write head (left or right) according to the current state and the symbols on the grid referred to by the current read-write head, and change the value of the state memory to bring the machine into a new state or keep the state unchanged.

Of course, these are just ideal Turing machines, because there are no infinite storage bands in reality, and a device like a more Turing theory can simulate any calculation that humans can do. Isn't that amazing? I'm sure you won't believe it, but Turing has been proved by strict mathematics. Let's take a look at the calculation process of the Turing machine.

2 the operation mechanism of Turing machine

Working steps of Turing machine

Prepare for

Store the initial grid words on the tape

Set the current state of the internal state memory

The read-write head sets the grid position initially done on the storage tape

Prepare the control command, that is, the control program.

Repeat the following steps until downtime

The read-write head reads the number or symbol of the current grid.

Find the corresponding control instruction according to the current state and the letters or symbols read.

According to the control instructions, perform the following three actions

To erase or write a number or symbol on a grid.

Change the state to a new state

The read and write head moves one grid to the left or right.

I guess you still don't understand. Don't worry. Students who have seen the "three-body" all know that the three-body people regard the earthlings as "worms". The dimensions of the three-body people are higher than the three-dimensional world of the earth, just as we human beings look at bugs.

Next, we put bugs into a two-dimensional world, taking bugs as an example to illustrate the simplest Turing machine model (note: this example is not original).

Suppose the ideal situation one:

The two-dimensional world in which the worm lives is an infinitely long paper tape, which is divided into small squares, each of which is only black and white. The fragments of the paper tape are:

Two-dimensional paper tape where the bug is located

Suppose the bug's senses are only eyes, and its eyesight is pitifully short, and it can only see the color of the current grid.

Bugs can climb one grid forward or one grid backward.

The operating system and program of the bug are as follows: we assume that black is the food area, the bug moves forward one square after eating the food, white is the blank area, and there is no food.

In this case, the color of the grid is the input information of the bug, the set is IN= {black, white}, and the output set is OUT= {move forward one grid, move backward one grid}

How does the bug move from the starting position?

At first it's black, and the bug moves forward one grid to the second grid.

The second is still black, and the bug moves forward one grid to the third.

The third frame is still black, and the bug moves forward one grid to reach the fourth grid.

The fourth frame is white, the bug moves back one grid, and goes back to the third grid.

It can be seen that on this tape, the bugs move back and forth in frames 4 and 3.

Suppose that the ideal case two

In reality, bugs can't be stupid enough to circulate wirelessly. Bugs will feel hungry and full, and the food will disappear after eating. So we improve the model in the case.

When the bug is in the black grid, if it is hungry, eat the food and turn the lattice white; if it is full, move back one grid.

When the bug is in a white grid, if it is hungry, stop and wait for the food to grow black; if it is full, move forward.

The operating system and programs of the bug are:

In this case, the input set is IN= {black, white}, and the output set is OUT= {move forward one grid, move backward one grid, eat the food white, wait for the food to grow black}, internal state S = {full, hungry}

Two-dimensional paper tape remains the same, from the starting position, the bug is initially hungry, how will the bug move?

The first frame is black, the worm is hungry, the food lattice becomes white after eating, and the new state of the worm is full.

The first frame is white, the worm is full, the bug moves forward one grid, reaches the second grid, and the new state of the bug is hungry.

The second frame is black, the insects are hungry, the food lattice turns white, and the new state of the insects is full.

The second frame is white, the worm is full, the bug moves forward one grid, reaches the third grid, and the new state of the bug is hungry.

The third frame is black, the insects are hungry, the food lattice turns white, and the new state of the insects is full.

The third frame is white, the worm is full, the bug moves forward one grid, reaches the fourth grid, and the new state of the bug is hungry.

The fourth frame is white, the worm is hungry, waiting for the food to grow black, and the new state of the bug is full.

The fourth frame is black, the worm is full, the bug retreats one square, reaches the third grid, and the new state of the bug is hungry.

At this point, the third grid has already grown the food, which is black, so the process is the same as in step 5.

In case 2, the behavior of the bug is a little more complicated than the situation, but the bug will still fall into an infinite loop.

At this point, if you have thoroughly understood how two-dimensional bugs move, then you have understood how the Turing machine works! Because in essence, the last bug model is a Turing machine!

3 how to understand Turing machine

I just explained how the Turing machine works with two-dimensional bugs. I believe your first reaction is that such a model is too simple!

He can't explain anything in the real world at all! Next, I will try to convince you that this model of the Turing machine is great!

In fact, all the decisions and behaviors of bugs can be abstracted into a Turing machine model.

Why can we do this abstraction?

In fact, the model of two-dimensional bugs can be expanded to be basically or completely consistent with the real world. Because the two-dimensional bug model starts with the premise that everything is simplified, it is really simple.

However, we can expand the input set, output action set and internal state set of two-dimensional bugs, and this model is suddenly much more practical.

Two-dimensional bugs can be in a three-dimensional space instead of simple paper tape.

The two-dimensional bug has good eyesight and can read information with a radius of 500 meters at a time.

Two-dimensional bugs can also have other sensory organs, such as smell, hearing, and so on, and these changes only expand the dimension and scope of the input set, and there are no other more essential changes.

The possible output set of two-dimensional bugs is also extraordinarily rich. It can not only move itself, but also transform its natural world as much as possible.

Furthermore, the internal state of a two-dimensional bug may be very many, and the programs that control its behavior may be extremely complex.

So what are two-dimensional bugs capable of? This is hard to say, because with the increase of the number of states inside the bug and the increase of the complexity of its environment, we are gradually losing the ability to predict the behavior of two-dimensional bugs.

But all these changes have not escaped the Turing machine model:

"input set, output set, internal state, fixed program instructions!"

It is these four things that capture the foundation of two-dimensional bug information processing.

4 what is Turing complete

Wikipedia explains:

In the theory of computability, a programming language or any other logical system, such as a universal Turing machine, has the computing power of a universal Turing machine. In other words, the system can simulate each other with the universal Turing machine.

The above explanation is quite abstract, through the above example to understand what is Turing machine, Turing complete is actually very simple to understand.

To put it simply, a system or programming language that can be abstracted into a Turing machine is Turing complete; all computable problems can be calculated by a Turing machine, so a logical system, device or programming language that meets such requirements is called Turing complete.

Therefore, it can be seen that the two-dimensional bug is Turing complete.

Bitcoin script because there are no conditional branches, loops and other control instructions, back to the above example of bugs, bugs can not judge according to the current state, choose to move or eat food and other a series of actions, so it does not meet the Turing machine model, is not Turing complete.

Five people are also Turing machines?

Can we be abstracted by this as well? Obviously, you can.

In fact, every one of us who can make decisions and think can be abstractly regarded as a Turing machine, that is, the teacher has always said: everyone has their own operating system, because they have metacognitive ability, and they can upgrade their own operating system.

The input state set is all the things you can see, hear, smell, and feel in your environment, and the possible output sets are your every word, every line, and all the facial expressions you can express. The set of internal states is much more complex. Because we can regard the state combination of any nerve cell as an internal state, then the state combination of all possible nerve cells will be astronomical! This is human memory. As long as the Turing machine has an internal state, it has a memory accordingly.

If you understand it this way, there are two more questions:

The program instructions of the Turing machine are fixed. But human beings have the ability to learn, that is to say, the human brain will evolve and the operating system will be upgraded, so the actual programming rules of the brain are not fixed, and it seems that the Turing machine model cannot be included.

Many human phenomena seem to be able to be used by Turing machines, including emotions, emotions, and so on.

At this point, I believe you have a deeper understanding of "what is the Turing machine and Turing completeness of the block chain". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.