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: published 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 set in Δ02 has Δ02-dimension 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.