On the computational power of random strings

DOI10.1016/j.apal.2009.03.001zbMath1192.68383MaRDI QIDQ2271990

Adam R. Day

Publication date: 5 August 2009

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2009.03.001

zbMATH Keywords

algorithmic information theory; Kolmogorov complexity; computability theory

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D15: Complexity of computation (including implicit computational complexity)

Related Items

A generalized characterization of algorithmic probability, The Complexity of Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the relation between descriptional complexity and algorithmic probability
• Incompleteness theorems for random reals
• Process complexity and effective random tests
• What can be efficiently reduced to the Kolmogorov-random strings?
• Algorithmic Randomness and Complexity
• Degrees of monotone complexity
• A Theory of Program Size Formally Identical to Information Theory
• On the complexity of random strings
• Power from Random Strings
• Three approaches to the quantitative definition of information^*
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part I
• Kolmogorov entropy in the context of computability theory