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.<p>It is an algorithm that solves with the same limiting O(n) behavior as the fastest algorithm that <i>provably</i> 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 <i>proof</i> (in that proof system) that the algorithm which always returns 0 is accurate and faster than the algorithm which computes it out in detail.<p>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.