Diagonally non-computable functions and fireworks

DOI10.1016/J.IC.2016.12.008zbMATH Open1423.03141arXiv1411.6846OpenAlexW1517996398MaRDI QIDQ515575FDOQ515575

Authors: Laurent Bienvenu, Ludovic Patey 

Publication date: 16 March 2017

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

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.

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

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
• Publication:4732457

zbMATH Keywords

diagonally non-computable functionsfireworks argumentsLevin-V'yugin algebranegligibility

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Forcing with bushy trees
• Reverse mathematics and initial intervals
• Joining non-low C.E. sets with diagonally non-computable functions
• On the uniform computational content of the Baire category theorem
• On the interplay between effective notions of randomness and genericity
• Degrees of randomized computability
• On the uniform computational content of computability theory
• Ramsey-type graph coloring and diagonal non-computability
• Title not available (Why is that?)

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)