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 |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=118079295&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 118079295 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Sep2016 vid: 81 iid: 3 pid: 15979 pub: Cambridge University Press artinfo: ui: 118079295 10.1017/jsl.2015.68 ppf: 833 ppct: 23 formats: tig: atl: ON REALS WITH ${\rm{\Delta }}_2^0$-BOUNDED COMPLEXITY AND COMPRESSIVE POWER. aug: au: HERBERT, IAN affil: DEPARTMENT OF MATHEMATICS NATIONAL UNIVERSITY OF SINGAPORE SINGAPORE su: Real numbers Kolmogorov complexity Algorithmic randomness Mathematical inequalities Binary sequences Natural numbers sug: subj: Real numbers Kolmogorov complexity Algorithmic randomness Mathematical inequalities Binary sequences Natural numbers keyword: Algorithmic Randomness K-trivials ab: 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 oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all ${\rm{\Delta }}_2^0$ orders, and call the new notions ${\rm{\Delta }}_2^0$-bounded K-trivial and ${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties of K-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the ${\rm{\Delta }}_2^0$-bounded K-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namely infinitely-often K-triviality and weak lowness for K (in each, the defining inequality must hold up to a constant, but only for infinitely many inputs). We show that ${\rm{\Delta }}_2^0$-bounded K-trivial implies infinitely-often K-trivial, but no implication holds between ${\rm{\Delta }}_2^0$-bounded low for K and weakly low for K. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|