Church-Turing thesis refers to the concept of an effective, systematic, or mechanical method in logic, mathematics, and computer science. It is formulated as a description of the intuitive concept of computability and, in relation to general recursive functions, is more often called Church's thesis. It also refers to the theory of computer-computable functions. The thesis appeared in the 1930s, when the computers themselves did not yet exist. It was later named after the American mathematician Alonso Church and his British colleague Alan Turing.
The effectiveness of the method of achieving results
The first device that looked like a modern computer was Bombie, a machine created by the English mathematician Alan Turing. It was used to decrypt German messages during World War II. But for his thesis and formalization of the concept of an algorithm, he used abstract machines, later called Turing machines. The thesis is of interest to both mathematicians and programmers, as this idea inspired the creators of the first computers.
In computability theory, the Church-Turing thesis is also known as the hypothesis about the nature of computable functions. It says that for any algorithmically computable function on natural numbers, there is a Turing machine capable of computing it. Or, in other words, there is an algorithm suitable for it. A well-known example of the effectiveness of this method is truth test charts for checking tautology.
A method for achieving any desired result is called “effective”, “systematic” or “mechanical” if:
- The method is specified in terms of a finite number of exact commands, each instruction is expressed using a finite number of characters.
- It will be executed without errors, will lead to the desired result in a certain number of steps.
- The method can be performed by a person without assistance with any equipment other than paper and pencil
- It does not require understanding, intuition or ingenuity on the part of the person performing the action
Earlier in mathematics, the informal term “effectively computable” was used to mean functions that can be calculated using pencil and paper. But the very notion of algorithmic computability was more intuitive than anything concrete. Now it was characterized by a function with a natural argument, for which there is a calculation algorithm. One of Alan Turing's accomplishments was the presentation of a formally accurate predicate, with the help of which one could replace the informal one if the condition for the effectiveness of the method was used. Church made the same discovery.
Basic concepts of recursive functions
The substitution of predicates proposed by Turing, at first glance, looked different from that proposed by his colleague. But as a result, they turned out to be equivalent, in the sense that each of them chooses the same set of mathematical functions. The Church-Turing thesis is a statement that this set contains every function whose values can be obtained by a method that satisfies the efficiency conditions. There was another difference between these two discoveries. It consisted in the fact that Church considered only examples of positive integers, while Turing described his work as encompassing computable functions with an integral or real variable.
Common recursive functions
Church’s original formulation says that the calculation can be done using the λ calculus. This is equivalent to using common recursive functions. Church-Turing thesis encompasses more types of calculations than those originally envisioned. For example, related to cellular automata, combinators, registration machines and substitution systems. In 1933, mathematicians Kurt Gödel and Jacques Herbrand created a formal definition of a class called common recursive functions. It uses functions in which more than one argument is possible.
Creating a λ-calculus method
In 1936, Alonso Church created a definition method called λ-calculus. It was associated with natural numbers. Inside the λ-calculus, the scientist determined their coding. As a result, they received the name of Church numbers. A function based on natural numbers was called λ-computable. There was another definition. A function from Church's thesis is called λ-computable under two conditions. The first sounded like this: if it was calculated on Church elements, and the second condition was the possibility of a member representing the λ-calculus.
Also in 1936, before studying the work of his colleague, Turing created a theoretical model for abstract machines, now called by his name. They could do the calculations by manipulating the characters on the tape. This also applies to other mathematical operations found in theoretical computer science, such as quantum probabilistic calculations. The function from Church's thesis was only subsequently justified using a Turing machine. Initially, they relied on λ-calculus.
Function computability
With suitable coding of natural numbers in the form of sequences of characters, a function on natural numbers is called computable according to Turing, if the abstract machine found the desired algorithm and displayed this function on tape. A similar device, which did not exist in the 1930s, in the future began to be considered a computer. The abstract Turing machine and Church's thesis became the forerunners of the era of development of computing devices. It was proved that the function classes formally defined by both scientists coincide. Therefore, as a result, both statements were combined into one. Church's computational functions and thesis also had a strong influence on the concept of computability. And also became an important tool for mathematical logic and theory of evidence.
Justification and problems of the method
There are conflicting points of view on the thesis. Numerous evidence has been compiled for the “working hypothesis” proposed by Church and Turing in 1936. But all the known methods or operations for identifying new effectively calculated functions from the given ones were associated with methods for constructing machines that did not exist then. In order to prove Church-Turing thesis, one proceeds from the fact that each realistic model of computation is equivalent.
Due to the variety of different analyzes, as a rule, this is considered particularly convincing evidence. All attempts to more accurately determine the intuitive notions of an effectively calculated function turned out to be equivalent. Each proposed analysis proved that it identifies the same class of functions, namely those that are computable by Turing machines. But some computational models turned out to be more efficient in terms of time costs and memory usage for different tasks. It was later noted that the basic concepts of recursive functions and Church's thesis are rather hypothetical.
"Thesis M"
It is important to distinguish between Turing's thesis and the assertion that everything that can be calculated by a computing device can be calculated by its machine. The second option has its own definition. Gandhi calls the second sentence "Thesis M". It sounds like this: "No matter what can be calculated by the device, it can be calculated by a Turing machine." In the narrow sense of the thesis, it is an empirical proposition, the truth value of which is unknown. Turing's thesis and "Thesis M" are sometimes confused. The version of the second is broadly incorrect. Various conditional machines have been described that can calculate functions that are not Turing computable. It is important to note that the first thesis does not entail the second, but is consistent with its falsity.
Reverse implication of the thesis
In computability theory, Church's thesis is used as a description of the concept of computability by a class of general recursive functions. American Stephen Kleene gave a more general wording. He called partially recursive all partial functions that can be calculated using algorithms.
Reverse implication is usually called Church's inverse thesis. It consists in the fact that each recursive function of positive integers is effectively calculated. In a narrow sense, a thesis simply means that possibility. But broadly, it abstracts from the question of whether this conditional machine can exist in it.
Quantum computers
The concepts of computable functions and Church's thesis became an important discovery for mathematics, machine theory, and many other sciences. But the technique has changed a lot and continues to improve. It is assumed that quantum computers can perform many common tasks with less time than modern ones. But questions remain, such as the problem of stopping. A quantum computer cannot answer it. And according to Church-Turing thesis, no other computing device either.