Limit Computability and Constructive Measure

by Denis R. Hirschfeldt and Sebastiaan A. Terwijn



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