Cover Image
QR Code

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 $...

Full description

Published in:Journal of Symbolic Logic Vol. 85; no. 1; pp. 271 - 300
Main Authors: NIES, ANDRÉ, SHAFER, PAUL
Format: Article
Published: Cambridge University Press Mar2020
Subjects:
Reverse mathematics
Computable functions
Algorithmic randomness
Kolmogorov complexity
Arithmetic
Online Access:View this record in EBSCOhost

Internet

View this record in EBSCOhost