Counting the changes of random $\Delta^0_2$ sets

SANTIAGO FIGUEIRA; DENIS HIRSCHFELDT; JOSEPH S. MILLER; KENG MENG NG; ANDRÉ NIES

JOURNAL OF LOGIC AND COMPUTATION

OXFORD UNIV PRESS

Año: 2015 vol. 25 p. 1073 - 1089

0955-792X

We study the number of changes of the initial segment $Z_s upharpoonright n$ for computable approximations of a ML random $Delta2$ 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 $Z_supharpoonright n$ changes more than $c 2^n$ times. We establish various connections with $omega$-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.