RANDOMNESS, RELATIVIZATION AND TURING DEGREES.
We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is MartinLöf random relative to &0slash;(). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incom...
| Publicado en: | Journal of Symbolic Logic Vol. 70; no. 2; pp. 515 - 536 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Jun2005
|
| 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=17237802&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 17237802 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Jun2005 vid: 70 iid: 2 pid: 15979 pub: Cambridge University Press artinfo: ui: 17237802 10.2178/jsl/1120224726 ppf: 515 ppct: 21 formats: tig: atl: RANDOMNESS, RELATIVIZATION AND TURING DEGREES. aug: au: Nies, André Stephan, Frank Terwijn, Sebastian A. affil: Department of Computer Science, University of Auckland, 38 Princes St, New Zealand Departments of Computer Science and Mathematics, National University of Singapore, 3 Science Drive 2, Singapore 117543, Republic of Singapore Institute of Discrete Mathematics and Geometry, Technische Universität Wien, Wiedner Hauptstrasse 8-10/E104, A-1040 Vienna, Austria su: Mathematical logic Mathematical analysis Random sets Set theory Computable functions Recursion theory Computational mathematics sug: subj: Mathematical logic Mathematical analysis Random sets Set theory Computable functions Recursion theory Computational mathematics ab: We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is MartinLöf random relative to &0slash;(). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ ¦x¦ - c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the cast: of time-bounded C-complexity. Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of MartinLöf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2005 holdings: @attributes: islocal: N |
|---|