Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician whose best-known accomplishment is the proposal about the notion of computability, called the Church-Turing thesis. The basic idea of the thesis is that any computation or calculation that is possible can be performed by an algorithm running on a simple machine (called a Turing machine) provided that sufficient time and storage space are available. This thesis provided a foundational basis for theoretical computer science.

Other relevant contributions by Church are the proofs of the undecidablility of Peano arithmetic and first-order logic (the latter result is known as Church's theorem) and the creation of "lambda calculus."

Life

Alonzo Church was born in Washington, DC, he received a bachelor's degree from Princeton University in 1924, completing his Ph.D. there in 1927, under Oswald Veblen. After a post doctorate at Georg August University of Göttingen, he taught at Princeton, 1929–1967, and at the University of California, Los Angeles, 1967–1990. He was the founding editor of the Journal of Symbolic Logic, editing its reviews section until 1979.

Church's doctoral students were an extraordinarily accomplished lot, including C. Anthony Anderson, Martin Davis, Leon Henkin, John George Kemeny, Stephen Kleene, Michael O. Rabin, Hartley Rogers, Jr, J. Barkley Rosser, Dana Scott, Raymond Smullyan, and Alan Turing.

He died in 1995, and was buried in Princeton Cemetery.

Work

One of the most important problems for logicians in the 1930s was David Hilbert's Entscheidungsproblem. The problem is whether there is an effectively computable program that, for every mathematical statement, will take it as input and return as output either "True" or "False," according to whether it is true or false. The program need not justify its answer, or provide a proof, so long as it is always correct.

Before the question could be answered, the notion of computability had to be formally specified. To do this, Church, with his student Stephen Kleene, invented λ-calculus and introduced the notion of λ-definability. Then he was able to prove that several large classes of functions frequently encountered in number theory were λ-definable, and, armed with this evidence, proposed to Kurt Gödel that one should think of the class of "effectively computable" functions (i.e., functions computable by some concrete algorithm) as the λ-definable functions, and, in his publication in 1936, claimed to solve the Entscheidungsproblem by proving that there was no λ-definable function separating truths from falsehoods. Kurt Gödel, however, was not convinced that this was true, calling the proposal "thoroughly unsatisfactory."

Independently, shortly after Church's result, in 1936, Alan Turing tried to capture the notion with the introduction of Turing machines. He proposed, like Church and Kleene before him, that his formal notion of mechanical computing agent was really the correct one. However, this time Gödel was convinced, writing about Alan Turing's machines: "That this really is the correct definition of mechanical computability was established beyond any doubt by Turing."

By this point, it had been shown that the classes of functions defined by λ-calculus and Turing machines coincided (Turing 1936, 263ff), so the two proposals were essentially identical. However, although Church's claim predated Turing's, it was Turing who, in the opinions of Gödel and others, finally gave a convincing argument for why these functions really contained all functions that one would be inclined to call "effectively computable," and the thesis was gaining acceptance.

Since this time, many other formalisms for describing effective computability had been proposed. To the three most commonly quoted notions specified by the recursive functions, the lambda calculus, and the Turing machine, Stephen Kleene (1952) added to the list the functions "reckonable in the system S₁" of Kurt Gödel (1936) and Emil Post's (1943, 1946) "canonical (also called normal) systems" (Kleene, p. 320). Since Kleene (1952), the various register machines, the various Turing machine-like models such as the Post-Turing machine, combinatory logic, and Markov algorithms have been added to the list. Gurevich adds the pointer machine model of Kolmogorov and Uspensky (1953, 1958). Gandy (1980) proposed four principles "the formulation [of which] is quite abstract, and can be applied to all kinds of automata and to algebraic systems. It is proved that if a device satisfies the principles then its successive states form a computable sequence" (Gurevich, p. 4).

All these systems have been shown to compute the same functions as Turing machines; systems like this are called Turing-complete. Because all these different attempts of formalizing the concept of algorithm have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. However, one should keep in mind that, by principle, the thesis is a definition (of the notion of computability) but not a theorem, and hence cannot be something that can be proved to be true.

Church-Turning thesis

The Church–Turing thesis (also known as Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of computability. The thesis can be stated as:

Every function which would naturally be regarded as computable can be computed by a Turing machine.

Any non-interactive computer program can be translated into a Turing machine, and any Turing machine can be translated into any Turing-complete programming language, so the thesis is equivalent to saying that any Turing-complete programming language is sufficient to express any algorithm. This also means that any solvable problem can therefore be reduced to previously solved problems (the Turing machine instruction set) or by definition is unsolvable.

References
ISBN links support NWE through referral fees

Bernstein, E. & U. Vazirani. "Quantum Complexity Theory." SIAM Journal on Computing. 26(5) (1997) 1411-1473
Blass, Andreas and Yuri Gurevich. Algorithms: A Quest for Absolute Definitions. Bulletin of European Association for Theoretical Computer Science. 81, 2003. Retrieved September 18, 2007.
Church, Alonzo. 1932. "A set of Postulates for the Foundation of Logic." Annals of Mathematics. 33, 346-366.
--------, 1936. "An Unsolvable Problem of Elementary Number Theory." American Journal of Mathematics. 58, 345-363.
--------, 1936. "A Note on the Entscheidungsproblem." Journal of Symbolic Logic. 1, 40-41.
--------, 1941. The Calculi of Lambda-Conversion. Princeton: Princeton University Press.
--------, 1996. Introduction to Mathematical Logic. Princeton, N.J.: Princeton University Press. ISBN 0691029067
Davis, Martin, ed. 1965. The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.
Gandy, Robin. 1980. Church's Thesis and the Principles for Mechanisms. Reprinted in H.J. Barwise, H.J. Keisler and K. Kunen, eds. The Kleene Symposium. North-Holland Publishing Company, pp. 123-148.
Gödel, K. 1934. On Undecidable Propositions of Formal Mathematical Systems. New York: Raven Press.
Gödel, K. 1936. "On The Length of Proofs," reprinted in Davis, M., ed. 1965. The Undecidable. New York: Raven Press.
Gurevich, Yuri. 1988. On Kolmogorov Machines and Related Issues. Bulletin of European Assoc. for Theor. Comp. Science, Number 35, June 1988, 71-82.
Gurevich, Yuri. Sequential Abstract State Machines Capture Sequential Algorithms. ACM Transactions on Computational Logic. Vol 1, no 1 (July 2000): 77-111. Retrieved September 18, 2007.
Herbrand, J. 1932. "Sur la non-contradiction de l'arithmétique." Journal fur die reine und angewandte Mathematik. 166, 1-8.
Hofstadter, Douglas R. Gödel, Escher, Bach: an Eternal Golden Braid.
Kleene, S.C. 1935. "A Theory of Positive Integers in Formal Logic." American Journal of Mathematics. 57, 153-173, 219-244.
Kleene, S.C. 1936. "Lambda-Definability and Recursiveness." Duke Mathematical Journal. 2, 340-353.
Knuth, Donald E. The Art of Computer Programming, Second Edition, Volume 1/Fundamental Algorithms. Addison-Wesley, 1973.
Markov, A.A. 1960. "The Theory of Algorithms." American Mathematical Society Translations. Series 2, 15, 1-14.
Pour-El, M.B. and J.I. Richards. 1989. Computability in Analysis and Physics. Springer Verlag.
Soare, Robert. 1995. Computability and Recursion. Bulletin of Symbolic Logic 2, 284—321.
Turing, A.M. 1936. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society. Series 2, 42 (1936-37), pp.230-265. Retrieved September 18, 2007.

External links

All links retrieved July 23, 2023.

Detailed info on the Church–Turing Hypothesis (Stanford Encyclopedia of Philosophy).

General philosophy sources

Credits

New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:

The history of this article since it was imported to New World Encyclopedia:

History of "Alonzo Church"

Note: Some restrictions may apply to use of individual images which are separately licensed.