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*:

- (1) (
*B.1*) There is a fixed bound for the number of symbolic configurations a computor can immediately recognize.

- (2) (
*B.2*) There is a fixed bound for the number of a computor's internal states that need to be taken into account.

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:*

- (3)
*(L.1)*Only elements of observed configurations can be changed.

- (4)
*(L.2)*The computor can shift his attention from one symbolic configuration to another only if the second is within a bounded distance from the first.

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.

- ACM Digital Library: Motivating the Church-Turing thesis in the twenty-first century
- CptS 317: The Church/Turing thesis and the Halting Problem
- Kurzweil Technologies, Inc.: Publications
- Luciano Floridi
- The Church-Turing Thesis
- The Church-Turing Thesis

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.