Descriptive complexity of computable sequences

DOI10.1016/S0304-3975(01)00030-5zbMath0982.68074OpenAlexW1976714922WikidataQ57349815 ScholiaQ57349815MaRDI QIDQ5958281

Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00030-5

zbMATH Keywords

infinite binary recursive sequences

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Comparison between the complexity of a function and the complexity of its graph ⋮ Descriptive complexity of computable sequences revisited

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