Algorithmic complexity as a criterion of unsolvability

DOI10.1016/J.TCS.2007.04.011MaRDI QIDQ2383595zbMATH OpenOpenAlexFDO

Authors Mark 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

algorithmic problemdecidabilityinductive algorithmic complexityinductive Turing machineKolmogorov complexityrecursive algorithmic complexitysuper-recursive algorithm

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic complexity of recursive and inductive algorithms
• Algorithmic information theory and undecidability
• scientific article; zbMATH DE number 2084325
• Generic complexity of undecidable problems
• Decidability and universality in the axiomatic theory of computability and algorithms

Cites work

• Algorithmic approach to dynamic information theory
• Algorithmic complexity of recursive and inductive algorithms
• Algorithmic entropy of sets
• Generalized kolmogorov complexity and other dual complexity measures
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1327755 (Why is no real title available?)
• scientific article; zbMATH DE number 2013202 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 227670 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Inductive inference and unsolvability
• Information, randomness and incompleteness. Papers on algorithmic information theory
• On the Length of Programs for Computing Finite Binary Sequences
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
• Program size, oracles, and the jump operation
• The position of index sets of identifiable sets in the arithmetical hierarchy

Cited in

(9)

• Algorithmic complexity of recursive and inductive algorithms
• A note on Blum static complexity measures
• Anytime algorithms for non-ending computations
• scientific article; zbMATH DE number 2084325 (Why is no real title available?)
• Inductive inference and unsolvability
• Decidability and universality in the axiomatic theory of computability and algorithms
• Learning the Undecidable from Networked Systems
• Descriptional complexity in encoded Blum static complexity spaces
• scientific article; zbMATH DE number 3074851 (Why is no real title available?)

This page was built for publication: Algorithmic complexity as a criterion of unsolvability

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