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...
| Publicado en: | Journal of Symbolic Logic Vol. 81; no. 3; pp. 833 - 856 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Sep2016
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |