COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS.
A coarse description of a set A ⊆ ω is a set D ⊆ ω such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in som...
| Publicado en: | Journal of Symbolic Logic Vol. 81; no. 3; pp. 1028 - 1047 |
|---|---|
| Autores principales: | , , , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Sep2016
|
| 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=118079296&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 118079296 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Sep2016 vid: 81 iid: 3 pid: 15979 pub: Cambridge University Press artinfo: ui: 118079296 10.1017/jsl.2015.70 ppf: 1028 ppct: 19 formats: tig: atl: COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS. aug: au: HIRSCHFELDT, DENIS R. JOCKUSCH, CARL G. KUYPER, RUTGER SCHUPP, PAUL E. affil: DEPARTMENT OF MATHEMATICS UNIVERSITY OF CHICAGO CHICAGO, IL, USA. DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN CHAMPAIGN, IL, USA DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN–MADISON MADISON, WI, USA su: Algorithmic randomness Compact spaces (Topology) Random sets Unsolvability (Mathematical logic) Computable functions sug: subj: Algorithmic randomness Compact spaces (Topology) Random sets Unsolvability (Mathematical logic) Computable functions keyword: 03D32 algorithmic randomness Coarse reducibility K-triviality Primary 03D30 Secondary 03D28 ab: A coarse description of a set A ⊆ ω is a set D ⊆ ω such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1-genericity in place of weak 2-randomness. In the other direction, we show that if $A \le _{{\rm{T}}} \emptyset {\rm{'}}$ is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set. We study both uniform and nonuniform notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if there is a Turing functional Φ such that if D is a coarse description of X, then ΦD is a coarse description of Y. A set B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B. We show that a certain natural embedding of the Turing degrees into the coarse degrees (both uniform and nonuniform) is not surjective. We also show that if two sets are mutually weakly 3-random, then their coarse degrees form a minimal pair, in both the uniform and nonuniform cases, but that the same is not true of every pair of relatively 2-random sets, at least in the nonuniform coarse degrees. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|