Depth, Highness and DNR Degrees

DOI10.1007/978-3-319-22177-9_7zbMath1434.03109OpenAlexW1507916642MaRDI QIDQ2947871

Philippe Moser, Frank Stephan

Publication date: 29 September 2015

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: http://eprints.maynoothuniversity.ie/6516/1/PM-Depth.pdf

zbMATH Keywords

recursion theoryMartin-Löf random setsBennett deep sequences

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Algorithmic randomness and dimension (03D32)

Related Items (3)

Lowness and logical depth ⋮ Limit-depth and DNR degrees ⋮ Randomness below complete theories of arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Depth as randomness deficiency
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computational depth and reducibility
• Recursive computational depth.
• On the polynomial depth of various sets of random strings
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Computational depth: Concept and applications
• Algorithmic Randomness and Complexity
• A minimal pair of 𝐾-degrees
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Schnorr trivial sets and truth-table reducibility
• A Theory of Program Size Formally Identical to Information Theory
• Finite Self-Information
• The importance of Π₁⁰ classes in effective randomness
• Every 2-random real is Kolmogorov random
• Feasible Depth
• ∏ 0 1 Classes and Degrees of Theories
• Randomness, relativization and Turing degrees
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Depth, Highness and DNR Degrees