Counting the changes of random Δ20 sets
Santiago Figueira, Denis R. Hirschfeldt, Joseph S. Miller, Keng Meng Ng, André Nies · Journal of Logic and Computation · 2013
We study the number of changes of the initial segment Zs ↾n for computable approximations of a Martin-Löf random Δ20 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 introduce a new 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 establish various connections with ω-c.e. tracing and omega;-c.e. jump domination, a new lowness property. We also examine some relationships to randomness theoretic notions of highness, and give applications to the study of (weak) Demuth cuppability.