Algorithmic complexity of recursive and inductive algorithms

DOI10.1016/J.TCS.2003.12.003MaRDI QIDQ1434367zbMATH OpenOpenAlexFDO

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

ComplexityDual complexity measureEfficiencyInductive Turing machineKolmogorov complexityRecursive algorithmSuper-recursive algorithmTuring machine

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic complexity as a criterion of unsolvability
• scientific article; zbMATH DE number 3924764
• Inductive complexity and Shannon entropy
• scientific article; zbMATH DE number 782018
• scientific article; zbMATH DE number 4008382

Cites work

• A Complexity Measure
• A formal theory of inductive inference. Part II
• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity
• An Overview of the Theory of Computational Complexity
• Communication Complexity
• Generalized kolmogorov complexity and other dual complexity measures
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3123490 (Why is no real title available?)
• scientific article; zbMATH DE number 3917710 (Why is no real title available?)
• scientific article; zbMATH DE number 3924764 (Why is no real title available?)
• scientific article; zbMATH DE number 4002078 (Why is no real title available?)
• scientific article; zbMATH DE number 51799 (Why is no real title available?)
• scientific article; zbMATH DE number 107775 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3595145 (Why is no real title available?)
• scientific article; zbMATH DE number 3592932 (Why is no real title available?)
• scientific article; zbMATH DE number 497572 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3805532 (Why is no real title available?)
• scientific article; zbMATH DE number 842688 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• Language identification in the limit
• Minimal-program complexity of sequences with restricted resources
• On the Length of Programs for Computing Finite Binary Sequences
• On the size of machines
• Process complexity and effective random tests
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The Cost of Developing Large-Scale Software
• What is complexity?

Cited in

(11)

• An information technology for efficiency analysis of recursive algorithms using standard complexity recurrences
• Algorithmic complexity as a criterion of unsolvability
• A note on Blum static complexity measures
• Inductive complexity and Shannon entropy
• Super-Recursive Algorithms
• Separating the classes of recursively enumerable languages based on machine size
• scientific article; zbMATH DE number 3924764 (Why is no real title available?)
• scientific article; zbMATH DE number 4008382 (Why is no real title available?)
• scientific article; zbMATH DE number 782018 (Why is no real title available?)
• Revising type-2 computation and degrees of discontinuity
• Descriptional complexity in encoded Blum static complexity spaces

This page was built for publication: Algorithmic complexity of recursive and inductive algorithms

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