Recursive computational depth

DOI10.1007/3-540-63165-8_171MaRDI QIDQ4571946zbMATH OpenOpenAlexFDO

Authors James I. Lathrop, Jack H. Lutz

Publication date 4 July 2018

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63165-8_171

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 I
• A unified approach to the definition of random sequences
• Almost everywhere high nonuniform complexity
• Computational depth and reducibility
• scientific article; zbMATH DE number 193560 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• The definition of random sequences
• Von Mises' definition of random sequences reconsidered
• Weakly useful sequences
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(10)

• Computational depth and reducibility
• Weakly useful sequences
• Recursive computational depth.
• Relativized depth
• Computational depth and reducibility
• Weakly useful sequences
• The Recursive Core
• A general notion of useful information
• Natural complexity, computational complexity and depth
• Computing Depths of Patterns

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 Q4571946)