On the computational power of random strings

DOI10.1016/J.APAL.2009.03.001zbMATH Open1192.68383OpenAlexW2154007663MaRDI QIDQ2271990FDOQ2271990

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

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

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)

Cites Work

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

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)