Diagonally non-computable functions and fireworks

DOI10.1016/j.ic.2016.12.008zbMath1423.03141arXiv1411.6846OpenAlexW1517996398MaRDI QIDQ515575

Ludovic Patey, Laurent Bienvenu

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

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

Related Items

On the uniform computational content of the Baire category theorem ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ Reverse mathematics and initial intervals ⋮ Ramsey-type graph coloring and diagonal non-computability ⋮ On the uniform computational content of computability theory ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebra of invariant properties of binary sequences
• Mass problems associated with effectively closed sets
• COMPARING THE STRENGTH OF DIAGONALLY NONRECURSIVE FUNCTIONS IN THE ABSENCE OF INDUCTION
• The typical Turing degree
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• Kolmogorov complexity and the Recursion Theorem
• Everywhere complex sequences and probabilistic method
• Algorithmic Randomness and Complexity
• A fixed-point-free minimal degree
• Measure and minimal degrees
• Diagonally non-recursive functions and effective Hausdorff dimension
• Shift-complex sequences
• Almost everywhere domination
• Comparing DNR and WWKL
• DEEP CLASSES
• FORCING WITH BUSHY TREES
• ∏ 0 1 Classes and Degrees of Theories