Copyright © 1999 Massachusetts Institute of Technology
Alonzo Church proposed 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 of identifying an informal notion, effectively calculable function, with a mathematically precise one, recursive function, has been called Church's thesis since Stephen Cole Kleene used that name in 1952. Alan TURING independently made a related proposal in 1936, Turing's thesis, suggesting the identification of effectively calculable functions with functions whose values can be computed by a particular idealized computing device, a Turing machine. As the two mathematical notions are provably equivalent, the theses are "equivalent," and are jointly referred to as the Church-Turing thesis.
The reflective, partly philosophical and partly mathematical, work around and in support of the thesis concerns one of the fundamental notions of mathematical logic. Its proper understanding is crucial for making informed and reasoned judgments on the significance of limitative results -- like GÖDEL'S THEOREMS or Church's theorem. The work is equally crucial for computer science, artificial intelligence, and cognitive psychology as it provides also for these subjects a basic theoretical notion. For example, the thesis is the cornerstone for Allen NEWELL's delimitation of the class of physical symbol systems, that is, universal machines with a particular architecture. Newell (1980) views this delimitation "as the most fundamental contribution of artificial intelligence and computer science to the joint enterprise of cognitive science." In a turn that had almost been taken by Turing (1948, 1950), Newell points to the basic role physical symbol systems have 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." The restrictive "almost" in Turing's case is easily motivated: he viewed the precise mathematical notion as a crucial ingredient for the investigation of the mind (using computing machines to simulate aspects of the mind), but did not subscribe to a sweeping "mechanist" theory. It is precisely for an understanding of such -- sometimes controversial -- claims that the background for Church's and Turing's work has to be presented carefully. Detailed connections to investigations in cognitive science, programmatically indicated above, are at the heart of many contributions (cf. for example, COGNITIVE MODELING, COMPUTATIONAL LEARNING THEORY, and COMPUTATIONAL THEORY OF MIND).
The informal notion of an effectively calculable function, effective procedure, or algorithm had been used in nineteenth century mathematics and logic, when indicating that a class of problems is solvable in a "mechanical fashion" by following fixed elementary rules. Hilbert in 1904 already suggested taking formally presented theories 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 precise characterization of the class of effective procedures. Hilbert's Entscheidungsproblem (see Hilbert and Bernays 1939), the decision problem for first order logic, was one such issue. It was solved negatively -- relative to the precise notion of recursiveness, respectively to Turing machine computability; though obtained independently by Church and Turing, this result is usually called Church's theorem. A second significant issue was the formulation of Gödel's Incompleteness theorems as applying to all formal theories (satisfying certain representability and derivability conditions). Gödel had established the theorems in his ground-breaking 1931 paper for specific formal systems like type theory of Principia Mathematica or Zermelo-Fraenkel set theory. The general formulation required a convincing characterization of "formality" (see FORMAL SYSTEMS.
According to Kleene (1981) and Rosser (1984), Church proposed in late 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 subsequent Princeton Lectures Gödel defined the concept of a (general) recursive function using an equational calculus, but he was not convinced that all effectively calculable functions would fall under it. The proof of the equivalence between l-definability and recursiveness (found by Church and Kleene in early 1935) led to Church's first published formulation of the thesis as quoted above; it was reiterated in Church's 1936 paper. Turing also introduced in 1936 his notion of computability by machines. Post's 1936 paper contains a model of computation that is strikingly similar to Turing's, but he did not provide any analysis in support of the generality of his model. On the contrary, 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 classical papers of Gödel, Church, Turing, Post, and Kleene are all reprinted in Davis 1965, and good historical accounts can be found in Davis 1982, Gandy 1988, and Sieg 1994.
Church (1936) presented 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 and in a logic, were considered by Church. In either case, the steps taken in determining function values have to be effective; if the effectiveness of steps is taken to mean recursiveness, then the function can be proved to be recursive. This requirement on steps in Church's argument corresponds to one of the "recursiveness conditions" formulated by Hilbert and Bernays (1939). That condition is used in their characterization of functions that are evaluated according to rules in a deductive formalism: it requires the proof predicate for a deductive formalism to be primitive recursive. Hilbert and Bernays show that all such "reckonable" functions are recursive and actually can be evaluated in a very restricted number theoretic formalism. Thus, in any formalism that satisfies the recursiveness conditions and contains this minimal number theoretic system, one can compute exactly the recursive functions. Recursiveness or computability consequently has, as Gödel emphasized, an absoluteness property not shared by other metamathematical notions like provability or definability; the latter notions depend on the formalism considered.
All such indirect and ultimately unsatisfactory considerations were bypassed by Turing. He focused directly on the fact that human mechanical calculability on symbolic configurations was the intended notion. Analyzing the processes that underlie such calculations (by a computer), Turing was led to certain boundedness and locality conditions. To start with, he demanded the immediate recognizability of symbolic configurations so that basic computation steps need not be further subdivided. This demand and the evident limitation of the computor's sensory apparatus motivate the conditions. Turing also required that the computor proceed deterministically. The above conditions, somewhat hidden in Turing's 1936 paper, are here formulated following Sieg (1994); first the boundedness conditions:
Because the behavior of the computor is uniquely determined by the finitely many combinations of symbolic configurations and internal states, he can carry out only finitely many different operations. These operations are restricted by the locality conditions:
Thus, on closer inspection, Turing's thesis is seen as the result of a two-part analysis. The first part yields the above conditions and Turing's central thesis, that any mechanical procedure can be carried out by a computor satisfying these conditions. The second part argues that any number theoretic function calculable by such a computor is computable by a Turing machine. Both Church and Gödel found Turing's analysis convincing; indeed, Church wrote (1937) that Turing's notion makes "the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately." From a strictly mathematical point, the analysis leaves out important steps, and the claim that is actually established is the more modest one that Turing machines operating on strings can be simulated by machines operating on single letters; a way of generalizing Turing's argument is presented in Sieg and Byrnes (1996).
Two final remarks are in order. First, all the arguments for the thesis take for granted that the effective procedures are being carried out by human beings. Gandy, by contrast, analyzed in his 1980 paper machine computability; that notion crucially involves parallelism. Gandy's mathematical model nevertheless computes only recursive functions. Second, the effective procedures are taken to be mechanical, not general cognitive ones -- as claimed by Webb and many others. Also, Gödel was wrong when asserting in a brief note from 1972 that Turing intended to show in his 1936 paper that "mental procedures cannot go beyond mechanical procedures." Turing, quite explicitly, had no such intentions; even after having been engaged in the issues surrounding machine intelligence, he emphasized in his 1953 paper that the precise concepts (recursiveness, Turing computability) are to capture the mechanical processes that can be carried out by human beings.
Church, A. (1935). An unsolvable problem of elementary number theory (abstract). Bulletin of the Amer. Math. Soc. 41:332-333.
Church, A. (1936). An unsolvable problem of elementary number theory. Amer. J. Math. 58:345-363.
Church, A. (1937). Review of Turing (1936). J. Symbolic Logic 2:42-43.
Davis, M., Ed. (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press.
Davis, M. (1982). Why Gödel didn't have Church's Thesis. Information and Control 54:3-24.
Gandy, R. (1980). Church's Thesis and principles for mechanisms. In Barwise, Keisler, and Kunen, Eds., The Kleene Symposium. North-Holland, pp. 123-148.
Gandy, R. (1988). The confluence of ideas in 1936. In R. Herken, Ed., The Universal Turing Machine. Oxford University Press, pp. 55-111.
Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. In Collected Works I. Oxford: Oxford University Press, 1986, pp. 144-195.
Gödel, K. (1934). On undecidable propositions of formal mathematical systems (Princeton Lectures). In Collected Works I. Oxford: Oxford University Press, 1986, pp. 346-369.
Gödel, K. (1972). A philosophical error in Turing's work. In Collected Works II. Oxford: Oxford University Press, 1986, pp. 306.
Gödel, K. (1986). Collected Works. Three volumes. S. Feferman et al., Eds. Oxford: Oxford University Press.
Hilbert, D., and P. Bernays. (1939). Grundlagen der Mathematik, vol. 2. Springer Verlag.
Kleene, S. (1952). Introduction to Metamathematics. Wolters-Noordhoff.
Kleene, S. (1981). Origins of recursive function theory. Annals Hist. Computing 3:52-66.
Newell, A. (1980). Physical symbol systems. Cognitive Science 2:135-184.
Post, E. (1936). Finite combinatory processes. Formulation 1. J. Symbolic Logic 1:103-105.
Rosser, B. (1984). Highlights of the history of the lambda-calculus. Annals Hist. Computing 6:337-349.
Sieg, W. (1994). Mechanical procedures and mathematical experience. In A. George, Ed., Mathematics and Mind. Oxford: Oxford University Press, pp. 71-117.
Sieg, W., and J. Byrnes. (1996). K-graph machines: generalizing Turing's machines and arguments. In P. Hájek, Ed., Lecture Notes in Logic 6. Springer Verlag, pp. 98-119.
Turing, A. (1936). On computable numbers, with an application to the Entscheidungsproblem. Reprinted in M. Davis, Ed., (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press.
Turing, A. (1948). Intelligent Machinery. In D. C. Ince, Ed., Collected Works of A. M. Turing: Mechanical Intelligence. North-Holland, pp. 107-127.
Turing, A. (1950). Computing machinery and intelligence. Mind 59:433-460.
Turing, A. (1953). Solvable and unsolvable problems. Science News 31:7-23.
van Heijenoort, J. (1967). From Frege to Gödel. Cambridge, MA: Harvard University Press.
Webb, J. C. (1980). Mechanism, Mentalism, and Metamathematics. Reidel.
Webb, J. C. (1990). Introductory note to Gödel (1972). In Collected Works II. Oxford: Oxford University Press, 1986, pp. 292-304.
Hilbert, D., and W. Ackermann. (1928). Grundzüge der theoretichen Logik. Springer Verlag.
Mundici, D., and W. Sieg. (1995). Paper machines. Philosophia Mathematica 3:5-30.
Post, E. (1947). Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12:1-11.
Sieg, W. (1997). Step by recursive step: Church's analysis of effective calculability. Bulletin of Symbolic Logic 3:154-180.
Soare, R. (1996). Computability and recursion. Bulletin of Sym bolic Logic 2:284-321.
Copyright © 1999 Massachusetts Institute of Technology