Counting the changes of random Δ02 sets

Consider a Martin-Löf random Δ02 set Z. We give lower bounds for the number of changes of Zs|n for computable approximations of Z. We show that each nonempty Π0 1 class has a low member Z with a computable approximation that changes only o(2n ) times. We prove that each superlow ML-random set alread...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Figueira, S., Hirschfeldt, D., Miller, J.S., Ng, K.M., Nies, A.
Formato: SER
Materias:
Lower bounds
Random set
Random processes
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v6158LNCS_n_p162_Figueira
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario:Consider a Martin-Löf random Δ02 set Z. We give lower bounds for the number of changes of Zs|n for computable approximations of Z. We show that each nonempty Π0 1 class has a low member Z with a computable approximation that changes only o(2n ) times. We prove that each superlow ML-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 Zs|n changes more than c2 n times. © 2010 Springer-Verlag Berlin Heidelberg.

Ejemplares similares