Church, Alonzo

Latest revision as of 08:20, 23 July 2023

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.

@@ Line 1: / Line 1: @@
-{{claimed}}
+{{Approved}}{{Images OK}}{{Submitted}}{{Paid}}{{copyedited}}
+{{epname|Church, Alonzo}}
-[[Image:Alonzo Church.jpg|thumb|250px|Alonzo Church (1903-1995)]]
+'''Alonzo Church''' (June 14, 1903 – August 11, 1995) was an [[United States|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]].
+{{toc}}
-'''Alonzo Church''' (June 14, 1903 – August 11, 1995) was an [[United States|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 spaces are available. This thesis provided a foundational basis for theoretical [[computer science]]. Other relevant results made by him are the proof of the [[decision problem|undecidablility]] of ''Peano arithmetic'' and [[formal logic|first-order logic]] (The latter result is known as Church's theorem) and the creation of the ''lambda calculus''.
+Other relevant contributions by Church are the proofs of the [[decision problem|undecidablility]] of ''Peano arithmetic'' and [[formal logic|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 postdoc 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.
+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. See [http://www.math.ucla.edu/~asl/bsl/0104/0104-005.ps].
+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.
-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.
-===Church's Main Accomplishments and Relevant History===
+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."
-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, '''Alonzo 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."
-Independently, shortly after Church's result, in 1936, [[Alan Turing]] tried to capture the notion with the introduction of [[Alan Turing|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:
+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.
-:"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 [[Alan Turing|Turing machine]], Stephen Kleene (1952) added to the list the functions "''reckonable'' in the system S<sub>1</sub>" 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).
-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 [[Alan Turing|Turing machine]], Stephen Kleene (1952) added to the list the functions " ''reckonable'' in the system S<sub>1</sub>" of [[Kurt Gödel]] 1936, and Emil Post's (1943, 1946) "''canonical'' [also called ''normal''] ''systems''" (cf Kleene (1952) 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 (2000), 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 basic idea of the thesis is that any possible computation can be performed by a program running on a very simple computer called ''[[Alan Turing|Turing-machine]]'', provided that sufficient time and storage space are available.
+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:
-Informally the '''Church–Turing thesis''' states that our notion of [[algorithm]] can be made precise and computers can run those algorithms. Furthermore, a computer can theoretically run any algorithm; in other words, all ordinary computers are equivalent to each other in terms of theoretical computational power, and it is not possible to build a calculation device that is more powerful than the simplest computer (a [[Turing machine]]).  Note that this formulation of power disregards practical factors such as speed or memory capacity; it considers all that is theoretically possible, given unlimited time and memory.
+<blockquote>Every function which would naturally be regarded as computable can be computed by a [[Alan Turing|Turing machine]].</blockquote>
-===Formal statement===
+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.
-The thesis can be stated as:
+==References==
+*Bernstein, E. & U. Vazirani. "Quantum Complexity Theory." ''SIAM Journal on Computing.'' 26(5) (1997) 1411-1473
-:''"Every '[[function (mathematics)|function]] which would naturally be regarded as [[computable function|computable]]' can be computed by a [[Turing machine]]."''
+*Blass, Andreas and Yuri Gurevich. [http://research.microsoft.com/~gurevich/Opera/164.pdf 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.
-The term '''effectively calculable''' is commonly used for a function that is naturally regarded as computable, for example one for which an algorithm is provided.  Due to the vagueness of the concept of effective calculability, the Church&ndash;Turing thesis cannot formally be proven.  "Disproof" would be possible only if humanity found ways of building [[hypercomputer]]s whose results are accepted as "computable"; as such, the thesis, although referencing mathematical objects, is properly in the realm of science rather than mathematics.
+*--------, 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.
-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.
+*--------, 1941. ''The Calculi of Lambda-Conversion.'' Princeton: Princeton University Press.
+*--------, 1996. ''Introduction to Mathematical Logic.'' Princeton, N.J.: Princeton University Press. ISBN 0691029067
-Variations of the thesis exist; for example, the Physical Church–Turing thesis (PCTT) states:
+*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.
-:''"Every function that can be physically computed can be computed by a Turing machine."''
+*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.
-<!-- is only valid for an idealized mathematical model and not (necessarily) for reality: —> <!-- This stronger statement may have been proven false in [[2002]] when [[Willem Fouché]] discovered that a Turing machine probably cannot effectively approximate any of the values of one-dimensional [[Brownian motion]] at rational points in time (with respect to [[Wiener measure]]; see reference below).—> <!— This isn't an objection, since the values cannot be physically measured with arbitrary precision anyways, so you haven't given a mechanical means of producing non Turing-computable functions. —>
+*Gurevich, Yuri. 1988. ''On Kolmogorov Machines and Related Issues.'' Bulletin of European Assoc. for Theor. Comp. Science, Number 35, June 1988, 71-82.
-Another variation is the Strong Church–Turing Thesis (SCTT), which is not due to Church or Turing, but rather was realized gradually in the development of [[complexity theory]].  It states (cf. Bernstein, Vazirani 1997):
+*Gurevich, Yuri. [http://research.microsoft.com/~gurevich/Opera/141.pdf 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.
-:''"Any 'reasonable' model of computation can be efficiently simulated on a [[probabilistic Turing machine]]."''
+*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. "[http://www.abelard.org/turpap2/tp2-ie.asp 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.
-The word 'efficiently' here means up to polynomial-time reductions. The Strong Church–Turing Thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time.  Assuming the conjecture that probabilistic polynomial time ([[BPP]]) equals deterministic polynomial time ([[P_(complexity)|P]]), the word 'probabilistic' is optional in the Strong Church–Turing Thesis.
+== External links ==
+All links retrieved July 23, 2023.
-If [[quantum computing|quantum computers]] are physically possible, they could invalidate the Strong Church–Turing Thesis, since it is also conjectured that quantum polynomial time ([[BQP]]) is larger than BPP.  In other words, there are efficient [[quantum algorithms]] that perform tasks that are not known to have efficient [[probabilistic algorithms]]; for example, factoring integers.
+*[http://plato.stanford.edu/entries/church-turing/ Detailed info on the Church–Turing Hypothesis] (Stanford Encyclopedia of Philosophy).
-===Philosophical implications===
+===General philosophy sources===
-The Church–Turing thesis has been alleged to have some profound implications for the [[philosophy of mind]]. There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of [[hypercomputation]]. When applied to physics, the thesis has several possible meanings:
-#The universe is equivalent to a Turing machine or is weaker; thus, computing non-recursive functions is physically impossible.  This has also been termed the ''strong Church–Turing thesis'' (not to be confused with the previously mentioned SCTT) and is a foundation of [[digital physics]].
-#The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a [[hypercomputation|hypercomputer]].  For example, a universe in which physics involves [[real numbers]], as opposed to [[computable number|computable real]]s, might fall into this category.
-#The universe is a [[hypercomputation|hypercomputer]], and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all [[quantum mechanics|quantum mechanical]] events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines.  (They are not necessarily efficiently equivalent; see above.)  [[John Lucas (philosopher)|John Lucas]] and, more famously, [[Roger Penrose]] have suggested that the human mind might be the result of quantum hypercomputation, although there is no scientific evidence for this proposal.
-There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
-=== Non computable functions ===
-One can formally define functions that are not computable. For example, there are functions on natural numbers that produce values, usually very large values, that cannot be computed. The most famous such function is the [[busy beaver]]. To make things simple, let us say that it describes the largest amount of work that a [[Turing machine]] can produce with limited resources (i.e., no more than ''n'' states). At best, researchers can give lower bounds for the ''busy beaver'' function for the smallest values of ''n'':  2, 3, 4, 5, and (painfully) 6 states.
-The basic problem is that to calculate the ''n''th ''busy beaver'' number, you have to run every possible n-state Turing machine and see which one does the most work before stopping.  To make matters worse, many Turing machines never stop at all — and for some of those it's impossible to know in advance whether they will stop or not.  This last connection to the [[halting problem]] makes computing the ''busy beaver'' function theoretically impossible, rather than merely impractical.
-== See also ==
-* [[Church-Turing thesis]]
-* [[Church-Turing-Deutsch principle]]
-* [[Higher-order logic]]
-==References==
-*Bernstein, E. & Vazirani, U. ''Quantum complexity theory'', SIAM Journal on Computing 26(5) (1997) 1411?1473
-*[[Andreas Blass]] and [[Yuri Gurevich]] (2003), [http://research.microsoft.com/~gurevich/Opera/164.pdf ''Algorithms: A Quest for Absolute Definitions''], Bulletin of European Association for Theoretical Computer Science 81, 2003. Includes an excellent bibliography of 56 references.
-*Church, Alonzo. 1932, "A set of Postulates for the Foundation of Logic", ''Annals of Mathematics'', second series, 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 landmarks in mathematics and physics. Princeton, N.J.: Princeton University Press. ISBN 0691029067 ISBN 9780691029061
-* [[Martin Davis]] editor, ''The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions'', Raven Press, New York, 1965. All the original papers are here including those by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section. Valuable commentary by Davis prefaces most papers.
-*[[Robin Gandy]], 1980, ''Church's Thesis and the Principles for Mechanisms'', reprinted in H.J. Barwise, H.J. Keisler and K. Kunen, eds., (1980), ''The Kleene Symposium'', North-Holland Publishing Company, pp. 123-148.
-*[[Kurt Gödel|Gödel, K.]], 1934, ''On Undecidable Propositions of Formal Mathematical Systems'', lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, ''The Undecidable'', New York: Raven Press.
-*[[Kurt Gödel|Gödel, K.]], 1936, "On The Length of Proofs", reprinted in Davis, M. (ed.) 1965, ''The Undecidable'', New York: Raven Press (pp.82-83), "Translated by the editor from the original article in ''Ergenbnisse eines mathematishen Kolloquiums'', Heft 7 (1936) pp. 23-24." Cited by Kleene (1952) as "Über die Lāange von Beweisen", in ''Ergebnisse eines math. Koll'', etc.
-*[[Yuri Gurevich]], 1988, ''On Kolmogorov Machines and Related Issues'', Bulletin of European Assoc. for Theor. Comp. Science, Number 35, June 1988, 71-82.
-*[[Yuri Gurevich]], [http://research.microsoft.com/~gurevich/Opera/141.pdf ''Sequential Abstract State Machines Capture Sequential Algorithms''], ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pages 77-111. Includes bibliography of 33 sources.
-*[[Jacques Herbrand|Herbrand, J.]], 1932, "Sur la non-contradiction de l'arithmétique", ''Journal fur die reine und angewandte Mathematik'', 166, 1-8.
-*[[Douglas Hofstadter|Hofstadter, Douglas R.]],  ''[[Gödel, Escher, Bach: an Eternal Golden Braid]]'', Chapter 17.
-*[[Stephen Cole Kleene|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.
-*[[Andrey Markov|Markov, A.A.]], 1960, "The Theory of Algorithms", ''American Mathematical Society Translations'', series 2, 15, 1-14. [[A. A. Markov]] (1954) ''Theory of algorithms''. Also: [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e. Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
-*Pour-El, M.B. & Richards, J.I., 1989, ''Computability in Analysis and Physics'', [[Springer Verlag]].
-*[[Robert Soare]], (1995-6), ''Computability and Recursion'', Bulletin of Symbolic Logic 2 (1996), 284—321.
-*[[Alan Turing|Turing, A.M.]], 1936, "[http://www.abelard.org/turpap2/tp2-ie.asp On Computable Numbers, with an Application to the Entscheidungsproblem]", ''Proceedings of the London Mathematical Society'', Series 2, 42 (1936-37), pp.230-265.
-== Sources and external links ==
+*[http://plato.stanford.edu/ Stanford Encyclopedia of Philosophy].
-* {{MacTutor Biography|id=Church}}
+*[http://www.iep.utm.edu/ The Internet Encyclopedia of Philosophy].
-* [http://www.math.ucla.edu/~asl/bsl/0104/0104-005.ps H B Enderton, In memoriam: Alonzo Church]
+*[http://www.bu.edu/wcp/PaidArch.html Paideia Project Online].
-* {{MathGenealogy|id=8011}}
+*[http://www.gutenberg.org/ Project Gutenberg].
-*[http://libweb.princeton.edu/libraries/firestone/rbsc/finding_aids/mathoral/pmcxrota.htm "Fine Hall in its golden age: Remembrances of Princeton in the early fifties" by Gian-Carlo Rota.] Contains a section on Church at Princeton.
-*[http://libweb.princeton.edu/libraries/firestone/rbsc/finding_aids/mathoral/pmc05.htm Interview of Church about his time at Princeton]
-*[http://libweb.princeton.edu/libraries/firestone/rbsc/aids/church/ Archived papers]
-*[http://plato.stanford.edu/entries/church-turing/ Detailed info on the Church–Turing Hypothesis] (Stanford Encyclopedia of Philosophy)
-===General Philosophy Sources===
-*[http://plato.stanford.edu/ Stanford Encyclopedia of Philosophy]. Retrieved July 14, 2007.
-*[http://www.iep.utm.edu/ The Internet Encyclopedia of Philosophy]. Retrieved July 14, 2007.
-*[http://www.epistemelinks.com/  Philosophy Sources on Internet EpistemeLinks]. Retrieved July 14, 2007.
-*[http://www.earlham.edu/~peters/gpi/index.htm Guide to Philosophy on the Internet]. Retrieved July 14, 2007.
-*[http://www.bu.edu/wcp/PaidArch.html Paideia Project Online]. Retrieved July 14, 2007.
-*[http://www.gutenberg.org/ Project Gutenberg]. Retrieved July 14, 2007.
-[[category:Philosophy and religion]]
+[[Category:philosophers]]
-[[Category:philosophy]]
+[[Category:mathematicians]]
-{{academia
-|teachers=[[Oswald Veblen]]
-|students=[[C. Anthony Anderson]]<br/>[[Peter Andrews]]<br/>[[George Alfred Barnard]]<br/>[[Martin Davis]]<br/>[[Leon Henkin]]<br/>[[David Kaplan (philosopher)|David Kaplan]]<br/>[[John George Kemeny]]<br/>[[Stephen Kleene]]<br/>[[John McCarthy (computer scientist)]]<br/>[[Michael O. Rabin]]<br/>[[Hartley Rogers, Jr]]<br/>[[J. Barkley Rosser]]<br/>[[Dana Scott]]<br/>[[Raymond Smullyan]]<br/>[[Alan Turing]]
-}}
-{{credits|Alonzo_Church|82046749|Church-Turing_thesis|144929873}}
+{{credits|Alonzo_Church|82046749|Church-Turing_thesis|144929873|Entscheidungsproblem|156525334}}