We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
RANDOMNESS NOTIONS AND REVERSE MATHEMATICS.
- Authors
NIES, ANDRÉ; SHAFER, PAUL
- Abstract
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.
- Subjects
REVERSE mathematics; COMPUTABLE functions; ALGORITHMIC randomness; KOLMOGOROV complexity; ARITHMETIC
- Publication
Journal of Symbolic Logic, 2020, Vol 85, Issue 1, p271
- ISSN
0022-4812
- Publication type
Article
- DOI
10.1017/jsl.2019.50