Optimal ordered problem solver

Research output: Contribution to journalArticlepeer-review

93 Scopus citations

Abstract

We introduce a general and in a certain sense time-optimal way of solving one problem after another, efficiently searching the space of programs that compute solution candidates, including those programs that organize and manage and adapt and reuse earlier acquired knowledge. The Optimal Ordered Problem Solver (OOPS) draws inspiration from Levin's Universal Search designed for single problems and universal Turing machines. It spends part of the total search time for a new problem on testing programs that exploit previous solution-computing programs in computable ways. If the new problem can be solved faster by copy-editing/invoking previous code than by solving the new problem from scratch, then OOPS will find this out. If not, then at least the previous solutions will not cause much harm. We introduce an efficient, recursive, backtracking-based way of implementing OOPS on realistic computers with limited storage. Experiments illustrate how OOPS can greatly profit from metalearning or metasearching, that is, searching for faster search procedures.
Original languageEnglish (US)
Pages (from-to)211-254
Number of pages44
JournalMachine Learning
Volume54
Issue number3
DOIs
StatePublished - Mar 1 2004
Externally publishedYes

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software

Fingerprint

Dive into the research topics of 'Optimal ordered problem solver'. Together they form a unique fingerprint.

Cite this