zbMATH — the first resource for mathematics

Joining non-low c.e. sets with diagonally non-computable functions. (English) Zbl 1327.03033
Summary: We show that every non-low c.e. set joins all \(\Delta _{2}^{0}\) diagonally non-computable functions to \(\emptyset ^{\prime}\). 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 A. R. Day and J. Reimann [Notre Dame J. Formal Logic 55, No. 1, 1–10 (2014; Zbl 1332.03010)]. The latter proof is also presented in the language of Kolmogorov complexity.

03D25 Recursively (computably) enumerable sets and degrees
03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI