Joining non-low C.E. sets with diagonally non-computable functions
Laurent Bienvenu, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies, Daniel D. Turetsky · Journal of Logic and Computation · 2013
We show that every non-low c.e. set joins all Δ20 diagonally non-computable functions to ∅′. We give two proofs: a direct argument, and a proof using an analysis of functions that are DNC relative to an oracle, extending work by Day and Reimann. The latter proof is also presented in the language of Kolmogorov complexity.