The Church-Turing thesis refers to the concept of an efficient, 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 computers themselves did not yet exist. It was later named after the American mathematician Alonso Church and his British colleague Alan Turing.
Efficiency of the method to achieve the result
The first device that resembled a modern computer was the Bombie, a machine created by the English mathematician Alan Turing. It was used to decipher 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. Thesis presentsinterest for both mathematicians and programmers, since this idea inspired the creators of the first computers.
In computability theory, the Church-Turing thesis is also known as the conjecture about the nature of computable functions. It states 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 the truth table test for testing tautology.
A way to achieve any desired result is called "effective", "systematic" or "mechanical" if:
- The method is specified in terms of a finite number of exact instructions, each instruction is expressed using a finite number of characters.
- It will run without errors, will produce the desired result in a certain number of steps.
- The method can be performed by a human unaided 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 refer to functions that can be calculated with 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 the achievements of Alan Turing wasrepresentation of a formally exact predicate, with the help of which it would be possible to replace the informal one, if the method efficiency condition is used. Church made the same discovery.
Basic concepts of recursive functions
Turing's change of predicates, at first glance, looked different from the one proposed by his colleague. But as a result, they turned out to be equivalent, in the sense that each of them selects the same set of mathematical functions. The Church-Turing thesis is the assertion that this set contains every function whose values can be obtained by a method that satisfies the efficiency conditions. There was another difference between the two discoveries. It was that Church considered only examples of positive integers, while Turing described his work as covering computable functions with an integral or real variable.
Common recursive functions
Church's original formulation states that the calculation can be done using the λ-calculus. This is equivalent to using generic recursive functions. The Church-Turing thesis covers more kinds of computation than originally thought. 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 general recursive functions. It uses functions where more than one argument is possible.
Creating a methodλ-calculus
In 1936, Alonso Church created a method of determination called the λ-calculus. He was associated with natural numbers. Within the λ-calculus, the scientist determined their encoding. As a result, they are called Church numbers. A function based on natural numbers was called λ-computable. There was another definition. The 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 being represented by a member of the λ-calculus.
Also in 1936, before studying his colleague's work, Turing created a theoretical model for the abstract machines now named after him. They could perform calculations by manipulating the characters on the tape. This also applies to other mathematical activities found in theoretical computer science, such as quantum probabilistic computing. The function from Church's thesis was only later substantiated using a Turing machine. Initially, they relied on λ-calculus.
Function computability
When natural numbers are appropriately encoded as sequences of characters, a function on natural numbers is said to be Turing computable if the abstract machine found the required algorithm and printed this function on tape. Such a device, which did not exist in the 1930s, would in the future be considered a computer. The abstract Turing machine and Church's thesis heralded an era of developmentcomputing devices. It was proved that the classes of functions formally defined by both scientists coincide. Therefore, as a result, both statements were combined into one. Computational functions and Church's thesis also had a strong influence on the concept of computability. They also became an important tool for mathematical logic and proof theory.
Justification and problems of the method
There are conflicting views on the thesis. Numerous evidence was collected for the "working hypothesis" proposed by Church and Turing in 1936. But all known methods or operations for discovering new effectively computable functions from given ones were connected with methods of constructing machines, which did not exist then. In order to prove the Church-Turing thesis, one starts from the fact that every realistic model of computation is equivalent.
Due to the variety of different analyzes, this is generally considered to be particularly strong evidence. All attempts to more precisely define the intuitive notion of an effectively computable function turned out to be equivalent. Every analysis that has been proposed has proven to single out the same class of functions, namely those that are computable by Turing machines. But some computational models have proven to be more efficient in terms of time and memory usage for different tasks. Later it was 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 anything 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 goes like this: “Whatever can be computed by a device can be computed by a Turing machine.” In the narrow sense of the thesis, it is an empirical proposition whose truth value is unknown. Turing's Thesis and "Thesis M" are sometimes confused. The second version is broadly incorrect. Various conditional machines have been described that can compute 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 notion of computability by a class of general recursive functions. The American Stephen Kleene gave a more general formulation. He called partially recursive all partial functions computable by algorithms.
Reverse implication is commonly referred to as Church's reverse thesis. It lies in the fact that every recursive function of positive integers is efficiently evaluated. In a narrow sense, a thesis simply denotes such a possibility. And in a broader sense, 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 technology 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 stopping problem. A quantum computer cannot answer it. And, according to the Church-Turing thesis, no other computing device either.
