response: Levin search

[Juergen Schmidhuber]

My response to David Wolpert's response to my response:

Although it is true that ``we have *no* a priori reason 
to believe that targets with low Kolmogorov complexity
(or anything else) are/not likely to occur in the real 
world'', it's also true that Levin search (LS) has the 
optimal order of search complexity for a broad class of
*non-incremental* search problems (David did not agree).
This is a well-known fact of theoretical computer
science.

Why is LS as efficient as any other search algorithm?
Because LS effectively *runs* all the other search
algorithms, but in a smart way that prevents it
from loosing too much time with "wrong" search 
algorithms.

David is right, however, by saying that ``In practice, 
it may (or may not) be a good idea to use an algorithm
that searches for low Levin complexity rather than one 
that works by other means.'' One reason for this is: in
practice, your problem size is always limited, and you 
*do* have to worry about the (possibly huge) constant 
buried in the notion of "optimal order of search 
complexity".

Note that all my recent comments refer to *non-incremental*
search --- for the moment, I am not addressing generalization
issues. Can LS help us to improve certain kinds of *incremental*
search and learning? We are currently trying to figure 
this one out.

Juergen Schmidhuber