Depth, highness and DNR degrees

DOI10.1007/978-3-319-22177-9_7MaRDI QIDQ2947871zbMATH OpenOpenAlexFDO

Authors 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 theoryBennett deep sequencesMartin-Löf random sets

Mathematics Subject Classification ID

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

Recommendations

• Depth, highness and DNR degrees
• Limit-depth and DNR degrees
• Relativized depth
• Computational depth and reducibility
• Computational depth and reducibility

Cites work

• scientific article; zbMATH DE number 193560 (Why is no real title available?)
• scientific article; zbMATH DE number 1048037 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A minimal pair of 𝐾-degrees
• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computability and randomness
• Computational depth and reducibility
• Computational depth: Concept and applications
• Depth as randomness deficiency
• Every 2-random real is Kolmogorov random
• Feasible Depth
• Finite self-information
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• On the polynomial depth of various sets of random strings
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Randomness, relativization and Turing degrees
• Recursive computational depth.
• Schnorr trivial sets and truth-table reducibility
• The importance of \(\Pi^0_1\) classes in effective randomness
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(6)

• Types of depth and formula size
• Lowness and logical depth
• An almost deep degree
• Randomness below complete theories of arithmetic
• Limit-depth and DNR degrees
• Depth, highness and DNR degrees

This page was built for publication: Depth, highness and DNR degrees

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