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).
Back to J. Schmidhuber's OOPS page