Notions of robust information coding

DOI10.3233/COM-160059MaRDI QIDQ5283443zbMATH OpenFDO

Authors Damir D. Dzhafarov, Gregory Igusa

Publication date 21 July 2017

Published in Computability (Search for Journal in Brave)

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

zbMATH Keywords

coarse computabilitygeneric case complexitygeneric computability

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: We introduce and study several notions of computability-theoretic reducibility between subsets of $omega$ that are "robust" in the sense that if only partial information is available about the oracle, then partial information can be recovered about the output. These are motivated by reductions between $P{i}_2^1$ principles in the context of reverse mathematics, and also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp (2012).

Recommendations

• Computable reductions and reverse mathematics
• On notions of computability-theoretic reduction between Π21 principles
• Coarse reducibility and algorithmic randomness
• Strong reducibility of partial numberings
• Strong Positive Reducibilities

Cites work

• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Cohesive avoidance and strong reductions
• Generic computability, Turing degrees, and asymptotic density
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• Nonexistence of minimal pairs for generic computability

Cited in

(6)

• Asymptotic density and computability
• Asymptotic density and the theory of computability: a partial survey
• On notions of computability-theoretic reduction between Π21 principles
• THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY
• A minimal pair in the generic degrees
• Density-1-bounding and quasiminimality in the generic degrees

This page was built for publication: Notions of robust information coding

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