1.0

**Jürgen Schmidhuber
juergen@idsia.ch - www.idsia.ch/~ juergen
IDSIA, Galleria 2, 6928 Manno-Lugano, Switzerland**

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.

**Keywords:** OOPS,
bias-optimality,
incremental optimal universal search,
efficient planning & backtracking in program space,
metasearching & metalearning,
self-improvement.

- Introduction

- Survey of Universal Search
and Suboptimal Incremental Extensions
- Bias-Optimality
- Near-Bias-Optimal Nonincremental Universal Search
- Asymptotically Fastest Nonincremental Problem Solver
- Previous Work on Incremental Extensions of Universal Search
- Other Work on Incremental Learning

- OOPS on Universal Computers
- Formal Setup and Notation
- Basic Principles of OOPS
- Essential Properties of OOPS
- Measuring Bias Through Optimal Search Time
- Summary

- OOPS on Realistic Computers
- Multitasking & Prefix
Tracking By Recursive Procedure
**``Try''** - Realistic OOPS for Finding Universal Solvers
- Near-Bias-Optimality of Realistic OOPS
- Realistic OOPS Variants for Optimization etc.
- Illustrated Informal Recipe for OOPS Initialization
- Example Initial Programming Language

- Multitasking & Prefix
Tracking By Recursive Procedure
- Limitations and Possible Extensions of OOPS
- How Often Can we Expect to Profit from Earlier Tasks?
- Fundamental Limitations of OOPS
- Outline of OOPS-based Reinforcement Learning (OOPS-RL)
- Gödel Machine and OOPS

- Experiments: 60 Successive Tasks
- On Task-Specific Initialization
- Towers of Hanoi
- Incremental Learning: First Solve 30 Simpler Context Free Language Tasks
- C-Code
- Experimental Results for Both Task Sets
- Analysis of the Results: Benefits of Metasearching
- Future Research
- Physical Limitations of OOPS
- Acknowledgments

- Example Programming Language

- Bibliography
- About this document ...

Back to OOPS main page