Lowness and logical depth

DOI10.1016/j.tcs.2017.08.010zbMath1418.03150OpenAlexW2745592874MaRDI QIDQ1676317

Michael McInerney, Keng Meng Ng, Rodney G. Downey

Publication date: 6 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.08.010

zbMATH Keywords

depthlownesscomputabilitycomputably enumerable degreesBennett depth

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Related Items

Pushdown and Lempel-Ziv depth ⋮ Limit-depth and DNR degrees ⋮ Searching for shortest and least programs ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Polylog depth, highness and lowness for E

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Depth as randomness deficiency
• Recursive computational depth.
• On the polynomial depth of various sets of random strings
• Time-bounded Kolmogorov complexity and Solovay functions
• Computational depth: Concept and applications
• Lowness properties and randomness
• Depth, Highness and DNR Degrees
• Algorithmic Randomness and Complexity
• Lowness for the class of random sets
• Feasible Depth
• An introduction to Kolmogorov complexity and its applications