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
Computability theory, algorithmic randomness and Turing's anticipation
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. This article looks at the applications of Turing's legacy in computation, particularly to the theory of algorithmic randomness, where classical mathematical concepts such as measure could be made computational. It also traces Turing's anticipation of this theory in an early manuscript.
§1. Introduction. Beginning with the work of Church, Kleene, Post and particularly Turing, especially in the magic year of 1936, we know what computation means. Turing's theory has substantially developed under the names of recursion theory and computability theory. Turing's work can be seen as perhaps the high point in the confluence of ideas in 1936. This paper, and Turing's 1939 paper [141] (based on his PhD Thesis of the same name), laid solid foundations to the pure theory of computation. This article gives a brief history of some of the main lines of investigation in computability theory, a major part of Turing's legacy.
Computability theory and its tools for classifying computational tasks have seen applications in many areas such as analysis, algebra, logic, computer science and the like. Such applications will be discussed in articles in this volume. The theory even has applications into what is thought of as proof theory in what is called reverse mathematics. Reverse mathematics attempts to calibrate the logical strength of theorems of mathematics according to calibrations of comprehension axioms in second order mathematics. Generally speaking most separations, that is, proofs that a theorem is true in one system but not another, are performed in normal “ω” models rather than nonstandard ones.
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 90 - 123Publisher: Cambridge University PressPrint publication year: 2014