The typical Turing degree
George Barmpalias, Adam R. Day and Andrew E.M. Lewis
Summary
The Turing degree of a real measures the computational
difficulty of producing its binary
expansion. Since Turing degrees are tailsets, it follows from Kolmogorov's 0-1
law that for any property
which may or may not be satisfied by any given Turing degree, the satisfying
class will either be of
Lebesgue measure 0 or 1, so long as it is measurable. So either the
typical degree satisfies the
property, or else the typical degree satisfies its negation. Further, there is then
some level of randomness
sufficient to ensure typicality in this regard. A similar analysis can be made in
terms of Baire category, where
a standard form of genericity now plays the role that randomness plays in the
context of measure.
We describe and prove a number of results in a programme of research which
aims to establish the
properties of the typical Turing degree, where typicality is gauged either in terms
of Lebesgue measure or
Baire category.