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
Autor principal: Figueira, Santiago Daniel
Publicado: 2010
Materias:
Lower bounds
Random set
Random processes
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6158LNCS_n_p162_Figueira
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 paper:paper_03029743_v6158LNCS_n_p162_Figueira
record_format dspace
spelling paper:paper_03029743_v6158LNCS_n_p162_Figueira2023-06-08T15:28:36Z Counting the changes of random Δ02 sets Figueira, Santiago Daniel 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. 2010 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6158LNCS_n_p162_Figueira 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, Santiago Daniel
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.
author Figueira, Santiago Daniel
author_facet Figueira, Santiago Daniel
author_sort Figueira, Santiago Daniel
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
publishDate 2010
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6158LNCS_n_p162_Figueira
http://hdl.handle.net/20.500.12110/paper_03029743_v6158LNCS_n_p162_Figueira
work_keys_str_mv AT figueirasantiagodaniel countingthechangesofrandomd02sets
_version_ 1768546348691357696

Ejemplares similares