Joining non-low C.E. sets with diagonally non-computable functions

摘要

We show that every non-low c.e. set joins all Δ_2~0 diagonally non-computable functions to 0'. 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.