Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Turing and the discovery of computability
Published online by Cambridge University Press: 05 June 2014
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
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 LegacyDevelopments from Turing's Ideas in Logic, pp. 467 - 492Publisher: Cambridge University PressPrint publication year: 2014
References
- 1
- Cited by