Cover Image
QR Code

ON REALS WITH ${\rm{\Delta }}_2^0$-BOUNDED COMPLEXITY AND COMPRESSIVE POWER.

The (prefix-free) Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A is K-trivial if its initial segments have the lowest possible complexity and A is low for K if using A as an orac...

Full description

Published in:Journal of Symbolic Logic Vol. 81; no. 3; pp. 833 - 856
Main Author: HERBERT, IAN
Format: Article
Published: Cambridge University Press Sep2016
Subjects:
Real numbers
Kolmogorov complexity
Algorithmic randomness
Mathematical inequalities
Binary sequences
Natural numbers
Online Access:View this record in EBSCOhost

Internet

View this record in EBSCOhost