MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY.
By the complexity of a finite sequence of 0's and 1's we mean the Kolmogorov complexity, that is the length of the shortest input to a universal recursive function which returns the given sequence as output. By initial segment complexity of an infinite sequence of 0's and 1's we mean the asymptotic...
| Publicado en: | Journal of Symbolic Logic Vol. 79; no. 1; pp. 20 - 45 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Mar2014
|
| 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=96277379&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 96277379 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Mar2014 vid: 79 iid: 1 pid: 15979 pub: Cambridge University Press artinfo: ui: 96277379 10.1017/jsl.2013.7 ppf: 20 ppct: 25 formats: tig: atl: MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY. aug: au: HUDELSON, W. M. PHILLIP su: Kolmogorov complexity Recursive functions Electronic data processing Information theory Machine theory sug: subj: Kolmogorov complexity Recursive functions Electronic data processing Information theory Machine theory keyword: algorithmic randomness effective Hausdorff dimension Martin-Löf randomness Partial randomness ab: By the complexity of a finite sequence of 0's and 1's we mean the Kolmogorov complexity, that is the length of the shortest input to a universal recursive function which returns the given sequence as output. By initial segment complexity of an infinite sequence of 0's and 1's we mean the asymptotic behavior of the complexity of its finite initial segments. In this paper, we construct infinite sequences of 0's and 1's with given recursive lower bounds on initial segment complexity which do not compute any infinite sequences of 0's and 1's with a significantly larger recursive lower bound on initial segment complexity. This improves several known results about randomness extraction and separates many natural degrees in the lattice of Muchnik degrees. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2014 holdings: @attributes: islocal: N |
|---|