Algorithmic complexity as a criterion of unsolvability

DOI10.1016/j.tcs.2007.04.011zbMath1124.68047OpenAlexW1997448562MaRDI QIDQ2383595

Mark S. Burgin

Publication date: 19 September 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.011

zbMATH Keywords

Kolmogorov complexitydecidabilitysuper-recursive algorithmalgorithmic probleminductive algorithmic complexityinductive Turing machinerecursive algorithmic complexity

Mathematics Subject Classification ID

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

Related Items

A Note on Blum Static Complexity Measures, DESCRIPTIONAL COMPLEXITY IN ENCODED BLUM STATIC COMPLEXITY SPACES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Program size, oracles, and the jump operation
• Algorithmic entropy of sets
• Algorithmic approach to dynamic information theory
• Algorithmic complexity of recursive and inductive algorithms
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• The position of index sets of identifiable sets in the arithmetical hierarchy
• Inductive inference and unsolvability
• Generalized kolmogorov complexity and other dual complexity measures
• On the Length of Programs for Computing Finite Binary Sequences
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers