Skip to main content Accessibility help
×
Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-29T01:41:03.730Z Has data issue: false hasContentIssue false

Turing and the discovery of computability

Published online by Cambridge University Press:  05 June 2014

Robert Irving Soare
Affiliation:
The University of Chicago
Rod Downey
Affiliation:
Victoria University of Wellington
Get access

Summary

Abstract. In §1 we give a short overview for a general audience of Godel, Church, Turing, and the discovery of computability in the 1930s. In the later sections we mention a series of our previous papers where a more detailed analysis of computability, Turing's work, and extensive lists of references can be found. The sections from §2—§9 challenge the conventional wisdom and traditional ideas found in many books and papers on computability theory. They are based on a half century of my study of the subject beginning with Church at Princeton in the 1960s, and on a careful rethinking of these traditional ideas.

The references in all my papers and books are given in the format, author [year], as in Turing [1936], in order that the references are easily identified without consulting the bibliography and are uniform over all papers. A complete bibliography of historical articles from all my books and papers on computabilityis given on the page as explained in §10.

§1. A very brief overview of computability.

1.1. Hilbert's programs. Around 1880 Georg Cantor, a German mathematician, invented naive set theory. A small fraction of this is sometimes taught to elementary school children. It was soon discovered that this naive set theory was inconsistent because it allowed unbounded set formation, such as the set of all sets. David Hilbert, the world's foremost mathematician from 1900 to 1930, defended Cantor's set theory but suggested a formal axiomatic approach to eliminate the inconsistencies. He proposed two programs.

Type
Chapter
Information
Turing's Legacy
Developments from Turing's Ideas in Logic
, pp. 467 - 492
Publisher: Cambridge University Press
Print publication year: 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[Church, 1936] A., Church, An unsolvable problem of elementary number theory, The American Journal of Mathematics, vol. 58 (1936), pp. 345-363.Google Scholar
[Church, 1937a] A., Church, Review of Turing 1936, The Journal of Symbolic Logic, vol. 2 (1937), no. 1, pp. 42-43.Google Scholar
[Church, 1937b] A., Church, Review of Post 1936, The Journal of Symbolic Logic, vol. 2 (1937), no. 1, pp. 43.Google Scholar
[Church, 1956] A., Church, Introduction to mathematical logic, vol. I, Princeton University Press, Princeton, New Jersey, 1956.
[Cooper, 2004] S. B., Cooper, Computablility theory, Chapman & Hall/CRC Mathematics, London, New York, 2004.
[Davis, 1958] M., Davis, Computability and unsolvability, Mc-Graw-Hill, New York, 1958, reprinted in 1982 by Dover Publications.
[Davis, 1965] M., Davis (editor), The undecidable. Basic papers on undecidable propositions, unsolvable problems, and computable functions, Raven Press, Hewlett, New York, 1965.
[Davis, 1982] M., Davis, Why Gödel did not have Church's Thesis, Information and Control, vol. 54 (1982),pp. 3-24.Google Scholar
[Davis, 1988] M., Davis, Mathematical logic and the origin of modern computers, in Herken, [1988], pp. 149-174.
[Downey-Hirschfeldt, 2010] R., Downey and D. R., Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, New York, 2010.
[Feferman, 2006] S., Feferman, Turing's thesis, Notices of the American Mathematical Society, vol. 53, (2006), pp. 1200-1206.Google Scholar
[Gödel, 1931] K., Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I, Monatshefte für Mathematik und Physik, vol. 38, (1931), pp. 173-178, (English translation in Davis [1965], pp. 4–38 and in van Heijenoort [1967], pp. 592–616).Google Scholar
[Gödel, 1934] K., Gödel, On undecidable propositions of formal mathematical systems, Notes by S. C., Kleene and J. B., Rosser on lectures at the Institute for Advanced Study, Princeton, New Jersey, 1934, 30 pp. (reprinted in Davis [1965: 39–74]).
[Gödel, 1946] K., Gödel, Remarks before the Princeton bicentennial conference of problems in mathematics, 1946, reprinted in Davis [1965], pp. 84-88.
[Gödel, 1986] K., Gödel, Collected works Volume I: Publications 1929–1936, (S., Feferman et al., editors), Oxford University Press, Oxford, 1986.
[Gödel, 1990] K., Gödel, Collected works Volume II: Publications 1938–1974, (S., Feferman et al., editors), Oxford University Press, Oxford, 1990.
[Gödel, 1995] K., Gödel, Collected works Volume III: Unpublished essays and lectures, (S., Feferman et al., editors), Oxford University Press, Oxford, 1995.
[Gurevich, 2013] Y., Gurevich, Analyzable and nonanalyzable computations, Turing centenary volume, (Thomas, Strahm and Giovanni, Sommaruga, editors), Birkhäuser/Springer, Basel, 2013, (to appear).
[Herken, 1988] R., Herken (editor), The universal Turing machine: A half-century survey, Oxford University Press, 1988.
[Hopcroft-Ullman] J. E., Hopcroft and J. D., Ullman, Introduction to automata, languages and computation, Addison-Wesley, 1979.
[Kleene, 1936] S. C., Kleene, General recursive functions of natural numbers, Mathematische Annalen, vol. 112, (1936), pp. 727-742.Google Scholar
[Kleene, 1936b] S. C., Kleene, λ-definability and recursiveness, Duke Mathematical Journal, vol. 2, (1936), pp. 340-353.Google Scholar
[Kleene, 1943] S. C., Kleene, Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53, (1943), pp. 41-73.Google Scholar
[Kleene, 1952] S. C., Kleene, Introduction to metamathematics, Van Nostrand, New York, 1952, ninth reprint 1988, Walters-Noordhoff Publishing Company, Groningën and North-Holland, Amsterdam.
[Nies, 2009] A., Nies, Computability and randomness, Oxford University Press, Oxford, UK, 2009.
[Post, 1943] E. L., Post, Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, vol. 65, (1943), pp. 197-215.Google Scholar
[Post, 1944] E. L., Post, Recursively enumerable sets of positive integers and their decision problems, American Mathematical Society. Bulletin, vol. 50, (1944), pp. 284-316.Google Scholar
[Sacks, 2003] G. E., Sacks, Mathematical logic in the 20th century, World Scientific Series in 20th Century Mathematics, vol. 6, Singapore University Press and World Scientific Publishing Co., Singapore, New Jersey, London, Hong Kong, 2003.
[Sieg, 1994] W., Sieg, Mechanical procedures and mathematical experience, Mathematics and mind (A., George, editor), Oxford University Press, 1994, pp. 71-117.
[Soare, 1987] R. I., Soare, Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Springer-Verlag, Heidelberg, 1987.
[Soare, 1996] R. I., Soare, Computability and recursion, The Bulletin of Symbolic Logic, vol. 2, (1996), pp. 284-321.Google Scholar
[Soare, 1999] R. I., Soare, The history and concept of computability, Handbook of computability theory (E. R., Griffor, editor), North-Holland, Amsterdam, 1999, pp. 3-36.
[Soare, 2007] R. I., Soare, Computability and incomputability, computation and logic in the real world, Proceedings of the third conference on Computability in Europe, CiE 2007, Siena, Italy, June 18–23, 2007 (S. B., Cooper, B., Löwe, and Andrea, Sorbi, editors), Lecture Notes in Computer Science, vol. 4497, Springer-Verlag, Berlin, Heidelberg, 2007.
[Soare, 2009] R. I., Soare, Turing oracle machines, online computing, and three displacements in computability theory, Annals of Pure and Applied Logic, vol. 160, (2009), pp. 368-399.Google Scholar
[Soare, 2012a] R. I., Soare, An interview with Robert Soare: Reflections on Alan Turing, published in Crossroads, The ACM Magazine for Students, Association of Computing Machinery, XRDS, Spring 2012, vol. 18 (2012), no. 3, a telephone interview with Robert Soare, transcribed by Arefin Huq, a computer science graduate student at Northwestern University, on December 15, 2011.
[Soare, 2012b] R. I., Soare, Formalism and intuition in computability theory, Philosophical Transactions of the Royal Society A, vol. 370, (2012), pp. 3277-3304.Google Scholar
[Soare, 2013a] R. I., Soare, Turing and the art of classical computability, Alan Turing—his work and impact (Barry, Cooper and Jan, van Leeuwen, editors), Elsevier, 2012, to appear.
[Soare, 2013b] R. I., Soare, Interactive computing and Turing–Post relativized computability, Computability: Gödel, Church, Turing, and beyond (Jack, Copeland, Carl, Posy, and Oron, Shagrir, editors), MIT Press, 2012, to appear.
[Soare, 2013c] R. I., Soare, Why Turing's thesis is not a thesis, Turing centenary volume (Thomas, Strahm and Giovanni, Sommaruga, editors), Birkhäuser/Springer, Basel, 2013, to appear.
[Soare, 2014] R. I., Soare, Turing and the art of classical computability: Theory and applications, Computability in Europe Series, Springer-Verlag, Heidelberg, 2012, to appear.
[Turing, 1936] A. M., Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society. Second Series, vol. 42, (1936), no. 3 and 4, pp. 230-265, reprinted in Davis [1965], pp. 116-154.Google Scholar
[Turing, 1937a] A. M., Turing, A correction, Proceedings of the London Mathematical Society. Second Series, vol. 43, (1937), pp. 544-546.Google Scholar
[Turing, 1937] A. M., Turing, Computability and λ-definability, The Journal of Symbolic Logic, vol. 2, (1937), pp. 153-163.Google Scholar
[Turing, 1939] A. M., Turing, Systems of logic based on ordinals, Proceedings of the London Mathematical Society, vol. 45, (1939), no. 3, pp. 161-228, reprinted in Davis[1965], pp. 154-222.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×