Limit Computability and Constructive Measure
Status: published in Chong, Feng, Slaman, Woodin, and Yang (eds.),
Computational
Prospects
of Infinity, Part II: Presented Talks, Lecture Notes Series,
Institute for
Mathematical
Sciences, National University of Singapore, Vol. 15, World Scientific
2008, 131 - 141.
Availability: published
version and preprint
Abstract. In this paper we study constructive measure and
dimension in the class Δ02 of limit
computable sets. We prove that the lower cone of any Turing-incomplete
set in
Δ02 has
Δ02-dimension
0, and in contrast, that although the upper cone of a noncomputable set in
Δ02 always has
Δ02-measure 0, upper cones in
Δ02 have nonzero
Δ02-dimension. In particular the
Δ02-dimension of the Turing degree of 0' (the
Halting Problem) is 1. Finally, it is proved that
the low sets do not have Δ02-measure 0, which
means that the low sets do
not form a small subset of Δ02.
This result has consequences for the existence of bi-immune sets.
drh@math.uchicago.edu