Limit complexities revisited
From MaRDI portal
Publication:1959396
DOI10.1007/s00224-009-9203-9zbMath1206.68154arXiv0802.2833OpenAlexW2013288533WikidataQ57349616 ScholiaQ57349616MaRDI QIDQ1959396
Alexander Shen, Laurent Bienvenu, Andrej A. Muchnik, Nikolai K. Vereshchagin
Publication date: 6 October 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0802.2833
Related Items (7)
What Percentage of Programs Halt? ⋮ Randomness, Computation and Mathematics ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ Relativized depth ⋮ Effectively approximating measurable sets by open sets ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Coherence of reducibilities with randomness notions
Cites Work
- Unnamed Item
- Unnamed Item
- Classical recursion theory. The theory of functions and sets of natural numbers
- Lower Limits of Frequencies in Computable Sequences and Relativized a Priori Probability
- Degrees of unsolvability of continuous functions
- Logical basis for information theory and probability theory
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Randomness, relativization and Turing degrees
- Kolmogorov complexity conditional to large integers
This page was built for publication: Limit complexities revisited
