Counting the Changes of Random Δ02 Sets

by Santiago Figueira, Denis R. Hirschfeldt, Joseph S. Miller, Keng Meng Ng, and André Nies

Status: Journal of Logic and Computation 25 (2015) 1073 - 1089.

Availability: PDF

Abstract. We study the number of changes of the initial segment Zs | n for computable approximations of a Martin-Löf random Δ02 set Z. We establish connections between this number of changes and various notions of computability theoretic lowness, as well as the fundamental thesis that, among random sets, randomness is antithetical to computational power. We first give some lower bounds for the number of changes of Zs | n for computable approximations of Z, and establish a hierarchy theorem: allowing more changes yields new ω-c.e. ML-random sets. We also examine the number of changes of approximations for computably random sets. We then show that each nonempty Π01 class has a low member Z with a computable approximation that changes only o(2n) times, and hence there is a low ML-random set with this property. On the other hand, we prove that every superlow ML-random set satisfies a stronger randomness notion called balanced randomness, which implies that for each computable approximation and each constant c, there are infinitely many n such that Zs | n changes more than c2n times. We also study the notion of being ω-c.e.-tracing introduced by Greenberg and Nies, showing that superlow sets cannot be ω-c.e.-tracing, and that every ML-random set that is not ω-c.e.-tracing is balanced random. We introduce the lowness property of being ω-c.e.-jump dominated, which we show lies strictly between jump traceability and array computability. We extend our result that no superlow set is ω-c.e.-tracing by showing that every superlow set is ω-c.e.-jump dominated, while no set that is ω-c.e.-tracing can be ω-c.e.-jump dominated. We also examine some relationships between being ω-c.e.-tracing, being ω-c.e. jump dominated, and randomness theoretic notions of highness, and give applications to the study of (weak) Demuth cuppability.