Algorithmic complexity of recursive and inductive algorithms

DOI10.1016/J.TCS.2003.12.003zbMATH Open1072.68048OpenAlexW2007412164MaRDI QIDQ1434367FDOQ1434367

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

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

zbMATH Keywords

Kolmogorov complexityTuring machineComplexityEfficiencyRecursive algorithmDual complexity measureInductive Turing machineSuper-recursive algorithm

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Process complexity and effective random tests
• A Theory of Program Size Formally Identical to Information Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Language identification in the limit
• A formal theory of inductive inference. Part II
• Communication Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Length of Programs for Computing Finite Binary Sequences
• A variant of the Kolmogorov concept of complexity
• What is complexity?
• A Complexity Measure
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the size of machines
• Title not available (Why is that?)
• An Overview of the Theory of Computational Complexity
• The Cost of Developing Large-Scale Software
• Minimal-program complexity of sequences with restricted resources
• Generalized kolmogorov complexity and other dual complexity measures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (11)

• Title not available (Why is that?)
• Revising type-2 computation and degrees of discontinuity
• Title not available (Why is that?)
• A note on Blum static complexity measures
• Descriptional complexity in encoded Blum static complexity spaces
• Super-Recursive Algorithms
• Algorithmic complexity as a criterion of unsolvability
• Separating the classes of recursively enumerable languages based on machine size
• An information technology for efficiency analysis of recursive algorithms using standard complexity recurrences
• Inductive complexity and Shannon entropy
• Title not available (Why is that?)

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)