## View n-th bitstring (0,1,01,10,11,100,…) as a possible program for a universal Turing machine.

## Until problem solved: for all n: execute one instruction of n-th bitstring every 2n steps on average.

## Asymptotically optimal: Suppose unknown fastest program solves problem of size k within f(k) steps.

## Lsearch will take at most O(2n f(k)) = O(f(k)) steps.

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

Back to J. Schmidhuber's OOPS page