** 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 solving the current task set within steps,
given current code bias
and .
Denote 's probability by (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 steps.
We observe that OOPS
will find a solution within at most
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 (necessary because we do not know in advance the
best value of ), 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:** Realistic OOPS Variants for
** Up:** OOPS on Realistic Computers
** Previous:** Realistic OOPS for Finding
Juergen Schmidhuber
2004-04-15

Back to OOPS main page