Depth, highness and DNR degrees
DOI10.1007/978-3-319-22177-9_7zbMATH Open1434.03109OpenAlexW1507916642MaRDI QIDQ2947871FDOQ2947871
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
Recommendations
Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Algorithmic randomness and complexity.
- Computability and randomness
- A Theory of Program Size Formally Identical to Information Theory
- Feasible Depth
- Schnorr trivial sets and truth-table reducibility
- Every 2-random real is Kolmogorov random
- Randomness, relativization and Turing degrees
- An introduction to Kolmogorov complexity and its applications
- ∏ 0 1 Classes and Degrees of Theories
- Classical recursion theory. The theory of functions and sets of natural numbers
- RELATIVIZING CHAITIN'S HALTING PROBABILITY
- The importance of \(\Pi^0_1\) classes in effective randomness
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- A minimal pair of 𝐾-degrees
- Title not available (Why is that?)
- Computational depth: Concept and applications
- Computational depth and reducibility
- Recursive computational depth.
- Depth as randomness deficiency
- Title not available (Why is that?)
- On the polynomial depth of various sets of random strings
- Finite self-information
Cited In (6)
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)
