Counting the Changes of Random $\Delta^0_2$ Sets

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

LECTURE NOTES IN COMPUTER SCIENCE

Elsevier

Año: 2010 vol. 6158 p. 162 - 171

0302-9743

Consider a Martin-Löf random $Delta^0_2$ set $Z$. We give lower bounds for the number of changes of the first $n$ bits of $Z_s$ for computable approximations of $Z$. We show that each nonempty $Pi^0_1$ class has a low member $Z$ with a computable approximation that changes only $o(2^n)$ times. We prove that each superlow Martin-Löf random set already 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 the first $n$ bits of $Z$ changes more than $c 2^n$ times.