In our opinion, the most important reason is that Turing is the first person to analyze the concept of algorithm completely along Godel's thought, and the concept of Turing machine clarifies the connotation of the concept of formal system; At the same time, like Post's idea in the 1920s, Turing introduced the computing system into the physical world by pointing out what machines can do, which triggered an information revolution and a big debate about heart-brain-computer. Moreover, Turing's paper reveals the fact that Godel realized that computability is an absolute concept that does not depend on formal systems.
With the assumption that "the development of computers follows Moore's Law" is generally accepted, Godel highly praised several factors of Turing's work, which showed more theoretical and practical significance to the development of computers. In the1980s, people began to discuss how to "transcend Turing computing", and regarded purely abstract mathematical concepts such as algorithms or calculations as the embodiment of physical laws, and regarded computing systems as the natural result of natural laws. In particular, I think that the Church-Turing proposition also leads to a physical principle, which is the physical version of the Church-Turing proposition put forward by D. deutsch in 1985 (also called the principle of strangeness). It is based on this principle that the computational nature of quantum computers has become the focus of attention since 1990. We believe that when we question the research program of cognitive computability in cognitive science, it is more necessary to clarify the connotation of Church-Turing proposition and singularity principle, and it is also necessary to make a proper logical analysis of the computational nature of quantum computers.
1 why didn't Godel bring up the topic of church?
Historically, R.Dedekind, G. Peano, T.Skolem, D.Hilbert and W.Ackermann all studied recursive functions, but Godel was the first person to define this concept accurately. The "primitive recursive function" we are talking about today was introduced by Godel in the epoch-making paper 193 1. 1934 From February to May, Godel introduced the concept of general recursive function in a series of lectures on incomplete results at Princeton College, pointing out that:
"The general recursive function (we now call it the original recursive function) has an important feature, that is, for each given set of independent variable values, the function value can be calculated through a limited program."
The historical significance is that Godel added a very constructive explanation (the famous footnote 3):
"The inverse proposition of this proposition [that is, every function calculated by a finite program is an original recursive function] seems to be true. Besides [primitive] recursion, are other forms of recursion allowed (such as recursion corresponding to the addition of two variables)? Because the concept of finite computability has not been defined, it is impossible to prove the inverse of this proposition at present, but it can be used as a principle to help exploration. " [6]
Godel's footnote was once considered by Martin Davis as a form of church paper. He even restated this in the name of "Godel's thesis":
Every mechanical computable function can be defined by a general recursive function.
In a paper introducing G? del's lecture, Davis expressed his views and sent the first draft to G? del for evaluation. This paper will be compiled into Uncertain Essays. To Davis' surprise, Godel expressed different opinions in his reply:
"... it is incorrect to say that footnote 3 is a statement of the church's thesis. I just put forward a guess that' finite computable program' and' recursive program' are equivalent. But in the series of lectures, I didn't expect that my concept of recursion included all possible recursion. ”[3]
From this letter, we can at least see that Godel gave the definition of "recursive function" in today's sense in the spring of 1934, but he didn't guess that his definition at that time was wide enough to include all recursion. Moreover, he thinks that his conjecture about the computability of the algorithm (that is, Davis's "Godel's thesis") is not the same as Church's thesis, but it can be used as a detection principle to help people find a satisfactory mathematical description of the concept of algorithmic computability.
2 from l definability to church topic
Church published his paper in a report of the American Mathematical Society in April 1935. In fact, Church's earliest concern about computability began with the concept of l definability. According to Church's student S.C.Kleene, by 1933, Church's "l definability" had been circulated among logicians in Princeton as a mature concept. At that time, he guessed that the l definable function was the algorithmic computable function, and finally put forward this topic. Later, Colin once recalled:
"When Church raised this topic, I was going to prove it by diagonalization, hoping to point out that the computable function of the algorithm exceeded L definable function classes. But I soon realized that I couldn't do it. So, overnight, I became a supporter of the church topic. " [9]
According to Davis' investigation, although Church was obviously interested in the concept of computability in 1933- 1934, until Godel gave a series of lectures in Princeton, there was no obvious indication that he thought the computability of the algorithm conformed to some strict mathematical concept, and there was no special statement about it. Perhaps after discussing with Godel from February to May in 1934, a clear opinion was formed and later church papers were given. 1935165438+1On October 29th, Church gave a somewhat vague statement:
"Speaking of the concepts of Godel, recursive function and algorithmic computability, this history turned out to be like this. When discussing the concept of l definability with Godel, we found that we could not find a good definition of algorithm computability. I propose that l definability can be used as a definition, but Godel thinks it is totally inappropriate. I replied that if you can provide any definition, even if it is partially satisfactory, I will prove that it must be included in the definable concept of L. At that time, Godel's only idea was to regard algorithmic computability as an uncertain concept, state an axiom set that can describe the recognized characteristics of this concept, and then do other things on this basis. Obviously, he later thought that the concept of recursive function proposed by J.Herbrand could be modified in the direction of computability. In particular, he pointed out that recursion and the computability of the algorithm can be linked in this sense. However, he added that he did not think that the two concepts could be satisfactorily confirmed to be consistent with each other, unless it was helpful for exploration in a certain sense. " [3]
When Church announced his project to the mathematics community on 1935, he expressed it like this: "Take Earl Brown's suggestion and make some amendments in an important aspect. Godel put forward the definition of recursive function in 1934 series of lectures, and basically adopted Godel's definition of positive integer recursive function. It should be emphasized that the algorithmic computable function of positive integer will be determined to be consistent with recursive function. Because other specious definitions about the computability of algorithms are originally derived concepts, which are either equivalent to recursion or weaker than recursion. " [3]
Obviously, Church did not choose to use the term "l definable" to state his thesis, but used the term "Elbrown-Godel general recursive function". Here, the definability of L is implied in the specious definition of computability of other algorithms. This wording gives the impression that in the spring of 1935, Church has not decided that the definability of L is equivalent to the general recursion of Earl Brown-Godel. Until April of 1936, Qiu Qicai came to the conclusion that the L definable function is a general recursive function in an unsolvable problem in elementary number theory.
In the paper 1936, Church gave the standard expression of what we now know as Church's paper: "Now we define the concept of algorithmic computability of positive integers by conforming to the concept of positive integer recursive function (or positive integer L definable function). This selected definition, which conforms to the intuitive concept of computability, is considered to have been verified. " [ 1]
Here, Church calls this equivalent relationship between the computability and recursion of the algorithm "definition". Post (E.Post) 1936 strongly opposes the formulation of the definition and thinks that it should only be regarded as a working hypothesis. In 1943, Clinney pointed out that the proposition describing this equivalence contains the characteristics of the strong working hypothesis, although we do have good reasons to believe it. So it is suggested to use the term "thesis" to express this proposition.
Although Church's thesis was put forward, Godel did not agree that computability was equal to recursion or l definability at that time. In his view, it is impossible to have a completely satisfactory and strict mathematical definition until a set of recognized characteristics of the computability concept of axiomatic representation algorithm are found. It was not until A.Turing published the results in 1936 that Godel admitted that this difficulty had been overcome.
Why did Godel appreciate Turing's paper?
We think that because of 1934- 1936, Church, Corinne and Godel have done a series of work on the mathematical description of the concept of computability, and finally Church put forward the standard form of his Church thesis. At the same time, Turing's thinking about computability is completely independent of Princeton mathematicians, and finally the concept of Pan Turing Machine is used to describe the computability of the algorithm, that is, "what the algorithm can calculate is what the Pan Turing Machine can achieve". Can be expressed as the following "Turing proposition":
"Each algorithm can be programmed on a universal Turing machine."
In the postscript of Princeton Lecture Notes (1934) published in 1965, Godel spoke highly of Turing's work. We believe that there are at least several main reasons why Godel does not accept the church proposition but appreciates the Turing proposition:
The concept of (1) universal Turing machine clarifies the concept of formal system.
It can be said that when Godel proves the incompleteness theorem, the formal system is still a rather vague concept, otherwise Godel will prove his theorem in a more concise way. It is the concept of Turing machine that makes the characteristics of formal system clearer and more accurate. Formal system is just a mechanical program that produces theorems, and the working program of Turing machine is exactly the program that mathematicians actually work in formal system. In other words, the formal system is just a Turing machine, which allows you to make choices in certain steps according to a predetermined range. Of course, it is precisely because of the concept of Turing machine that Godel's incompleteness theorem on mathematical formal systems has produced Turing machine programs to replace various versions of formal systems, such as the version of downtime problem and the later version of complexity in algorithmic information theory. [ 10]
(2) Turing reached his conclusion along the research approach closest to Godel's thought.
Although Church's work is exquisite and elegant, he is completely based on pure mathematical analysis. Turing's analysis is not limited to the formal world of mathematics, it is a commendable example of philosophical application. [3] In addition, Turing reached his conclusion along the research method closest to Godel's idea. Godel once commented that "Turing's work gives an analysis of the concept of' mechanical program' (also known as' algorithm',' calculation program' or' combination program') and points out that this concept is equivalent to' Turing machine'". However, other equivalent definitions of computability given before "rarely suit our original purpose anyway". [2]
So, what is Godel's "original purpose"? Obviously, he has always advocated that "the computability of the algorithm is regarded as an undefined concept, and an axiom set that can describe the recognized characteristics of this concept is given, and then something can be done". In his view, this is the real way to seek a strict mathematical description of computability. Although Turing did not use any formal axiomatic method to deal with the problem, he pointed out that "the recognized characteristics of algorithm computability" will inevitably lead to some kind of function class, which can be accurately defined. Turing machine, which clearly and accurately expresses the concept of mechanical program, refers to Turing machine that produces partial recursive function, rather than general recursive function. Therefore, in Godel's view, Turing was the first person to give a convincing reason for the consistency between the precise concept and the intuitive concept. It is correct and consistent with our original intention to describe the computability of the algorithm with the distinct concepts of "programmable on Turing machine" or "realizable on Turing machine".
(3) The concept of computability of Turing machine reveals the fact that computability is independent of formal system.
In order to let us further see why Turing's work is so important to Godel, we should also examine Godel's understanding of the concept of absolute computability. On June 1935, 19, Godel reported "On the Length of Proof" at Vienna University, referring to the so-called "acceleration theorem". The strict statement of [7] theorem uses the concept that a function φ(x) is computable in a formal system S, which means that for every number m, there is a corresponding number n, so φ(m)= n is provable in the system. For the sequence S 1, S2, ... in which each system satisfying the formal system is stronger than the previous system, this means that a function is computable in Si, which means that it depends on I. ..
In this report, Godel added a note about "absolute computability": "It can be pointed out that a function that can be calculated in Si, one of the formal systems, or even in the superheterodyne type is already computable in S 1. Therefore, in a sense, the concept of' computability' is' absolute', while all other well-known metamathematical concepts (such as provable and definable) in reality are completely dependent on the given system. "
Godel's understanding of this kind of "absolute" computability is roughly in 1934- 1935, 1946. In "Speech on Mathematics on the 200th Anniversary of Princeton", Godel particularly emphasized this kind of "absolute" meaning:
"In my opinion, the extreme importance of the concept of general recursion or Turing machine computability seems to be largely attributed to the fact that with the help of this concept, it successfully gives the absolute definition of meaningful epistemological concept for the first time, that is, computability does not depend on the choice of formal system. But in all other cases of previous processing, such as defining decidability or definability, it depends on the given language. Although absolute computability is only a special concept of decidability, the situation is completely different from the past. " [8]
(4) The concept of Turing Machine introduces computing system into the physical world.
Another reason why Godel deserves to praise Turing's work may be that, like Post's idea in the 1920s, Turing introduced the computing system into the physical world by pointing out what computing machines could do, or in other words, turned a computable problem into a physically realizable one, thus triggering an information revolution and a big debate about heart-brain-computer. Turing actually pointed out that anything that can be formally described and algorithmically processed can be processed quickly and accurately by the computer as a special case of the universal Turing machine. This principle opens a new era of machine simulation of human intelligence. As Turing said in his article Countable Numbers, his motivation to study computability is not only formal, but "mental science". Even in his later years, Godel is still interested in discussing the topic of mind-brain-computer proposed by Turing, which may indicate that he likes psychological science.
The Physical Version of Church-Turing Proposition and the Computational Essence of Quantum Computer
Godel's appreciation of Turing's work is precisely the foundation and motivation for the development of modern theoretical computers. When the first universal electronic computer was born, people really saw the physical realization of the universal Turing machine (although there was no infinite storage). From then on, people began to think, is the real world itself computable? Is the ideal simulator for simulating objective reality physically realizable in principle, or is the objective world completely beyond the scope of general Turing machine simulation? A considerable number of physicists are optimistic about this. 1985, Professor Dodge of Oxford University even put forward an inspiring physical version of the Church-Turing thesis, replacing "computable function" with "finite realizable physical system" and stating his so-called "odd principle" (also known as the Church-Turing principle of physics): "Every finite realizable physical system, as we know, Therefore, in principle, a general-purpose computer can be used to operate a perfect simulation in a limited way.
Obviously, the Duoqi principle is a stronger "working hypothesis" than the Chuchi-Turing thesis. From the Church-Turing proposition to the Duoqi principle, our computable territory is constantly expanding. If the Duoqi principle is correct, it will reveal the profound nature of physical reality. This position based on physicalism and computability is also the core of various working hypotheses pursued by artificial intelligence experts. Dodge and others regard purely abstract mathematical concepts such as algorithms or calculations as the embodiment of physical laws and the computing system as the natural result of natural laws. In their view, the concept of general-purpose computer is not only recognized by the laws of nature, but also probably the inherent requirement of the laws of nature. In fact, we know that all those who advocate virtual reality technology, artificial life and artificial intelligence believe in the truth of the singularity principle. Of course, there is no strong scientific evidence to refute the odd number principle, because it is a full-name proposition containing the concept of "universal simulation machine". In principle, the number of algorithms (programs) that can be realized by a general simulator is infinite.
According to the latest development of theoretical computer, the advocates of quantum computer assert that the universal simulator that can realize the odd principle can only be the quantum universal Turing machine. 1998 "standard-bearer in quantum field" G.L.Milburn pointed out that the physical theory is closely related to the physical version of the Church-Turing thesis. The fact is that the observed data given by the physical theory through mathematics are exactly the data provided by what we call computable problems, so these data can be obtained through the algorithm running on the general Turing machine. Both classical and quantum physical systems can be simulated with arbitrary high precision. However, for some problems, the running time of the program may be an astronomical number. If the world is classic, Monte Carlo method can be used to simulate randomness effectively; But if the world is a quantum with irreducible randomness, the classical randomness based on hidden variables cannot be used to explain quantum randomness, and the game of quantum world should follow Feynman's law. Therefore, R.Feynmen realized that the solution to this problem is to build a quantum computer, that is, to use the quantum process itself as a means of calculation, and the basic steps of calculation will be carried out at the atomic or subatomic level. Therefore, in 1998, the Church-Turing proposition was revised as follows:
"The results of all limited descriptive physical measurement systems can perfectly simulate the operation of a general quantum computer in a limited way, and the recording of measurement results is the final product."
The "limited describable physical measuring system" here means that the instructions for establishing and operating measuring devices must be able to be expressed in limited codes; "Perfect simulation" means that the data generated by simulation cannot be distinguished from the data obtained by real measurement; "Final product" means that all analog measurements must end at some point and no new results will be produced.
So where does quantum computer surpass classical computer? What is its computational essence?
First of all, quantum computers can do calculations that classical computers can't do: for example, they can simulate quantum physical systems with arbitrary accuracy, so that the solution time does not increase exponentially with the scale of the problem. For example, in the past, even if a supercomputer was used, it would take longer than the age of the universe to complete the operation of decomposing a 64-bit number into the product of prime factors. The quantum algorithm of Peter Shor of Bell Laboratories, relying on large-scale quantum entanglement, can successfully decompose a 64-bit number into the product of prime factors in a relatively short time on a quantum computer. The ability of quantum computer to surpass classical Turing machine lies in the power of parallel computing generated by quantum coherence.
Quantum computer is a physical device to realize calculation, a physical system operating according to the laws of quantum physics, and a modern computer based on quantum Turing machine. The algorithm of universal Turing machine is completely certain. In this deterministic algorithm, when the current state of the reading and writing head of Turing machine and the contents of the current storage unit are given, the next state and movement of the reading and writing head are completely determined. In the classical probability algorithm, when the current state of the read-write head and the current content of the storage unit are given, the Turing machine changes to the next state with a certain probability to complete the movement of the read-write head. This probability function is a real number with a value of [0, 1], which completely determines the properties of the probabilistic Turing machine. The difference between a quantum computer and a classical probabilistic Turing machine is that the current read-write head state and the current memory cell content have changed from a classical orthogonal state (0, 1) to a quantum state (the probability superposition state of 0, 1, 0 and 1), and the probability function has changed into a complex-valued probability amplitude function, so the properties of a quantum computer are determined by the probability amplitude function. Quantum computers can perform efficient calculations entirely because of quantum superposition effect, that is, the state of an atom can be in the probability superposition state of 0 and 1. Generally speaking, with L qubits, a quantum computer can process 2L numbers at the same time, which is equivalent to calculating 2L numbers in a classical computer in one step. Quantum computers use quantum States (quantum bits are needed to replace classical bits) to correspond to computer data and programs. The different physical states of the pickup head are described by quantum physics, and the dynamic mechanism of the machine is also determined by quantum physics. Of course, a more important problem is that we must also describe its output, and what we need in the end is classical bits, not quantum bits, which will solve the thorny "decoherence".
However, we must clearly realize that no matter how fast the quantum computer is, since it is only a quantum Turing machine in theory, it is bound to be limited by the logical limit set by Godel's theorem. Quantum computers can't calculate uncountable functions and can't solve the shutdown problem. In the final analysis, the calculation of quantum computer is essentially Turing machine calculation, that is, recursive function calculation, so the Church-Turing proposition is still the theoretical basis of quantum computer. Dodge tried to bring the whole physical world into the calculation range, tried to simulate human intelligence with quantum computers, but still could not get rid of the inherent limitations of logic. If computability is an absolute concept independent of formal system, as Godel said, then quantum computer is just another computing carrier with faster computing speed.
Whether the unremitting pursuit of computing technology can let us capture a real "consistent and complete" world in the program is worth thinking about. [1 1] Are there no logical obstacles in the process of providing scientific answers to natural problems? Besides Turing machine, are there any other computing models, such as DNA computer? Is it possible that human mind is a machine beyond Turing machine? The principle of Duoqi tells us that not only physics determines what a computer can do, but also what a computer can do will determine the ultimate nature of the laws of physics. Obviously, the original intention of the multi-odd principle is not limited to the significance of transforming the computing carrier, but to point out that the real world = the physical world = the computing world.