×

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.

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