Abstract
The conventional wisdom presented in most computability books and historical papers is that there were several researchers in the early 1930’s working on various precise definitions and demonstrations of a function specified by a finite procedure and that they should all share approximately equal credit. This is incorrect. It was Turing alone who achieved the characterization, in the opinion of Gödel. We also explore Turing’s oracle machine and its analogous properties in analysis.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Church, A.: An unsolvable problem of elementary number theory. American J. of Math. 58, 345–363 (1936)
Church, A.: Review of Turing 1936. J. Symbolic Logic 2(1), 42–43 (1937)
Davis, M.: The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Raven Press, Hewlett, New York (1965)
Davis, M.: Why Gödel did not have Church’s Thesis. Information and Control 54, 3–24 (1982)
Gandy, R.: Church’s thesis and principles for mechanisms. In: The Kleene Symposium, North-Holland, pp. 123–148 (1980)
Gandy, R.: The confluence of ideas in 1936. In: Herken, pp. 55–111 (1988)
Gödel, K.: Über formal unentscheidbare sätze der Principia Mathematica und verwandter systeme. I, Monatsch. Math. Phys. vol. 38 pp. 173–178 (1931) (English trans. in Davis 1965, pp. 4–38, and in van Heijenoort, pp. 592–616 (1967)
Gödel, K.: On undecidable propositions of formal mathematical systems, Notes by Kleene, S.C., Rosser, J.B. (eds.) on lectures at the Institute for Advanced Study, Princeton, New Jersey, 30 pp (Reprinted in Davis 1965 [3, 39–74] (1934)
Gödel, K.: Undecidable diophantine propositions. In: Gödel, pp. 156–175 (1995)
Gödel, K.: Remarks before the Princeton bicentennial conference of problems in mathematics, Reprinted in: Davis 1965 [3], pp. 84–88 (1946)
Gödel, K.: Some basic theorems on the foundations of mathematics and their implications. In: Gödel pp. 304–323 (This was the Gibbs Lecture delivered by Gödel on December 26, 1951 to the Amer. Math. Soc.) (1995)
Gödel, K.: Postscriptum to Gödel 1931, written in 1946, printed in Davis, pp. 71–73 (1965)
Hilbert, D., Ackermann, W.: Grundzüge der theoretischen Logik. In (English translation of 1938 edition, Chelsea, New York, 1950), Springer, Berlin (1928)
Hodges, A.: Alan Turing: The Enigma, Burnett Books and Hutchinson, London, and Simon and Schuster, New York (1983)
Kleene, S.C.: General recursive functions of natural numbers. Math. Ann. 112, 727–742 (1936)
Kleene, S.C.: Recursive predicates and quantifiers. Trans. A.M.S. 53, 41–73 (1943)
Kleene, S.C.: Introduction to Metamathematics, Van Nostrand, New York. Ninth reprint 1988, Walters-Noordhoff Publishing Co., Groningën and North-Holland, Amsterdam (1952)
Kleene, S.C.: Mathematical Logic, London, Sydney. John Wiley and Sons, Inc, New York (1967)
Kleene, S.C.: Origins of recursive function theory. Annals of the History of Computing 3, 52–67 (1981)
Kleene, S.C.: Reflections on Church’s Thesis. Notre Dame. Journal of Formal Logic 28, 490–498 (1987)
Kleene, S.C.: Turing’s analysis of computability, and major applications of it, In: Herken, pp. 17–54 (1988)
Kleene, S.C., Post, E.L.: The upper semi-lattice of degrees of recursive unsolvability. Ann. of Math. 59, 379–407 (1954)
Post, E.L.: Finite combinatory processes–formulation, J. Symbolic Logic vol. 1 pp. 103–105 (1936). Reprinted in Davis, pp. 288–291 (1965)
Post, E.L.: Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. vol. 50, pp. 284–316 (1944). Reprinted in Davis, pp. 304–337 (1965)
Sieg, W.: Mechanical procedures and mathematical experience. In: George, A. (ed.) Mathematics and Mind, Oxford Univ. Press, Oxford (1994)
Soare, R.I.: Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer, Heidelberg (1987)
Soare, R.I.: Computability and recursion. Bulletin of Symbolic Logic 2, 284–321 (1996)
Soare, R.I.: Extensions, Automorphisms, and Definability, In: Cholak, P., Lempp, S., Lerman, M., Shore, R. (eds.) Computability Theory and its Applications: Current Trends and Open Problems, American Mathematical Society, Contemporary Math. #257, American Mathematical Society, Providence, RI, pps. 279–307 (2000)
Soare, R.I.: Computability Theory and Applications, Springer-Verlag, Heidelberg (to appear)
Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. In: Proc. London Math. Soc. ser. 2 vol. 42 (Parts 3 and 4) pp. 230–265 (1936) [Turing, 1937] A correction, ibid. vol. 43, pp. 544–546 (1937)
Turing, A.M.: Systems of logic based on ordinals. In: Proc. London Math. Soc. vol. 45 Part 3 pp. 161–228 (1939) reprinted in Davis, pp. 154–222 (1965)
Zabell, S.L.: Alan Turing and the Central Limit Theorem. American Mathematical Monthly 102(6), 483–494 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Soare, R.I. (2007). Computability and Incomputability. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds) Computation and Logic in the Real World. CiE 2007. Lecture Notes in Computer Science, vol 4497. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73001-9_75
Download citation
DOI: https://doi.org/10.1007/978-3-540-73001-9_75
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73000-2
Online ISBN: 978-3-540-73001-9
eBook Packages: Computer ScienceComputer Science (R0)