LEBESGUE DENSITY AND $\prod _1^0$ CLASSES.
Analyzing the effective content of the Lebesgue density theorem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this inquiry: the positive density points with respect...
| Publicado en: | Journal of Symbolic Logic Vol. 81; no. 1; pp. 80 - 96 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Mar2016
|
| 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=113600893&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 113600893 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Mar2016 vid: 81 iid: 1 pid: 15979 pub: Cambridge University Press artinfo: ui: 113600893 10.1017/jsl.2015.66 ppf: 80 ppct: 16 formats: tig: atl: LEBESGUE DENSITY AND $\prod _1^0$ CLASSES. aug: au: KHAN, MUSHFEQ affil: DEPARTMENT OF MATHEMATICS UNIVERSITY OF HAWAII AT MANOA 2565 MCCARTHY MALL (KELLER HALL 401A) HONOLULU, HAWAII 96822, USA E-mail: khan@math.hawaii.edu su: Algorithmic randomness Mathematics theorems Algorithms Random effects model Computable functions sug: subj: Algorithmic randomness Mathematics theorems Algorithms Random effects model Computable functions keyword: 03D32 03D78 03F60 26E40 effective analysis ab: Analyzing the effective content of the Lebesgue density theorem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this inquiry: the positive density points with respect to effectively closed (or $\prod _1^0$) sets of reals, and a proper subclass, the density-one points. Bienvenu, Hölzl, Miller, and Nies have shown that the Martin-Löf random positive density points are exactly the ones that do not compute the halting problem. Treating this theorem as our starting point, we present several new results that shed light on how density, randomness, and computational strength interact. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|