Using almost-everywhere theorems from analysis to study randomness

ResearchSpace/Manakin Repository

Show simple item record Miyabe, K en Nies, Andre en Zhang, J en 2017-01-05T02:52:01Z en 2016-09 en
dc.identifier.citation The Bulletin of Symbolic Logic 22(03):305-331 Sep 2016 en
dc.identifier.issn 1079-8986 en
dc.identifier.uri en
dc.description.abstract We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin-Löf (ML) randomness. We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent. (1) all effectively closed classes containing z have density 1 at z. (2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z. (3) z is a Lebesgue point of each lower semicomputable integrable function. We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff's pointwise ergodic theorem. Lastly, we study randomness notions related to density of and classes at a real. en
dc.publisher Association for Symbolic Logic en
dc.relation.ispartofseries The Bulletin of Symbolic Logic en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from en
dc.rights.uri en
dc.title Using almost-everywhere theorems from analysis to study randomness en
dc.type Journal Article en
dc.identifier.doi 10.1017/bsl.2016.10 en
pubs.issue 03 en
pubs.begin-page 305 en
pubs.volume 22 en
dc.description.version AM - Accepted Manuscript en
dc.rights.holder Copyright: Association for Symbolic Logic en
pubs.end-page 331 en
pubs.publication-status Published en
dc.rights.accessrights en
pubs.subtype Article en
pubs.elements-id 544603 en Science en School of Computer Science en
dc.identifier.eissn 1943-5894 en
pubs.record-created-at-source-date 2017-01-05 en 2016-10-10 en

Full text options

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace

Advanced Search