On the computational power of random strings

DOI10.1016/j.apal.2009.03.001zbMath1192.68383OpenAlexW2154007663MaRDI 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 theoryKolmogorov complexitycomputability theory

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (max. 100)

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

This page was built for publication: On the computational power of random strings