Limit-depth and DNR degrees

DOI10.1016/J.IPL.2018.02.015zbMath1476.03059OpenAlexW2789971377MaRDI QIDQ1708266

Frank Stephan, Philippe Moser

Publication date: 5 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://mural.maynoothuniversity.ie/13190/1/PM_computer%20science_limit%20depth.pdf

zbMATH Keywords

Kolmogorov complexitytheory of computationlogical depth

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items (1)

Searching for shortest and least programs

Cites Work

• Unnamed Item
• Unnamed Item
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computational depth and reducibility
• Lowness and logical depth
• On the polynomial depth of various sets of random strings
• Depth, Highness and DNR Degrees
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity

This page was built for publication: Limit-depth and DNR degrees