## To find and then freeze qn+1, do in parallel:

## SEARCH1: test all prefixes on all tasks ? n+1

## SEARCH2: test only prefixes starting with qn, and only on task n+1! (safe because we know such prefixes solve all tasks ? n)

## Both searches depth-first: branches of search tree are program prefixes; backtrack (restore tasks and states) once the sum of runtimes of current prefix on all current tasks exceeds prefix probability times current search time limit

## 8-bias-optimal: lose at most factor 2 for SEARCH2, factor 2 for backtracking, factor 2 for incremental time limit doubling

Previous slide | Next slide | Back to first slide | View graphic version |

Back to J. Schmidhuber's OOPS page