Realistic OOPS for Finding Universal Solvers

Recall that the instruction set $Q$ should contain instructions for invoking or calling code found below $a_{frozen}$, for copying such code into $s(r)$, and for editing the copies and executing the results (examples in Appendix A).

Now suppose there is an ordered sequence of tasks $r_1, r_2, \ldots$. Inductively suppose we have solved the first $n$ tasks through programs stored below address $a_{frozen}$, and that the most recently discovered program starting at address $a_{last} \leq a_{frozen}$ actually solves all of them, possibly using information conveyed by earlier programs $q^1,q^2,\ldots$. To find a program solving the first $n+1$ tasks, Realistic OOPS invokes Try as follows (using set notation for task rings, where the tasks are ordered in cyclic fashion--compare basic Method 3.1):

---------------------------------------------

Method 4.2 (Realistic OOPS (n+1))   Initialize current time limit
$T := 2$ and $q$-pointer $qp := a_{frozen}$ (top frozen address).

1. Set instruction pointer $ip(r_{n+1}) := a_{last}$ (start address of code solving all tasks up to $n$).

IF Try ( $qp, r_{n+1}, \{ r_{n+1} \}, 0, \frac{1}{2}$) then exit.
(This means that half the search time is assigned to the most recent $q_{a_{last}:a_{frozen}}$ and all possible prolongations thereof).

2. IF it is possible to initialize all $n+1$ tasks within time $T$:

Set local variable $a := a_{frozen} + 1$ (first unused address); for all $r \in \{ r_1, r_2, \ldots, r_{n+1} \}$ set $ip(r) := a$.
IF Try ( $qp, r_{n+1}, \{ r_1, r_2, \ldots, r_{n+1} \}, 0, \frac{1}{2}$) set $a_{last} := a$ and exit.
(This means that half the time is assigned to all new programs with fresh starts).

3. Set $T := 2 T$, and go to 1.

---------------------------------------------

Therefore, given tasks $r_1, r_2, \ldots,$ first initialize $a_{last}$; then for $i := 1, 2, \ldots$ invoke Realistic OOPS$(i)$ to find programs starting at (possibly increasing) address $a_{last}$, each solving all tasks so far, possibly eventually discovering a universal solver for all tasks in the sequence.

As address $a_{last}$ increases for the $n$-th time, $q^n$ is defined as the program starting at $a_{last}$'s old value and ending right before its new value. Program $q^m$ ($m>i,j$) may exploit $q^i$ by calling it as a subprogram, or by copying $q^i$ into some state $s(r)$, then editing it there, e.g., by inserting parts of another $q^j$ somewhere, then executing the edited variant.

Back to OOPS main page