next up previous
Next: Realistic OOPS Variants for Up: OOPS on Realistic Computers Previous: Realistic OOPS for Finding


Near-Bias-Optimality of Realistic OOPS

Realistic OOPS is not only asymptotically optimal in the sense of [30] (see Method 2.1), but also near bias-optimal (compare Def. 2.1, Observation 3.4):

Observation 4.1   Ignoring hardware-specific overhead, OOPS is 8-bias-optimal with respect to the current task.

To see this, consider a program $p$ solving the current task set within $k$ steps, given current code bias $q_{0:a_{frozen}}$ and $a_{last}$. Denote $p$'s probability by $P(p)$ (compare Eq. (1) and Method 4.2; for simplicity we omit the obvious conditions). A bias-optimal solver would find a solution within at most $k/P(p)$ steps. We observe that OOPS will find a solution within at most $2^3k/P(p)$ steps, ignoring a bit of machine-specific overhead (for marking changed tape components, measuring time, switching between tasks, etc, compare Section 4.1): At most a factor 2 might be lost through allocating half the search time to prolongations of the most recent code, another factor 2 for the incremental doubling of $T$ (necessary because we do not know in advance the best value of $T$), and another factor 2 for Try's resets of states and tasks. If we do not want to ignore hardware issues: on currently widely used computers we can realistically expect to suffer from slowdown factors smaller than acceptable values such as, say, 100.


next up previous
Next: Realistic OOPS Variants for Up: OOPS on Realistic Computers Previous: Realistic OOPS for Finding
Juergen Schmidhuber 2004-04-15

Back to OOPS main page