To allow us to efficiently undo 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 so-called ring of tasks, where 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 there are unsolved tasks ( ) AND there is enough time left () AND instruction pointer valid ( ) AND instruction valid ( ) AND no halt condition is encountered (e.g., error such as division by 0, or robot bumps into obstacle; evaluate conditions in the above order until first satisfied, if any) DO:
Interpret / execute token according to the rules of the given programming language, continually increasing by the consumed time. This may modify including instruction pointer and distribution , but not code . 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 (like in the round-robin method of standard operating systems). ELSE set Done TRUE; (all tasks solved; new code frozen, if any).
2. Use to efficiently reset only the modified to FALSE (the global mark variables will be needed again in step 3), but do not pop yet.
3. IF (i.e., if there is 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 ) DO:
Set and Done Try ( ), where is 's probability according to current distribution .
4. Use to efficiently restore only those changed since , thus restoring all tapes to their states at the beginning of the current invocation of Try. This will also restore instruction pointer and original search distribution . Return the value of Done.
Since the distributions are modifiable, we speak of
self-generated continuation probabilities.
As the variable
total code is growing,
its probability can be readily updated:
Example. In many programming languages the probability of token ``('', given a previous token ``WHILE'', equals 1. Having observed the ``('' there is not a lot of new code to execute yet -- in such cases the rules of the programming language will typically demand another increment of instruction pointer ip(r), which will lead to the request of another token through subsequent increment of the topmost code address. However, once we have observed a complete expression of the form ``WHILE (condition) DO (action),'' it may take a long time until the conditional loop -- interpreted via -- is exited and the top address is incremented again, thus asking for a new token.
The round robin Try variant above keeps circling through all unsolved tasks, executing one instruction at a time. Alternative Try variants could also sequentially work on each task until it is solved, then try to prolong the resulting on the next task, and so on, appropriately restoring previous tasks once it turns out that the current task cannot be solved through prolongation of the prefix solving the earlier tasks. One potential advantage of round robin Try is that it will quickly discover whether the currently studied prefix causes an error for at least one task, in which case it can be discarded immediately.
Nonrecursive C-Code. An efficient iterative (nonrecursive) version of Try for a broad variety of initial programming languages was implemented in C. Instead of local stacks , a single global stack is used to save and restore old contents of modified cells of all tapes / tasks.