Next: OOPS For Finding Universal Up: Optimal Ordered Problem Solver Previous: Optimal Ordered Problem Solver

## OOPS Prerequisites: Multitasking & Prefix Tracking Through Method Try''

The Turing machine-based setups for HSEARCH and LSEARCH assume potentially infinite storage. Hence they may largely ignore questions of storage management. In any practical system, however, we have to efficiently reuse limited storage. This, and multitasking, is what the present subsection is about. The recursive method Try below allocates time to program prefixes, each being tested on multiple tasks simultaneously, such that the sum of the runtimes of any given prefix, tested on all tasks, does not exceed the total search time multiplied by the prefix probability (the product of the tape-dependent probabilities of its previously selected components in ). Try tracks effects of tested program prefixes, such as storage modifications (including probability changes) and partially solved task sets, to reset conditions for subsequent tests of alternative prefix continuations in an optimally efficient fashion (at most as expensive as the prefix tests themselves). Optimal backtracking requires that any prolongation of some prefix by some token gets immediately executed. To allow for efficient undoing of state changes, we use global Boolean variables (initially FALSE) for all possible state components . We initialize time probability ; q-pointer and state (including and ) with task-specific information for all task names in a ring of tasks. Here the expression ring'' indicates that the tasks are ordered in cyclic fashion; denotes the number of tasks in ring . Given a global search time limit , we Try to solve all tasks in , by using existing code in and / or by discovering an appropriate prolongation of :

Method 2.1 (returns TRUE or FALSE; )   .

1. Make an empty stack ; set local variables Done FALSE.

WHILE and and instruction pointer valid ( ) and instruction valid ( ) and no halt condition (e.g., error such as division by 0) encountered (evaluate conditions in this order until first satisfied, if any) DO:

If possible, interpret / execute token according to the rules of the given programming language (this may modify including instruction pointer and distribution , but not ), continually increasing by the consumed time. Whenever the execution changes some state component whose FALSE, set TRUE and save the previous value by pushing the triple onto . Remove from if solved. IF , set equal to the next task in ring . ELSE set Done TRUE; (all tasks solved; new code frozen, if any).

2. Use to efficiently reset only the modified to FALSE (but do not pop yet).

3. IF (this means an online request for prolongation of the current prefix through a new token): WHILE Done FALSE and there is some yet untested token (untried since as value for ), set and Done Try ( ), where is 's probability according to current .

4. Use to efficiently restore only those changed since , thus also restoring instruction pointer and original search distribution . Return the value of Done.

It is important that instructions whose runtimes are not known in advance can be interrupted by Try at any time. Essentially, Try conducts a depth-first search in program space, where the branches of the search tree are program prefixes, and backtracking is triggered once the sum of the runtimes of the current prefix on all current tasks exceeds the prefix probability multiplied by the total time limit. A successful Try will solve all tasks, possibly increasing . In any case Try will completely restore all states of all tasks. Tracking / undoing effects of prefixes essentially does not cost more than their execution. So the in Def. 2.1 of -bias-optimality is not greatly affected by backtracking: ignoring hardware-specific overhead, we lose at most a factor 2. An efficient iterative (non-recursive) version of Try for a broad variety of initial programming languages was implemented in C.

Next: OOPS For Finding Universal Up: Optimal Ordered Problem Solver Previous: Optimal Ordered Problem Solver
Juergen Schmidhuber 2003-02-25