Counting the Changes of Random Δ02 Sets
Status: published in the Journal
of Logic and Computation 25 (2015) 1073 - 1089.
Availability: journal
version and preprint
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.
drh@math.uchicago.edu