pith. sign in

arxiv: 1406.2982 · v1 · pith:PQBZLB3Enew · submitted 2014-06-11 · 🧮 math.LO

Notions of robust information coding

classification 🧮 math.LO
keywords informationnotionspartialrobustavailablecoarsecodingcomputability-theoretic
0
0 comments X
read the original 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 $\Pi^1_2$ principles in the context of reverse mathematics, and also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp (2012).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.