PPT Slide

Hutter’s search algorithm (on Schmidhuber’s SNF grant 61847)

• Let p*:X?Y be a given algorithm or specification.

• Let p be any algorithm, computing provably the same function as p*

• with computation time provably bounded by the function tp(x).

• timetp(x) is the time needed to compute the time bound tp(x).

• Then the algorithm Mp* computes p*(x) in time

timeMp(x) < 5·tp(x) + dp·timetp(x) + cp

• with constants cp and dp depending on p but not on x.

• Neither p, tp, nor the proofs need to be known in advance for the construction of Mp* (x).

Previous slide

Next slide

Back to first slide

View graphic version