##
Counting the Changes of Random Δ^{0}_{2} Sets

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

Availability: PDF

**Abstract.** We study the number of changes of the initial segment
*Z*_{s} | *n*
for computable approximations of a Martin-Löf random
Δ^{0}_{2} 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 *Z*_{s} | *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
Π^{0}_{1} class has a low
member *Z* with a computable approximation that changes only
*o(2*^{n}) 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
*Z*_{s} | *n*
changes more than *c2*^{n} 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