Mostrar el registro sencillo del ítem
dc.contributor.author
Figueira, Santiago
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Hirschfeldt, Denis R.
dc.contributor.author
Miller, Joseph S.
dc.contributor.author
Ng, Keng Meng
dc.contributor.author
Nies, André
dc.date.available
2017-12-04T18:40:28Z
dc.date.issued
2013-01
dc.identifier.citation
Figueira, Santiago; Hirschfeldt, Denis R.; Miller, Joseph S.; Ng, Keng Meng; Nies, André; Counting the changes of random Δ20 sets; Oxford University Press; Journal Of Logic And Computation; 25; 4; 1-2013; 1073-1089
dc.identifier.issn
0955-792X
dc.identifier.uri
http://hdl.handle.net/11336/29585
dc.description.abstract
We study the number of changes of the initial segment Zs ↾n for computable approximations of a Martin-Löf random Δ02Δ20 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 Zs ↾n changes more than c2n times. We establish various connections with ω-c.e. tracing and omega;-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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Oxford University Press
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Martin-Löf Randomness
dc.subject
Demuth Randomness
dc.subject
Computable Approximation
dc.subject
Omega-C.E.
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Counting the changes of random Δ20 sets
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2017-05-15T21:08:02Z
dc.identifier.eissn
1465-363X
dc.journal.volume
25
dc.journal.number
4
dc.journal.pagination
1073-1089
dc.journal.pais
Reino Unido
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Oxford
dc.description.fil
Fil: Figueira, Santiago. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Hirschfeldt, Denis R.. University of Chicago; Estados Unidos
dc.description.fil
Fil: Miller, Joseph S.. University of Wisconsin; Estados Unidos
dc.description.fil
Fil: Ng, Keng Meng. Nanyang Technological University; Singapur
dc.description.fil
Fil: Nies, André. The University Of Auckland; Nueva Zelanda
dc.journal.title
Journal Of Logic And Computation
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1093/logcom/exs083
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://academic.oup.com/logcom/article-abstract/25/4/1073/966067
Archivos asociados