Counting the changes of random Δ<inf>2</inf>0 sets

We study the number of changes of the initial segment Z<inf>s</inf> ⌈<inf>n</inf> for computable approximations of a Martin-Löf random Δ<inf>2</inf>0 set Z. We establish connections between this number of changes and various notions of computability theoretic lown...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Figueira, S., Hirschfeldt, D.R., Miller, J.S., Ng, K.M., Nies, A.
Formato:	JOUR
Materias:	balanced randomness computable approximation lowness Matin-Löf randomness ω-c.e. jump domination ω-c.e. tracing Formal logic Logic programming Computational power Random set Random processes
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0955792X_v25_n4_p1073_Figueira
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_0955792X_v25_n4_p1073_Figueira
record_format	dspace
spelling	todo:paper_0955792X_v25_n4_p1073_Figueira2023-10-03T15:51:50Z Counting the changes of random Δ<inf>2</inf>0 sets Figueira, S. Hirschfeldt, D.R. Miller, J.S. Ng, K.M. Nies, A. balanced randomness computable approximation lowness Matin-Löf randomness ω-c.e. jump domination ω-c.e. tracing Formal logic Logic programming balanced randomness computable approximation Computational power lowness Random set Random processes We study the number of changes of the initial segment Z<inf>s</inf> ⌈<inf>n</inf> for computable approximations of a Martin-Löf random Δ<inf>2</inf>0 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<inf>s</inf> ⌈<inf>n</inf> changes more than c2n times. We establish various connections with ω-c.e. tracing and ω-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. © The Author, 2013. Published by Oxford University Press. All rights reserved. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0955792X_v25_n4_p1073_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	balanced randomness computable approximation lowness Matin-Löf randomness ω-c.e. jump domination ω-c.e. tracing Formal logic Logic programming balanced randomness computable approximation Computational power lowness Random set Random processes
spellingShingle	balanced randomness computable approximation lowness Matin-Löf randomness ω-c.e. jump domination ω-c.e. tracing Formal logic Logic programming balanced randomness computable approximation Computational power lowness Random set Random processes Figueira, S. Hirschfeldt, D.R. Miller, J.S. Ng, K.M. Nies, A. Counting the changes of random Δ<inf>2</inf>0 sets
topic_facet	balanced randomness computable approximation lowness Matin-Löf randomness ω-c.e. jump domination ω-c.e. tracing Formal logic Logic programming balanced randomness computable approximation Computational power lowness Random set Random processes
description	We study the number of changes of the initial segment Z<inf>s</inf> ⌈<inf>n</inf> for computable approximations of a Martin-Löf random Δ<inf>2</inf>0 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<inf>s</inf> ⌈<inf>n</inf> changes more than c2n times. We establish various connections with ω-c.e. tracing and ω-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. © The Author, 2013. Published by Oxford University Press. All rights reserved.
format	JOUR
author	Figueira, S. Hirschfeldt, D.R. Miller, J.S. Ng, K.M. Nies, A.
author_facet	Figueira, S. Hirschfeldt, D.R. Miller, J.S. Ng, K.M. Nies, A.
author_sort	Figueira, S.
title	Counting the changes of random Δ<inf>2</inf>0 sets
title_short	Counting the changes of random Δ<inf>2</inf>0 sets
title_full	Counting the changes of random Δ<inf>2</inf>0 sets
title_fullStr	Counting the changes of random Δ<inf>2</inf>0 sets
title_full_unstemmed	Counting the changes of random Δ<inf>2</inf>0 sets
title_sort	counting the changes of random δ<inf>2</inf>0 sets
url	http://hdl.handle.net/20.500.12110/paper_0955792X_v25_n4_p1073_Figueira
work_keys_str_mv	AT figueiras countingthechangesofrandomdinf2inf0sets AT hirschfeldtdr countingthechangesofrandomdinf2inf0sets AT millerjs countingthechangesofrandomdinf2inf0sets AT ngkm countingthechangesofrandomdinf2inf0sets AT niesa countingthechangesofrandomdinf2inf0sets
_version_	1807320137935618048

Counting the changes of random Δ<inf>2</inf>0 sets

Ejemplares similares