Recursive computational depth

DOI10.1007/3-540-63165-8_171zbMath1401.68129OpenAlexW1566207393MaRDI QIDQ4571946

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

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

Cites Work

• Almost everywhere high nonuniform complexity
• Computational depth and reducibility
• Weakly useful sequences
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Von Mises' definition of random sequences reconsidered
• A unified approach to the definition of random sequences
• The definition of random sequences
• A formal theory of inductive inference. Part I
• Unnamed Item
• Unnamed Item

This page was built for publication: Recursive computational depth