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 :
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.