In fact, it is difficult for students without computer expertise to understand the meaning of this word. In fact, students majoring in computer science do not have a deep understanding of the concepts of Turing machine, Turing completeness and Turing test. In order to facilitate the understanding of blockchain technology and smart contracts, the author is going to take you step by step to understand Turing machine in several articles. I believe that through these articles, you can understand what Turing is complete.
Alan mathison turing (19 12 June 23rd-1June 7th, 954), a British mathematician and logician, is known as the father of computer science theory and artificial intelligence.
193 1 year, Turing was admitted to King's College, Cambridge University, and won a mathematics scholarship for his excellent performance.
1936 in may, turing, who was only 24 years old, published a paper entitled "on the application of digital calculation in decision-making problems". In this paper, a computing device is proposed, which is later called "Turing Machine". Turing machine is not a concrete computer, but a computing concept and theory.
1938 received his Ph.D. from Princeton, and his thesis was entitled "Logical System Based on Ordinal Number", which had a far-reaching influence on the research of mathematical logic. In the same year, Turing returned to England and worked as a researcher at King's College, Cambridge University.
During World War II, Turing went to 1939 to engage in military work, mainly to decipher enemy passwords. Because of the need of deciphering, he participated in the development of the earliest electronic computer in the world. He achieved excellent results in his work, deciphered the German Enigma code, and won the highest award of the government-1945 Medal of Honor of the British Empire.
From 65438 to 0945, Turing completed his work in the Ministry of Foreign Affairs. He tried to resume his pre-war research in theoretical computer science and develop a new computer.
1950 published the paper "computational machinery and intelligence", which provided a pioneering idea for the later artificial intelligence science. The famous Turing test was put forward.
1950, 1950, 10 In June, Turing published a paper, "Can machines think? . This epoch-making work won Turing the title of "Father of Artificial Intelligence". At this time, artificial intelligence has also entered the stage of practical development. With the continuous maturity of AI technology in recent years, people are more and more aware of the profundity of Turing's thoughts: they are still one of the main ideas of artificial intelligence.
1On June 7th, 954, Turing, who was only 4 1 year old, was found dead in his bed at home with an apple on his head. This is the origin of the logo of the now famous Apple Computer Company.
From Turing's life, we know that he was born in the early 20th century. 19 12.
In the national structure of the world, World War I broke out at this time (1913 ~1921), followed by World War II from 1939 to 1945. As we all know, these two world wars forced many scientific and technological developments. During World War II,
In the development of scientific and technological civilization, the mathematicization of logic has promoted the birth and development of mathematical logic. But at the same time, the third mathematical crisis happened in this period, which is introduced as follows. Turing took the course "Basic Mathematics" when he was in Cambridge. The speaker is Newman. Newman's whole course includes the proof of Godel's incompleteness theorem and unresolved decisive problems.
Behind these scientific and technological events is actually people's cognitive research on computability theory, and Turing is the terminator of this problem.
Incidentally, Einstein put forward the special theory of relativity in 1905, and Turing, who was only in 1927 15 years old, wrote an abstract to help his mother understand the theory of relativity.
Before the 20th century, it was generally believed that all problem classes had algorithms, and people's calculation research was to find out the algorithms. 1900, the famous mathematician Hilbert put forward 23 famous mathematical problems to the international mathematical community at the mathematician conference at the turn of the century.
The tenth question is this:
"Diophantine equation" refers to one or more integral coefficient equations, and their solutions are only in the integer range.
The simple explanation of the above problem is: given an uncertain equation arbitrarily, it is judged whether the equation has an integer solution through finite step operation.
This question is in 1970. A mathematician in the Soviet Union proved that in fact, many mathematical problems have no answers, and even there are more questions without answers than those with answers.
This paper puts forward the problem of limited and mechanical proof steps, which is actually an algorithm. But people didn't know what "algorithm" was at that time. In fact, many problems in the field of mathematics at that time were closely related to "algorithm", so a scientific definition of "algorithm" came to the fore. Then, in 1930s, two people finally put forward the method of defining the algorithm accurately, one is Turing and the other is Church. Turing machine model proposed by Turing is more intuitive.
Turing's way of thinking about this problem is different from ordinary people. Turing was thinking about three issues when writing the aforementioned paper "On Countability and Its Application in Determinism".
A genius like Turing has a high-profile understanding of thinking.
Turing's first consideration is whether all the math problems have been solved. If this problem is not solved, he will try to solve it and finally find no solution. All efforts are a waste of time and energy.
For mathematical problems with answers, only a part of them can be completed in a limited number of steps, thus determining the boundaries of the computer.
After determining the boundary, we should design a universal, effective and equivalent machine to ensure that we do things according to this method and finally get the answer. Turing machine is such a machine designed by Turing. Strictly speaking, it is a mathematical model and a theoretical calculation model.
Turing machine has been put forward for more than 80 years. Today, all computers, including quantum computers, are not beyond the theoretical scope of Turing machine.
The third mathematical crisis occurred at the end of 19 and the beginning of the 20th century, when mathematics was in an unprecedented period of prosperity. The first is the mathematization of logic, which promotes the birth of mathematical logic.
As early as the end of 19, Cantor made a basic research on set theory. It is found that all mathematics can be summarized by the concept of set, which means that set is the basis of all mathematics. However, when the building was about to be completed, a terrible thing happened, and Russell paradox shattered the mathematician's dream.
A popular version of Russell's paradox is:
Why is it the third mathematical crisis?
Because there is a very important concept: shutdown problem, which is a very important problem in the computability theory of logic mathematics and the solution to the third mathematical crisis.
The problem of downtime is to judge whether any program can end running in a limited time. This problem is equivalent to the following judgment problem: whether there is a program P or not, for any input program W, it can be judged that W will end in a limited time or loop indefinitely.
Some people speculate that Turing machine model was designed by Turing when thinking about downtime, which is very reasonable.
During his stay at King's College, Cambridge, Turing studied a new book called Mathematical Basis of Quantum Mechanics, which was written by a young Hungarian mathematician, john von neumann. Turing realized that calculation can be expressed by deterministic mechanical motion. In fact, although our current electronic computer is not mechanical in our traditional sense, the electronic movement inside the CPU is equivalent to mechanical movement.
At the same time, Turing also realized that people's thoughts and consciousness come from the uncertainty principle in quantum mechanics, which is not only the microscopic world, but also the law of the universe itself. So Turing realized that calculation is certain and determinable, while consciousness is uncertain and uncountable.
Today, with the great development of AI artificial intelligence, many people are worried that computers will be as conscious as people. In fact, Turing had considered this issue more than 80 years ago.
As mentioned earlier, Turing wrote a paper "Computing Machine and Intelligence" in 1950, in which the word Turing test was put forward:
How difficult is this test? At present, all our artificial intelligence has not completed this test. The AI products displayed at the Google I/O conference in March, 2065438+2008 are said to have "partially passed the Turing test". How much of this part is unknown.
Historically, the period from the end of 19 to the middle of the 20th century was the transitional period between the second industrial revolution and the third industrial revolution. The second industrial revolution was mainly about the invention and use of electricity, magnetism and internal combustion engines. By this time, scientists have a clearer understanding of the world, and natural sciences such as physics and mathematics have developed rapidly. Mathematicians at this time found that many phenomena can be expressed by mathematical models, from the movement of objects to the movement of planets, from heat energy to kinetic energy, from electricity to magnetism and so on. Then the question is, can all phenomena be expressed by mathematical models? It is this problem that urges people to think and study many basic problems in mathematics.
There is an old saying in China: Heroes come from troubled times. In the Turing era, there were many scientific heroes in the history of science, including Einstein, von Neumann, Turing, Godel and so on. On the one hand, it is the background of the times, on the other hand, their talents and efforts have greatly accelerated the process of the third industrial revolution represented by informationization.
Judging from the thinking, problem-solving methods and cognition of these masters, they are beyond ordinary people. From the thinking of computability theory, it gives us great enlightenment:
* * For more technology and thinking about blockchain, you can scan the code and join my small circle. Here, I am with you. We study blockchain technology together, discuss blockchain thinking, predict the future of blockchain, and be the top 10% person in the future.
**