Recursive computational depth.

DOI10.1006/INCO.1999.2794MaRDI QIDQ1854307zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Recursive computational depth
• Computational depth and reducibility
• Computational depth and reducibility
• Weakly useful sequences
• Weakly useful sequences

Cites work

• A formal theory of inductive inference. Part II
• A Theory of Program Size Formally Identical to Information Theory
• A unified approach to the definition of random sequences
• Almost everywhere high nonuniform complexity
• Category and Measure in Complexity Classes
• Computational depth and reducibility
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 46153 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3344793 (Why is no real title available?)
• Process complexity and effective random tests
• THE BANACH-MAZUR GAME
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• Von Mises' definition of random sequences reconsidered
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weakly useful sequences
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(21)

• Lowness and logical depth
• Weakly useful sequences
• The complexity of stochastic sequences
• Kolmogorov-Loveland randomness and stochasticity
• Relativized depth
• Bounded randomness
• Depth, highness and DNR degrees
• On the Polynomial Depth of Various Sets of Random Strings
• On the difference between finite-state and pushdown depth
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• Recursive computational depth
• Computational depth and reducibility
• Weakly useful sequences
• A general notion of useful information
• Natural complexity, computational complexity and depth
• Deep _1⁰ classes
• Computing Depths of Patterns
• Pushdown and Lempel-Ziv depth
• Pebble-depth
• Lowness for bounded randomness
• Depth as randomness deficiency

This page was built for publication: Recursive computational depth.

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