Algorithmic complexity of recursive and inductive algorithms

DOI10.1016/j.tcs.2003.12.003zbMath1072.68048MaRDI QIDQ1434367

Mark S. Burgin

Publication date: 4 August 2004

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

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

zbMATH Keywords

Kolmogorov complexity; Complexity; Turing machine; Recursive algorithm; Efficiency; Dual complexity measure; Inductive Turing machine; Super-recursive algorithm

Mathematics Subject Classification ID

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

Related Items

Algorithmic complexity as a criterion of unsolvability

Cites Work

• What is complexity?
• Process complexity and effective random tests
• Generalized kolmogorov complexity and other dual complexity measures
• A Theory of Program Size Formally Identical to Information Theory
• A Complexity Measure
• The Cost of Developing Large-Scale Software
• Communication Complexity
• Minimal-program complexity of sequences with restricted resources
• On the Length of Programs for Computing Finite Binary Sequences
• On the size of machines
• 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
• An Overview of the Theory of Computational Complexity
• Language identification in the limit
• A formal theory of inductive inference. Part II
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item