Publication at Faculty of Mathematics and Physics |
2013
Abstract
We show that every non-low C.E. set joins all Δ-0-2 (Δ^0_2) 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.