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