Descriptive complexity of computable sequences

DOI10.1016/S0304-3975(01)00030-5MaRDI QIDQ5958281zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Bruno Durand, A. 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)

Recommendations

• scientific article; zbMATH DE number 1304316
• On minimal-program complexity measures
• Descriptive complexity of computable sequences revisited
• Randomness for computable measures and initial segment complexity
• Binary sequences. I: Complexity

Cites work

• A formal theory of inductive inference. Part I
• A variant of the Kolmogorov concept of complexity
• Comparison between the complexity of a function and the complexity of its graph
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1304316 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Information-theoretic characterizations of recursive infinite strings
• On the Length of Programs for Computing Finite Binary Sequences
• Relations between varieties of kolmogorov complexities
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(8)

• Descriptive complexity of computable sequences revisited
• On the information carried by programs about the objects they compute
• On the complexity of computable real sequences
• Strict process machine complexity
• scientific article; zbMATH DE number 1304316 (Why is no real title available?)
• DESCRIPTIVE COMPLEXITY IN CANTOR SERIES
• On minimal-program complexity measures
• Comparison between the complexity of a function and the complexity of its graph

This page was built for publication: Descriptive complexity of computable sequences

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