Index Sets of Universal Codes

Abstract

We examine sets of codes such that certain properties are invariant under the choice of oracle from a range of possible oracles and establish a connection between such codes and Medvedev reductions. In examing the complexity of such sets of \emph{universal codes}, we prove completeness results at various levels of the arithmetic hierarchy as well as two general theorems for obtaining ${\Pi }_1^1$-completeness for sets of universal codes. Among other corollaries, we show that the set of codes for Medvedev reductions of bi-immune sets to DNC functions is ${\Pi }_1^1$-complete.

13 pages

Cited by in corpus (1)

• From eventually different functions to pandemic numberings