Depth, Highness and DNR Degrees
From MaRDI portal
Publication:2947871
DOI10.1007/978-3-319-22177-9_7zbMath1434.03109OpenAlexW1507916642MaRDI QIDQ2947871
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
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 Π10 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