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.)
Full Text: