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)

Levin, 2001

Hutter, 2001

on Schmidhuber’s SNF grant

Previous slide

Next slide

Back to first slide

View graphic version