THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS

DOI10.1142/S0129054102001199zbMath1066.68057OpenAlexW2148452608MaRDI QIDQ3021962

Marcus Hutter

Publication date: 22 June 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054102001199

zbMATH Keywords

computational complexityalgorithmic information theoryKolmogorov complexityaccelerationBlum's speed-up theoremLevin search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

ON OPTIMAL INVERTERS ⋮ Open problems in universal induction \& intelligence ⋮ On Universal Transfer Learning ⋮ On universal transfer learning ⋮ A theory of incremental compression ⋮ Consistency and Optimality

Cites Work

• A Mathematical Theory of Communication
• Relations between diagonalization, proof systems, and complexity gaps
• Gaussian elimination is not optimal
• Randomness conservation inequalities; information and independence in mathematical theories
• Complexity-based induction systems: Comparisons and convergence theorems
• Minimum description length induction, Bayesianism, and Kolmogorov complexity
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the Length of Programs for Computing Finite Binary Sequences
• On Effective Procedures for Speeding Up Algorithms
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part I