Descriptive complexity of computable sequences
From MaRDI portal
Publication:5958281
DOI10.1016/S0304-3975(01)00030-5zbMath0982.68074WikidataQ57349815 ScholiaQ57349815MaRDI QIDQ5958281
Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Information-theoretic characterizations of recursive infinite strings
- Relations between varieties of kolmogorov complexities
- On the Length of Programs for Computing Finite Binary Sequences
- A variant of the Kolmogorov concept of complexity
- 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
- Comparison between the complexity of a function and the complexity of its graph