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 are motivated by reductions between Π2 principles in the context of reverse mathematics (where some of our results have already been applied, in the work of Hirschfeldt and Jockusch [3]), and also encompasses generic and coarse reducibilities (previously studied by Jockusch

Locations

• Computability - View
• arXiv (Cornell University) - View - PDF