Here "as quickly as the fastest algorithm" means: it takes at most 5x longer, plus a colossal enormous additive constant.
To be a bit more precise, suppose you have a problem parameterized by some numbers a,b,c,...,z, and suppose there is some algorithm A that provably solves the problem, for any parameter values, in time T(a,b,c,...,z). Then Hutter's algorithm solves the problem im time at most 5T(a,b,c,...,z) + C where C, unfortunately, is something that looks like (smaller stuff) . 2^L where L is the length of the shortest proof that A solves the problem in time T(a,b,c,...,z).
That timing information probably gives a clue as to how the algorithm works. Modulo oversimplification and handwaving, it enumerates all possible proofs of the form "such-and-such an algorithm solves the problem at takes at most such-and-such an amount of time to do it", and interleaves this with executing whatever algorithm it's currently got the best time bound for. There's a bit of subtlety in scheduling things so that it doesn't waste lots of time on what turn out to be worse algorithms. And that's basically it.
Good summary. As I finished working through his algorithm description, I wondered at the sentence in the summary that motivated me to read closely: 'An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms.' "Low-order additive terms"? Come on.
I've spoken briefly to Hutter about this, but the description is simply not correct. Though you'd have to read the paper to notice; Hutter makes the same mistake.
It is an algorithm that solves with the same limiting O(n) behavior as the fastest algorithm that provably solves a problem, relative to the proof system. This is a very large difference, never mind additive or multiplicative constants! For example, if my proof system is Peano arithmetic, and I try to compute the limiting behavior of Goodstein sequences, the answer is always "0" but there exists no proof (in that proof system) that the algorithm which always returns 0 is accurate and faster than the algorithm which computes it out in detail.
I'm afraid that the descriptions by Marcus Hutter (or Juergen Schmidhuber) of what their algorithms do cannot be taken at face value. You have to read through the paper and apply your own skepticism if you want to know. They're interesting algorithms, but there seems to have been some kind of race or academic incentive to gloss over as many limitations as possible.
A similarly misleading statement in the abstract: "the most efficient program computing some function f is also among the shortest programs provably computing f."
If this were actually true, it would reveal an extremely deep principle about efficiency.
But this is not the actual "most efficient" program that is short, it is Hutter's asymptotically efficient program, which out of some strange reason Hutter has taken to calling "the fastest program", which it is not. It is never the most efficient program (it makes use of a program more efficient than itself). It is "among the shortest" such programs in the sense that it can be specified using a fixed framework plus the shortest program such that other programs which solve the problem can be proven equivalent to it, relative to the proof system.
I was pretty disappointed when I worked that out - from the abstract's statement that the most efficient algorithm is always among the shortest, I was expecting to discover some deep principle about skipping unnecessary steps, or some such.
So am I correct in interpreting that this "fastest program" f means the function that M is fastest at identifying, proving, and executing, rather than the function whose execution time is fastest in a vacuum?
If I understand correctly, the "fastest program f" is the one which M not only proves to solve the problem, but also proves to solve more quickly than any other provable time bound. That is, it's not so much "fastest program f" as "program f with the lowest provable time bound among programs with provable time bounds relative to the proof system". This is another critical constraint that I should have mentioned earlier - the result really is a lot weaker than the abstract makes it sound.
I think that's slightly incorrect. The proof M is looking for is of the following statement: "P is an algorithm that solves the problem and T is an algorithm that is guaranteed to output, for any input, an upper bound on the running time of P for that input." There's no requirement that P should be proved to be faster than some other program.
Anyhow, your criticism of the result's limited applicability still stands. I can't resist offering another nitpick: it's curious that the author neglected to mentioned that the proof system must be sound.
To be a bit more precise, suppose you have a problem parameterized by some numbers a,b,c,...,z, and suppose there is some algorithm A that provably solves the problem, for any parameter values, in time T(a,b,c,...,z). Then Hutter's algorithm solves the problem im time at most 5T(a,b,c,...,z) + C where C, unfortunately, is something that looks like (smaller stuff) . 2^L where L is the length of the shortest proof that A solves the problem in time T(a,b,c,...,z).
That timing information probably gives a clue as to how the algorithm works. Modulo oversimplification and handwaving, it enumerates all possible proofs of the form "such-and-such an algorithm solves the problem at takes at most such-and-such an amount of time to do it", and interleaves this with executing whatever algorithm it's currently got the best time bound for. There's a bit of subtlety in scheduling things so that it doesn't waste lots of time on what turn out to be worse algorithms. And that's basically it.