The Fastest and Shortest Algorithm for all Well-Defined Problems
By Marcus Hutter. 2000
82 citations recorded by the source corpus.
An algorithm M is described that solves any well-defined problem p as quickly a the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof. M has broader applicability and can be faster than Levin's universal search, the fastest method for inverting functions save for a large multiplicative constant. An extension of Kolmogorov complexity and two novel natural measures of function complexity are used to show the most efficient program computing some function f is also among the shortest programs provably computing f.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- S. Omohundro
- J. Urgen Schmidhuber
- David R Ha
- Alex Graves
- Sergey Levine
- Yoshua Bengio
- Quoc V. Le
- Faustino J. Gomez
In Computational Theory and Mathematics
- S. Omohundro
- J. Urgen Schmidhuber
- David R Ha
- Sergey Levine
- Jeff Clune
- Pierre-Yves Oudeyer
- Tom Schaul
- Rupesh Kumar Srivastava
Citations in the corpus
- Deep learning in neural networks: An overview (2014, methodology): “Remarkably, there exist blueprints of universal problem solvers or universal RL machines for unlimited problem depth that are time-optimal in various theoretical senses (Hutter, 2002, 2005; Schmidhuber, 2002, 2006b).”
- PowerPlay: Training an Increasingly General Problem Solver by Continually Searching for the Simplest Still Unsolvable Problem (2011, methodology): “It does not need to be universal and asymptotically optimal (Levin, 1973; Hutter, 2002; Schmidhuber, 2004b, 2009) like the recent (not necessarily practically feasible) general problem solvers discussed in Section 7.2; instead it should take into account all constant architecture-specific slowdowns…”
- Optimal Ordered Problem Solver (2002, neutral): “Compare Levin (1973, 1984), Solomonoff (1986), Schmidhuber et al. (1997b), Li and Vit´anyi (1997), Hutter (2002a) (Levin also attributes similar ideas to Al-lender): Method 2.1 ( Lsearch) Set current time limit T=1.”
- Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements (2003, background): “While the hardwired brute force theorem provers of AIXI(t, l) and hsearch systematically search in raw proof space— they can hide the proof search cost (exponential in proof size) in their asymptotic optimality notation [16, 15]—the initial, not yet self-improved Gödel machine already produces many ”
- Gödel Machines: Fully Self-referential Optimal Universal Self-improvers (2007, methodology): “Nevertheless, unlike previous methods, it can in principle exploit at least the provably good speed-ups of any part of its initial software, including those parts responsible for huge (but problem class-independent) slowdowns ignored by the earlier approaches [17, 16].”
- The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions (2002, methodology): “Thanks to Ray Solomonoff, Leonid Levin, Marcus Hutter, Christof Schmidhuber, and an unknown reviewer, for useful comments.”
- The Nature of Self-Improving Artificial Intelligence (2008, background): “performs as well as any other program for any well-specified task [26].”