Bridging computational notions of depth

DOI10.1016/J.IC.2026.105420MaRDI QIDQ6841899zbMATH OpenFDO

Authors Laurent Bienvenu, Christopher P. Porter

Publication date 20 March 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105420

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Complex tilings
• Computability and randomness
• Computational depth and reducibility
• Deep _1⁰ classes
• Depth, highness and DNR degrees
• Forbidden information
• General random sequences and learnable sequences
• Kolmogorov complexity and the recursion theorem
• Lowness and logical depth
• Mathematical metaphysics of randomness
• On the interplay between effective notions of randomness and genericity
• Randomness and semimeasures
• Randomness conservation inequalities; information and independence in mathematical theories
• Randomness for computable measures and initial segment complexity
• Relativized depth
• Solovay functions and their applications in algorithmic randomness
• Strong reductions in effective randomness
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(1)

• Dimensionality and randomness

This page was built for publication: Bridging computational notions of depth

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