A similarly misleading statement in the abstract:  "the most efficient program computing some function f is also among the shortest programs provably computing f."<p>If this were actually true, it would reveal an extremely deep principle about efficiency.<p>But this is not the <i>actual</i> "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 <i>most</i> 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.<p>I was pretty disappointed when I worked that out - from the abstract's statement that <i>the</i> most efficient algorithm is always among the shortest, I was expecting to discover some deep principle about skipping unnecessary steps, or some such.