Optimal Ordered Problem Solver (OOPS)

**Notation.**
Unless stated otherwise or obvious,
to simplify notation,
throughout the paper newly introduced variables
are assumed to be integer-valued and to cover the range clear from the context.
Given some finite or infinite countable alphabet
,
let denote the set of finite sequences or strings over ,
where is the empty string. We use the alphabet name's lower case
variant to introduce (possibly variable) strings such as
;
denotes the number of symbols in string , where
;
is the -th symbol of ;
if and
otherwise
(where
).
is the concatenation of and (e.g.,
if and then
).

Consider countable alphabets and .
Strings
represent possible internal
*states* of a computer; strings
represent code or programs for manipulating states.
We focus on being the set of integers
and
representing a set of
instructions of some programming language (that is,
substrings within states may also encode programs).

is a set of currently unsolved tasks.
Let the variable denote the current state of task ,
with -th component on a *computation tape*
(think of a separate tape for each task).
For convenience we combine current state and current
code in a single
*address space*,
introducing negative and positive addresses ranging
from to ,
defining the content of address as
if
and
if
.
All dynamic task-specific data
will be represented at non-positive addresses.
In particular, the current instruction pointer
*ip(r)*
of task
can be found at (possibly variable)
address
.
Furthermore, also encodes
a modifiable probability distribution
on . This variable distribution will be used to
select a new instruction in case points to
the current topmost address right after the end of the current code .

is a variable address that cannot decrease.
Once chosen, the *code bias*
will remain unchangeable forever -- it is a (possibly empty)
sequence of programs , some of them
prewired by the user, others *frozen* after previous successful
searches for solutions to previous tasks.
Given , the goal is to solve all tasks ,
by a program that appropriately uses or extends
the current code
.

We will do this in a *bias-optimal* fashion, that is,
no solution candidate will get much more search time
than it deserves, given some initial probabilistic bias
on program space :

- OOPS Prerequisites: Multitasking & Prefix Tracking Through Method ``Try''
- OOPS For Finding Universal Solvers

Back to OOPS home page