Notions of robust information coding

Abstract

We introduce and study several notions of computability-theoretic reducibility between subsets of ω 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 notions are motivated by reductions between $Π_{2}^{1}$ principles in the context of reverse mathematics, where some of our results have already been applied, e.g., by Hirschfeldt and Jockusch [to appear]. Our work also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp [J. Lond. Math. Soc. (2) 85(2) (2012), 472–490].

Keywords

Generic computability generic case complexity coarse computability

Get full access to this article

View all access options for this article.

References

P.A.

Cholak and

Igusa, Density-1-bounding and quasiminimality in the generic degrees (to appear).

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer-Verlag, New York, 2010, xxviii + 855 pp.

R.G.

Downey,

C.G.

JockuschJr. and

P.E.

Schupp, Asymptotic density and computably enumerable sets, J. Math. Log. 13(2) (2013), 1350005.

D.D.

Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143(2) (2015), 869–876.

D.R.

Hirschfeldt and

C.G.

JockuschJr., On notions of computability theoretic reduction between

Π_{2}^{1}

principles (to appear).

D.R.

Hirschfeldt,

C.G.

JockuschJr.,

Kuyper and

P.E.

Schupp, Coarse reducibility and algorithmic randomness (to appear).

Igusa, Nonexistence of minimal pairs for generic computability, J. Symbolic Logic 78(2) (2013), 511–522.

Igusa, The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals, J. Symbolic Logic (to appear).

C.G.

JockuschJr. and

P.E.

Schupp, Generic computability, Turing degrees, and asymptotic density, J. Lond. Math. Soc. (2) 85(2) (2012), 472–490.

10.

G.E.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990, xvi + 344 pp.

11.

R.I.

Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, xviii + 437 pp.