Relativized depth

DOI10.1016/J.TCS.2023.113694MaRDI QIDQ2686103zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Valentino Delle Rose, Wolfgang Merkle

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

\(K\)-trivialityBennett's logical depthMartin-Löf randomnessPA-degrees

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Recommendations

• Computational depth and reducibility
• Computational depth and reducibility
• Recursive computational depth.
• Computational depth: Concept and applications
• Recursive computational depth

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic randomness and complexity.
• Computability and randomness
• Computational depth and reducibility
• Depth, highness and DNR degrees
• Every sequence is reducible to a random one
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1543065 (Why is no real title available?)
• scientific article; zbMATH DE number 2236645 (Why is no real title available?)
• Limit complexities revisited
• Lowness properties and randomness
• Mass Problems and Randomness
• On the construction of effectively random sets
• On the relation between descriptional complexity and algorithmic probability
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• The importance of \(\Pi^0_1\) classes in effective randomness
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(12)

• Lowness and logical depth
• Limit-depth and DNR degrees
• On the polynomial depth of various sets of random strings
• Depth relevance and hyperformalism
• An almost deep degree
• Depth, highness and DNR degrees
• The fundamental difference between depth and delay
• Depth, highness and DNR degrees
• Deep _1⁰ classes
• Feasible Depth
• Relativized depth
• Bridging computational notions of depth

This page was built for publication: Relativized depth

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