Notions of robust information coding
Damir D. Dzhafarov, Gregory Igusa · Computability · 2017
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 [Formula: see text] 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].