Bounded Turing reductions and data processing inequalities for sequences

DOI10.1007/s00224-017-9804-7zbMath1408.68083arXiv1608.04764OpenAlexW2962955706MaRDI QIDQ1787951

Adam Case

Publication date: 5 October 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityeffective dimensiondata processing inequalityTuring reductionalgorithmic mutual informationcomputable Lipschitz reduction

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness and the linear degrees of computability
• Turing oracle machines, online computing, and three displacements in computability theory
• Mutual dimension and random sequences
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Randomness and reducibility
• The dimensions of individual strings and sequences
• Mutual Dimension
• Random reals and Lipschitz continuity
• Randomness conservation inequalities; information and independence in mathematical theories
• Every sequence is reducible to a random one
• Elements of Information Theory
• Mutual Information and Maximal Correlation as Measures of Dependence
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Bounded Turing reductions and data processing inequalities for sequences