optimal search algorithm

[juergen@idsia.ch]

Dear connectionists,

Recently Marcus Hutter has developed a very general, asymptotically
optimal search method that should be of interest to researchers in the
areas of reinforcement learning & neural networks & AI. The method is
not limited to machine learning problems though - I believe it will find
its way into general computer science textbooks. With the benefit of
hindsight I find it amazing that it has remained undiscovered up until
the turn of the century.

-------------------------------------------------------------------------

The fastest and shortest algorithm for all well-defined problems
Marcus Hutter, IDSIA 

An algorithm M is described that solves any well-defined problem p as
quickly as the fastest algorithm computing a solution to p, save for
a factor of 5 and low-order additive terms. M optimally distributes
resources between the execution of provably correct p-solving programs
and an enumeration of all proofs, including relevant proofs of program
correctness and of time bounds on program runtimes. M avoids Blum's
speed-up theorem by ignoring programs without correctness proof. M has
broader applicability and can be faster than Levin's universal search, the
fastest method for inverting functions save for a large multiplicative
constant. An extension of Kolmogorov complexity and two novel natural
measures of function complexity are used to show that the most efficient
program computing some function f is also among the shortest programs
provably computing f.

ftp://ftp.idsia.ch/pub/techrep/IDSIA-16-00.ps.gz

-------------------------------------------------------------------------



Juergen Schmidhuber                                      www.idsia.ch