CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS.
We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativizatio...
| Publicado en: | Journal of Symbolic Logic Vol. 79; no. 2; pp. 526 - 561 |
|---|---|
| Autores principales: | , , , , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Jun2014
|
| 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=97059208&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 97059208 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Jun2014 vid: 79 iid: 2 pid: 15979 pub: Cambridge University Press artinfo: ui: 97059208 10.1017/jsl.2013.21 ppf: 526 ppct: 35 formats: tig: atl: CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS. aug: au: BIENVENU, LAURENT DOWNEY, ROD GREENBERG, NOAM NIES, ANDRÉ TURETSKY, DAN affil: LIAFA, CNRS & UNIVERSITY OF PARIS 7, PARIS, FRANCE SCHOOL OF MATHEMATICS, STATISTICS AND OPERATIONS RESEARCH, VICTORIA UNIVERSITY OF WELLINGTON, WELLINGTON, NEW ZEALAND DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF AUCKLAND, PRIVATE BAG 92019, AUCKLAND, NEW ZEALAND KURT GÖDEL RESEARCH FOR MATHEMATICAL LOGIC, UNIVERSITY OF VIENNA, VIENNA, AUSTRIA su: Set theory Computable functions Algorithmic randomness Turing machines Random sets sug: subj: Set theory Computable functions Algorithmic randomness Turing machines Random sets keyword: Demuth randomness lowness partial relativization ab: We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2014 holdings: @attributes: islocal: N |
|---|