An algorithm that solves any problem as quickly as the fastest algorithm

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.

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.