ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY.
In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence (as shown by Kautz) and every 2-random sequence forms a minimal pair in the Turing degree...
| Publicado en: | Journal of Symbolic Logic Vol. 84; no. 1; pp. 393 - 408 |
|---|---|
| Autores principales: | , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Mar2019
|
| 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=135348251&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 135348251 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Mar2019 vid: 84 iid: 1 pid: 15979 pub: Cambridge University Press artinfo: ui: 135348251 10.1017/jsl.2018.53 ppf: 393 ppct: 15 formats: tig: atl: ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY. aug: au: BIENVENU, LAURENT PORTER, CHRISTOPHER P. affil: LABRI, CNRS & UNIVERSITÉ DE BORDEAUX TALENCE, FRANCE E-mail DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE DRAKE UNIVERSITY DES MOINES, USA E-mail su: Algorithmic randomness Mathematical notation Unsolvability (Mathematical logic) Binary operations Random sets sug: subj: Algorithmic randomness Mathematical notation Unsolvability (Mathematical logic) Binary operations Random sets keyword: algorithmic randomness effective genericity ab: In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence (as shown by Kautz) and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence (as shown by Nies, Stephan, and Terwijn). We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence (where pb-genericity is an effective notion of genericity that is strictly between 1-genericity and 2-genericity). Moreover, we prove that for every comeager G ⊆ 2 , there is some weakly 2-random sequence X that computes some Y ∈ G, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2019 holdings: @attributes: islocal: N |
|---|