Church’s thesis the thesis, proposed by Alonzo Church at a meeting of the American Mathematical Society in April 1935, ‘that the notion of an effectively calculable function of positive integers should be identified with that of a recursive function. . . .’ This proposal has been called Church’s thesis ever since Kleene used that name in his Introduction to Metamathematics (1952). The informal notion of an effectively calculable function (effective procedure, or algorithm) had been used in mathematics and logic to indicate that a class of problems is solvable in a ‘mechanical fashion’ by following fixed elementary rules. Underlying epistemological concerns came to the fore when modern logic moved in the late nineteenth century from axiomatic to formal presentations of theories. Hilbert suggested in 1904 that such formally presented theories be taken as objects of mathematical study, and metamathematics has been pursued vigorously and systematically since the 1920s. In its pursuit, concrete issues arose that required for their resolution a delimitation of the class of effective procedures. Hilbert’s important Entscheidungsproblem, the decision problem for predicate logic, was one such issue. It was solved negatively by Church and Turing – relative to the precise notion of recursiveness; the result was obtained independently by Church and Turing, but is usually called Church’s theorem. A second significant issue was the general formulation of the incompleteness theorems as applying to all formal theories (satisfying the usual representability and derivability conditions), not just to specific formal systems like that of Principia Mathematica.
According to Kleene, Church proposed in 1933 the identification of effective calculability with l-definability. That proposal was not published at the time, but in 1934 Church mentioned it in conversation to Gödel, who judged it to be ‘thoroughly unsatisfactory.’ In his Princeton Lectures of 1934, Gödel defined the concept of a recursive function, but he was not convinced that all effectively calculable functions would fall under it. The proof of the equivalence between l-definability and recursiveness (by Church and Kleene) led to Church’s first published formulation of the thesis as quoted above. The thesis was reiterated in Church’s ‘An Unsolvable Problem of Elementary Number Theory’ (1936). Turing introduced, in ‘On Computable Numbers, with an Application to the Entscheidungsproblem’ (1936), a notion of computability by machines and maintained that it captures effective calculability exactly. Post’s paper ‘Finite Combinatory Processes, Formulation 1’ (1936) contains a model of computation that is strikingly similar to Turing’s. However, Post did not provide any analysis; he suggested considering the identification of effective calculability with his concept as a working hypothesis that should be verified by investigating ever wider formulations and reducing them to his basic formulation. (The classic papers of Gödel, Church, Turing, Post, and Kleene are all reprinted in Davis, ed., The Undecidable, 1965.) In his 1936 paper Church gave one central reason for the proposed identification, namely that other plausible explications of the informal notion lead to mathematical concepts weaker than or equivalent to recursiveness. Two paradigmatic explications, calculability of a function via algorithms or in a logic, were considered by Church. In either case, the steps taken in determining function values have to be effective; and if the effectiveness of steps is, as Church put it, interpreted to mean recursiveness, then the function is recursive. The fundamental interpretative difficulty in Church’s ‘step-by-step argument’ (which was turned into one of the ‘recursiveness conditions’ Hilbert and Bernays used in their 1939 characterization of functions that can be evaluated according to rules) was bypassed by Turing. Analyzing human mechanical computations, Turing was led to finiteness conditions that are motivated by the human computer’s sensory limitations, but are ultimately based on memory limitations. Then he showed that any function calculable by a human computer satisfying these conditions is also computable by one of his machines. Both Church and Gödel found Turing’s analysis convincing; indeed, Church wrote in a 1937 review of Turing’s paper that Turing’s notion makes ‘the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately.’ This reflective work of partly philosophical and partly mathematical character provides one of the fundamental notions in mathematical logic. Indeed, its proper understanding is crucial for (judging) the philosophical significance of central metamathematical results – like Gödel’s incompleteness theorems or Church’s theorem. The work is also crucial for computer science, artificial intelligence, and cognitive psychology, providing in these fields a basic theoretical notion. For example, Church’s thesis is the cornerstone for Newell and Simon’s delimitation of the class of physical symbol systems, i.e. universal machines with a particular architecture; see Newell’s Physical Symbol Systems (1980). Newell views the delimitation ‘as the most fundamental contribution of artificial intelligence and computer science to the joint enterprise of cognitive science.’ In a turn that had been taken by Turing in ‘Intelligent Machinery’ (1948) and ‘Computing Machinery and Intelligence’ (1950), Newell points out the basic role physical symbol systems take on in the study of the human mind: ‘the hypothesis is that humans are instances of physical symbol systems, and, by virtue of this, mind enters into the physical universe. . . . this hypothesis sets the terms on which we search for a scientific theory of mind.’
See also COMPUTER THEORY, GÖDEL’S IN- COMPLETENESS THEOREMS , PROOF THEORY, RECURSIVE FUNCTION THEORY. W.S.