Index Sets of Universal Codes

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 $Π_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 $Π_1^1$-complete.

No reviews yet.

No comments yet.