Relativized depth

DOI10.1016/J.TCS.2023.113694OpenAlexW4317802061MaRDI QIDQ2686103

Laurent Bienvenu, Wolfgang Merkle, Valentino Delle Rose

Publication date: 24 February 2023

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

Full work available at URL: https://arxiv.org/abs/2112.04451

zbMATH Keywords

Martin-Löf randomness\(K\)-trivialityBennett's logical depthPA-degrees

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the relation between descriptional complexity and algorithmic probability
• Computational depth and reducibility
• Limit complexities revisited
• Lowness properties and randomness
• Algorithmic Randomness and Complexity
• Mass Problems and Randomness
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Every sequence is reducible to a random one
• A Theory of Program Size Formally Identical to Information Theory
• The importance of Π₁⁰ classes in effective randomness
• On the construction of effectively random sets
• Two-Tape Simulation of Multitape Turing Machines

This page was built for publication: Relativized depth