First: Non-Incremental Universal Search
LSEARCH (1973, 1984): Given a single problem and a probability distribution P on programs.
Until problem solved: In phase i=1,2,3… execute all programs p with runtime ? 2i P(p).
Asymptotically optimal: Suppose unknown fastest program solves problem of size k within f(k) steps. LSEARCH will take at most O(f(k)/P(p))=O(f(k)) steps.
First applications: Schmidhuber, ICML 95, Neural Networks 97, Schmidhuber & Wiering & Zhao, ICML 97, MLJ 97.
My postdoc’s optimal HSEARCH for all well- defined problems: constant factor ə+? !
But additive unknown constant :-(
“Only math nerds would consider 2500 finite.” (L. Levin)
on Schmidhuber’s SNF grant
Back to J. Schmidhuber's OOPS page