THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS

DOI10.1142/S0129054102001199MaRDI QIDQ3021962zbMATH OpenOpenAlexFDO

Authors 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

accelerationalgorithmic information theoryBlum's speed-up theoremcomputational complexityKolmogorov complexityLevin search

Mathematics Subject Classification ID

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

Recommendations

• Short lists with short programs in short time
• On effective procedures for speeding up algorithms
• On the problem of finding minimal programs for tables
• Cost-effectiveness of algorithms
• Generic algorithms for halting problem and optimal machines revisited

Cites work

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

Cited in

(7)

• On universal transfer learning
• Open problems in universal induction \& intelligence
• A theory of incremental compression
• On optimal inverters
• Consistency and optimality
• On Universal Transfer Learning
• The fastest way of computing all universes

This page was built for publication: THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS

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