Publikace na Matematicko-fyzikální fakulta |
2013
Abstrakt
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.