Multitasking & Prefix Tracking By Recursive Procedure ``Try''

In both subsearches of Method 3.1 (steps 2 and 3), Realistic OOPS evaluates alternative prefix continuations by a practical, token-oriented backtracking procedure that efficiently reuses limited storage and can deal with several tasks in parallel, given some code bias in the form of previously found code.

The novel recursive method Try below essentially conducts a depth-first search in program space, where the branches of the search tree are program prefixes (each modifying a bunch of task-specific states), and backtracking (partial resets of partially solved task sets and modifications of internal states and continuation probabilities) is triggered once the sum of the runtimes of the current prefix on all current tasks exceeds the current time limit multiplied by the prefix probability (the product of the history-dependent probabilities of the previously selected prefix components in $Q$). This ensures near-bias-optimality (Def. 2.1), given some initial probabilistic bias on program space $\subseteq Q^*$.

Given task set $R$, the current goal is to solve all tasks $r \in R$, by a single program that either appropriately uses or extends the current code $q_{0:a_{frozen}}$ (no additional freezing will take place before all tasks in $R$ are solved).

Back to OOPS main page