Diagonally non-computable functions and fireworks

DOI10.1016/J.IC.2016.12.008MaRDI QIDQ515575zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Ludovic Patey

Publication date 16 March 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6846

zbMATH Keywords

diagonally non-computable functionsfireworks argumentsLevin-V'yugin algebranegligibility

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Other Turing degree structures (03D28)

Abstract: A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, the class of coherent completions of Peano Arithmetic or the class of reals of minimal degrees. One class of particular interest in the study of negligibility is the class of diagonally non-computable (DNC) functions, proven by Kucera to be non-negligible in a strong sense: every Martin-L"of random real computes a DNC function. Ambos-Spies et al. showed that the converse does not hold: there are DNC functions which compute no Martin-L"of random real. In this paper, we show that such the set of such DNC functions is in fact non-negligible. More precisely, we prove that for every sufficiently fast-growing computable~$h$, every 2-random real computes an $h$-bounded DNC function which computes no Martin-L"of random real. Further, we show that the same holds for the set of reals which compute a DNC function but no bounded DNC function. The proofs of these results use a combination of a technique due to Kautz (which, following a metaphor of Shen, we like to call a `fireworks argument') and bushy tree forcing, which is the canonical forcing notion used in the study of DNC functions.

Recommendations

• Joining non-low C.E. sets with diagonally non-computable functions
• Diagonally non-recursive functions and effective Hausdorff dimension
• Comparing DNR and WWKL
• Forcing with bushy trees
• scientific article; zbMATH DE number 4118353

Cites work

• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 4053595 (Why is no real title available?)
• scientific article; zbMATH DE number 3559552 (Why is no real title available?)
• scientific article; zbMATH DE number 3637728 (Why is no real title available?)
• A fixed-point-free minimal degree
• Algebra of invariant properties of binary sequences
• Algorithmic randomness and complexity.
• Almost everywhere domination
• Comparing DNR and WWKL
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction
• Deep \(\Pi_1^0\) classes
• Diagonally non-recursive functions and effective Hausdorff dimension
• Everywhere complex sequences and the probabilistic method
• Forcing with bushy trees
• Mass problems associated with effectively closed sets
• Measure and minimal degrees
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• Shift-complex sequences
• The typical Turing degree
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(9)

• On the interplay between effective notions of randomness and genericity
• On the uniform computational content of the Baire category theorem
• Reverse mathematics and initial intervals
• Joining non-low C.E. sets with diagonally non-computable functions
• On the uniform computational content of computability theory
• Ramsey-type graph coloring and diagonal non-computability
• scientific article; zbMATH DE number 7407778 (Why is no real title available?)
• Forcing with bushy trees
• Degrees of randomized computability

This page was built for publication: Diagonally non-computable functions and fireworks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515575)