RANDOMNESS NOTIONS AND REVERSE MATHEMATICS.
We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$ -random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C -incompressible is provable in $...
| Published in: | Journal of Symbolic Logic Vol. 85; no. 1; pp. 271 - 300 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Published: |
Cambridge University Press
Mar2020
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=142723347&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 142723347 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Mar2020 vid: 85 iid: 1 pid: 15979 pub: Cambridge University Press artinfo: ui: 142723347 10.1017/jsl.2019.50 ppf: 271 ppct: 29 formats: tig: atl: RANDOMNESS NOTIONS AND REVERSE MATHEMATICS. aug: au: NIES, ANDRÉ SHAFER, PAUL affil: SCHOOL OF COMPUTER SCIENCE UNIVERSITY OF AUCKLAND PRIVATE BAG, 92019, AUCKLAND, NEW ZEALAND URL: https://www.cs.auckland.ac.nz/~nies/ SCHOOL OF MATHEMATICS UNIVERSITY OF LEEDS LEEDS, LS2 9JT, UK URL: http://www1.maths.leeds.ac.uk/~matpsh/ su: Reverse mathematics Computable functions Algorithmic randomness Kolmogorov complexity Arithmetic sug: subj: Reverse mathematics Computable functions Algorithmic randomness Kolmogorov complexity Arithmetic keyword: 03D32 03F35 68Q30 algorithmic randomness computability theory Primary 03B30 reverse mathematics ab: We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$ -random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C -incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2020 holdings: @attributes: islocal: N |
|---|