Limit Computability and Constructive Measure
Status: to appear in the proceedings of the Program on Computational
Prospects of Infinity, Singapore 2005.
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