##
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 Delta_{0}^{2} of limit
computable sets. We prove that the lower cone of any Turing-incomplete
set in
Delta_{0}^{2} has Delta_{0}^{2}-dimension
0, and in contrast, that although the upper cone of a noncomputable set in
Delta_{0}^{2} always has
Delta_{0}^{2}-*measure* 0, upper cones in
Delta_{0}^{2} have nonzero
Delta_{0}^{2}-*dimension*. In particular the
Delta_{0}^{2}-dimension of the Turing degree of 0' (the
Halting Problem) is 1. Finally, it is proved that
the low sets do not have Delta_{0}^{2}-measure 0, which
means that the low sets do
not form a small subset of Delta_{0}^{2}.
This result has consequences for the existence of bi-immune sets.

drh@math.uchicago.edu