Algorithmic complexity of recursive and inductive algorithms

DOI10.1016/j.tcs.2003.12.003zbMath1072.68048OpenAlexW2007412164MaRDI 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 complexityComplexityTuring machineRecursive algorithmEfficiencyDual complexity measureInductive Turing machineSuper-recursive algorithm

Mathematics Subject Classification ID

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

Related Items

A Note on Blum Static Complexity Measures ⋮ Separating the Classes of Recursively Enumerable Languages Based on Machine Size ⋮ Algorithmic complexity as a criterion of unsolvability ⋮ Revising Type-2 Computation and Degrees of Discontinuity ⋮ DESCRIPTIONAL COMPLEXITY IN ENCODED BLUM STATIC COMPLEXITY SPACES

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