On the computational power of random strings

DOI10.1016/J.APAL.2009.03.001MaRDI QIDQ2271990zbMATH OpenOpenAlexFDO

Authors 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

Kolmogorov complexitycomputability theoryalgorithmic information theory

Mathematics Subject Classification ID

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

Recommendations

• Power from Random Strings
• On the complexity of random strings
• Limits on the Computational Power of Random Strings
• Limits on the computational power of random strings
• STACS 2004

Cites work

• scientific article; zbMATH DE number 3456654 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3489017 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part I
• Algorithmic randomness and complexity.
• Degrees of monotone complexity
• Incompleteness theorems for random reals
• Kolmogorov entropy in the context of computability theory
• On process complexity
• On the complexity of random strings
• On the relation between descriptional complexity and algorithmic probability
• Power from Random Strings
• Process complexity and effective random tests
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Three approaches to the quantitative definition of information^*
• What can be efficiently reduced to the Kolmogorov-random strings?

Cited in

(9)

• The Complexity of Complexity
• An excursion to the Kolmogorov random strings
• On the Polynomial Depth of Various Sets of Random Strings
• What can be efficiently reduced to the Kolmogorov-random strings?
• Power of Randomization in Automata on Infinite Strings
• On a Conjecture about Binary Strings Distribution
• The combinatorial complexity of a finite string
• Limits on the Computational Power of Random Strings
• A generalized characterization of algorithmic probability

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

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