Recursive computational depth.
From MaRDI portal
Publication:1854307
DOI10.1006/inco.1999.2794zbMath1045.68569OpenAlexW2026888287MaRDI QIDQ1854307
James I. Lathrop, Jack H. Lutz
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1999.2794
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Bounded Randomness ⋮ Lowness and logical depth ⋮ Depth, Highness and DNR Degrees ⋮ Pushdown and Lempel-Ziv depth ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ The complexity of stochastic sequences ⋮ Lowness for bounded randomness ⋮ Weakly useful sequences ⋮ Depth as randomness deficiency ⋮ Kolmogorov-Loveland randomness and stochasticity
Cites Work
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Almost everywhere high nonuniform complexity
- Computational depth and reducibility
- Process complexity and effective random tests
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- Category and Measure in Complexity Classes
- Von Mises' definition of random sequences reconsidered
- THE BANACH-MAZUR GAME
- A Theory of Program Size Formally Identical to Information Theory
- Weakly useful sequences
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- A unified approach to the definition of random sequences
- The definition of random sequences
- A formal theory of inductive inference. Part II
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Recursive computational depth.
