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
id todo:paper_03029743_v6158LNCS_n_p162_Figueira
record_format dspace
spelling todo:paper_03029743_v6158LNCS_n_p162_Figueira2023-10-03T15:19:14Z Counting the changes of random Δ02 sets Figueira, S. Hirschfeldt, D. Miller, J.S. Ng, K.M. Nies, A. Lower bounds Random set Random processes 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. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v6158LNCS_n_p162_Figueira
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Lower bounds
Random set
Random processes
spellingShingle Lower bounds
Random set
Random processes
Figueira, S.
Hirschfeldt, D.
Miller, J.S.
Ng, K.M.
Nies, A.
Counting the changes of random Δ02 sets
topic_facet Lower bounds
Random set
Random processes
description 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.
format SER
author Figueira, S.
Hirschfeldt, D.
Miller, J.S.
Ng, K.M.
Nies, A.
author_facet Figueira, S.
Hirschfeldt, D.
Miller, J.S.
Ng, K.M.
Nies, A.
author_sort Figueira, S.
title Counting the changes of random Δ02 sets
title_short Counting the changes of random Δ02 sets
title_full Counting the changes of random Δ02 sets
title_fullStr Counting the changes of random Δ02 sets
title_full_unstemmed Counting the changes of random Δ02 sets
title_sort counting the changes of random δ02 sets
url http://hdl.handle.net/20.500.12110/paper_03029743_v6158LNCS_n_p162_Figueira
work_keys_str_mv AT figueiras countingthechangesofrandomd02sets
AT hirschfeldtd countingthechangesofrandomd02sets
AT millerjs countingthechangesofrandomd02sets
AT ngkm countingthechangesofrandomd02sets
AT niesa countingthechangesofrandomd02sets
_version_ 1807318535228096512

Ejemplares similares