Limit Computability and Constructive Measure
Status: published in Chong, Feng, Slaman, Woodin, and Yang (eds.),
of Infinity, Part II: Presented Talks, Lecture Notes Series,
Sciences, National University of Singapore, Vol. 15, World Scientific
2008, 131 - 141.
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
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.