USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS.
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 slightl...
| Publicado en: | Bulletin of Symbolic Logic Vol. 22; no. 3; pp. 305 - 332 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Sep2016
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=118689617&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 118689617 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 10798986 1BA jtl: Bulletin of Symbolic Logic issn: 10798986 maglogo: N pubinfo: dt: Sep2016 vid: 22 iid: 3 pid: 15979 pub: Cambridge University Press artinfo: ui: 118689617 10.1017/bsl.2016.10 ppf: 305 ppct: 27 formats: tig: atl: USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS. aug: au: MIYABE, KENSHI NIES, ANDRÉ ZHANG, JING affil: DEPARTMENT OF MATHEMATICS SCHOOL OF SCIENCE AND TECHNOLOGY MEIJI UNIVERSITY, JAPAN E-mail: kenshi.miyabe@gmail.com DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF AUCKLAND, NEW ZEALAND E-mail: andre@cs.auckland.ac.nz DEPARTMENT OF MATHEMATICAL SCIENCES CARNEGIE MELLON UNIVERSITY, USA E-mail: jingzhang@cmu.edu su: Ergodic theory Random data (Statistics) Random effects model Birkhoff's theorem (Relativity) Relativistic theorems (Relativity) Random dynamical systems sug: subj: Ergodic theory Random data (Statistics) Random effects model Birkhoff's theorem (Relativity) Relativistic theorems (Relativity) Random dynamical systems keyword: almost-everywhere theorem ergodic theory Lebesgue density randomness ab: 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 ${\rm{\Pi }}_n^0$ and ${\rm{\Sigma }}_1^1$ classes at a real. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|