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: PostScript, DVI, and PDF
Abstract. In this paper we study constructive measure and
dimension in the class Delta02 of limit
computable sets. We prove that the lower cone of any Turing-incomplete
set in
Delta02 has Delta02-dimension
0, and in contrast, that although the upper cone of a noncomputable set in
Delta02 always has
Delta02-measure 0, upper cones in
Delta02 have nonzero
Delta02-dimension. In particular the
Delta02-dimension of the Turing degree of 0' (the
Halting Problem) is 1. Finally, it is proved that
the low sets do not have Delta02-measure 0, which
means that the low sets do
not form a small subset of Delta02.
This result has consequences for the existence of bi-immune sets.
drh@math.uchicago.edu