Notions of robust information coding

Article type: Research Article

Authors: Dzhafarov, Damir D.^a | Igusa, Gregory^b

Affiliations: [a] Department of Mathematics, University of Connecticut, 196 Auditorium Road, Storrs, CT 06269, U.S.A.. damir@math.uconn.edu | [b] Department of Mathematics, University of Notre Dame, 255 Hurley Hall, Notre Dame, IN 46556, U.S.A.. gigusa@nd.edu

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 Π21 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

DOI: 10.3233/COM-160059

Journal: Computability, vol. 6, no. 2, pp. 105-124, 2017