Coarse reducibility and algorithmic randomness

DOI10.1017/JSL.2015.70zbMATH Open1403.03069arXiv1505.01707OpenAlexW2963133035MaRDI QIDQ2976378FDOQ2976378

Authors: Denis R. Hirschfeldt, Carl G. jun. Jockusch, Rutger Kuyper, Paul E. Schupp 

Publication date: 28 April 2017

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: A coarse description of a subset A of omega is a subset D of omega 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 is a 1-random set which Turing-reduces to 0', 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 Phi such that if D is a coarse description of X, then Phi^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.

Full work available at URL: https://arxiv.org/abs/1505.01707

Recommendations

• Coherence of reducibilities with randomness notions
• Asymptotic density, computable traceability, and 1-randomness
• Asymptotic density and the coarse computability bound
• Density-1-bounding and quasiminimality in the generic degrees
• Computuing \(K\)-trivial sets by incomplete random sets

zbMATH Keywords

algorithmic randomness\(K\)-trivialitycoarse reducibility

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Algorithmic randomness and complexity.
• An inequality related to the isoperimetric inequality
• Generic-case complexity, decision problems in group theory, and random walks.
• Generic computability, Turing degrees, and asymptotic density
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Characterizing the strongly jump-traceable sets via randomness
• Computuing \(K\)-trivial sets by incomplete random sets
• Using random sets as oracles
• A fixed-point-free minimal degree
• Splitting properties and jump classes
• Lowness for genericity
• Asymptotic density, immunity and randomness

Cited In (18)

• Strong Medvedev reducibilities and the KL-randomness problem
• Robustness of average-case meta-complexity via pseudorandomness
• Asymptotic density, computable traceability, and 1-randomness
• Some Questions in Computable Mathematics
• Computing from projections of random points
• Effective Brenier Theorem
• THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY
• Notions of robust information coding
• A minimal pair in the generic degrees
• Lowness, Randomness, and Computable Analysis
• Title not available (Why is that?)
• Coherence of reducibilities with randomness notions
• Proofs of randomized algorithms in Coq
• Asymptotic density and the theory of computability: a partial survey
• Density-1-bounding and quasiminimality in the generic degrees
• Asymptotic density and computability
• Random Oracle Reducibility
• Proofs of Randomized Algorithms in Coq

This page was built for publication: Coarse reducibility and algorithmic randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976378)