Basic Principles of OOPS

Given a sequence of tasks, we solve one task after another in the given order. The solver of the $n$-th task $(n \geq 1)$ will be a program $q^i$ $(i \leq n)$ stored such that it occupies successive addresses somewhere between 1 and $l(q)$. The solver of the $1$st task will start at address 1. The solver of the $n$-th task $(n>1)$ will either start at the start address of the solver of the $n-1$-th task, or right after its end address. To find a universal solver for all tasks in a given task sequence, do:

Method 3.1 (OOPS)   FOR task index $n=1,2,\ldots$ DO:

1. Initialize current time limit $T := 2$.

2. Spend at most $T/2$ on a variant of LSEARCH that searches for a program solving task $n$ and starting at the start address $a_{last}$ of the most recent successful code (1 if there is none). That is, the problem-solving program either must be equal to $q_{a_{last}:a_{frozen}}$ or must have $q_{a_{last}:a_{frozen}}$ as a prefix. If solution found, go to 5.

3. Spend at most $T/2$ on LSEARCH for a fresh program that starts at the first writeable address and solves all tasks $1..n$. If solution found, go to 5.

4. Set $T := 2 T$, and go to 2.

5. Let the top non-writeable address $a_{frozen}$ point to the end of the just discovered problem-solving program.

Here step 2 tries to generalize by using the solver of the first $n-1$ tasks for task $n$. Extending a previous solution while simultaneously looking for a new solution may be viewed as a way of combining exploration and exploitation.

Back to OOPS main page