Descriptive complexity of computable sequences revisited

DOI10.1016/J.TCS.2020.01.013zbMath1443.68075arXiv1902.01279OpenAlexW3000495224WikidataQ126347941 ScholiaQ126347941MaRDI QIDQ2290652

Nikolai K. Vereshchagin

Publication date: 29 January 2020

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

Full work available at URL: https://arxiv.org/abs/1902.01279

zbMATH Keywords

Kolmogorov complexitylimit complexitycomputable sequences

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Classical recursion theory. Vol. II
• Kolmogorov Complexity and Algorithmic Randomness
• Relations between varieties of kolmogorov complexities
• On the Length of Programs for Computing Finite Binary Sequences
• A variant of the Kolmogorov concept of complexity
• A formal theory of inductive inference. Part II
• Descriptive complexity of computable sequences
• Kolmogorov complexity conditional to large integers

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