The computability theory , also called recursion theory , is one of the four parts constituting the logic mathematics, the other three being, set theory , model theory and the proof theory , and handles the study and classification of relationships and computable applications. Furthermore, the theory of computability, together with the theory of automata , languages and machines, is the foundation of theoretical computing and this, in turn, of the computer industry.
History
From time immemorial it has been known that certain kinds of problems such as, for example, the determination of the greatest common divisor of two integers, by means of Euclid’s algorithm , or the determination of prime numbers, by means of the Eratosthenes sieve., are algorithmically soluble. There are mechanical algorithms that allow obtaining the solution of the problem in question. So until the beginning of the 20th century it was assumed that algorithms existed and that the only problem was to determine them. So, if you want to determine an algorithm, there is no need to define the class of all algorithms; this is only necessary if it is tried to demonstrate that some problem is not algorithmically soluble, that for this problem there is no algorithm to solve it. It is possible that the first to affirm the non-existence of an algorithm was Tietze in 1908, who said of the finite presentation groups:. . . the question of when two groups are isomorphic is not generally soluble. But it seems that it was, on the one hand, the problem of the declimability of predicate logic raised by Hilbert and Ackermann in their book on logic, published in 1928, and on the other, the issue of the solubility of all mathematical problems, which He induced, for the sake of solving them, various researchers from 1930, and among which we can mention Godel, Church and Turing, to propose various formalizations of the informal concept of mechanically computable function. Because of all these formalizations, and other proposals by Kleene, Post, and Markoff, that they were shown to be two to two equivalents, the hypothesis, known as the Church-Turing-Post-Kleene Hypothesis , was proposed., which affirms the coincidence between the informal concept of mechanically or algorithmically computable partial function, and the formal, mathematical concept of recursive partial application. Naturally, this hypothesis, similar in nature to other hypotheses proposed in the empirical sciences, is not demonstrable, and its ultimate foundation lies in the aforementioned equivalences.
Computable and non-computable sets
The recursion theory originated in the 1930s with the work of Kurt Gödel , Alonzo Church , Alan Turing , Stephen Kleene and Emil Post .
The fundamental results obtained by the researchers stabilized the concept of computable function as the correct way to formalize the idea of effective calculations.
These results led Stephen Kleene (1952) to coin two names, Church’s Thesis and Turing’s Thesis. Today both are considered as a single hypothesis, the Church-Turing Thesis, which states that any function that is computable by a certain algorithm is a computable function. Although he was somewhat skeptical at first, around 1946 Gödel defended this thesis.
With a definition of effective calculations came the first evidence that there are certain problems in mathematics that cannot be solved effectively. Church and Turing, inspired by the techniques used by Gödel to prove his incompleteness theorems, separately demonstrated that it is not possible to decide the Entscheidungsproblem (challenge in symbolic logic to find a general algorithm that would decide if a first order calculus formula is a theorem) in an effective way. This result showed that there is no algorithmic procedure that can correctly decide if certain mathematical propositions are true or not.
Many problems in mathematics have been shown to be undecidable once these first examples were established. In 1947, Markov and Post published their work separately showing that the word problem for semigroups cannot be effectively resolved. Expanding on this result, Pyotr Novikov and William Boone independently demonstrated in the 1950s that the word problem for semigroups cannot be solved effectively: there is no effective procedure that, given a word in a group, decides whether the element represented by the word is the group identity element. In 1970 Yuri Matiyasevich proved (using Julia Robinson’s results) Matiyasevich’s Theorem, which implies that Hilbert’s tenth problem has no effective solution; This problem asked whether or not there was a procedure by which it could be decided whether a diophantine equation for integers has an integer solution. The Undecidable Problems List contains additional examples of problems without computable solutions.
The study of which mathematical constructions can be carried out effectively is sometimes called recursive mathematics; The Handbook of Recursive Mathematics covers many of the known results in this field.
