Randomness notions and reverse mathematics

Por • 3 sep, 2018 • Sección: Leyes

André Nies, Paul Shafer

We investigate the strength of a randomness notion R as a set-existence principle in second-order arithmetic: for each Z there is X that is R-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in RCA0. We verify that RCA0proves the basic implications among randomness notions: 2-random ⇒ weakly 2-random ⇒ Martin-Lof random ⇒ computably random ⇒ Schnorr random. Also, over RCA0 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-Lof randoms, and we describe a sense in which this result is nearly optimal.

arXiv:1808.02746v1 [math.LO]  Logic (math.LO)

Post to Twitter

Escribe un comentario