Computability theory, algorithmic randomness and Turing's anticipation
Rodney G. Downey · Cambridge University Press eBooks · 2014
. 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.