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 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.