Searching for Bobby Fisher

One of the cool results of computer science which I recently learned is Levin’s universal search. Suppose you have a function f from a set X to a set Y. Many problems in computer science ask for you to invert this problem, i.e. given a y in Y, find x such that f(x)=y (there may be multiple such x’s but let’s not worry too much about that let’s just say you want to find an x such that f(x)=y.) Further lets assume that we have an efficient method for evaulating f(x). Thus, we may efficiently test whether a possible solution, x, satisfies the desired f(x)=y. OK, so that’s the problem. How do you solve it?
Well here is what Levin proposed. Consider running all possible programs which can solve this problem. We will do this serial, but with the time spent running each program which is proportional to 2^(-l(p)) where l(p) is the length of the program p. So we will be running shorter programs more often than we are running longer programs. There is a program q, which is the fastest program for solving our problem. This program runs in time T(q). Eventually our program will execute this program and get the correct result. How long does this take? A quick calculation shows that this time is at works 2^(l(q)) (T(q)+Tv) where Tv is the time to verify that the answer is correct (not included in T(q)). Thus, up to 2^(l(q)) the program is the fastest possible. Think about a class of programs now: notice that we will have produced an algorithm for this inversion problem which is, up to this huge multiplicative constant optimal. If we were to use big-O notation, this constant would be hidden and we would say assymptotically we have the most efficient algorithm!
Needless to say, the multiplicative constant DOES matter and in most cases is ridiculously large. But the story doesn’t end here. Recently Marcus Hutter has shown how to make this multiplicative constant 5 (Hutter’s work also solves a broad classes than the one described above.) What’s the catch this time? The catch this time is that there is an additive constant which is huge!