General Search methods and Kolmogorov Complexity

The theory of Kolmogorov complexity provides a basis for building optimal universal predictors as well as optimally fast search algorithms for a wide variety of computer science problems. In practical work we will continue to develop general yet computable, feasible search and learning algorithms based on or inspired by concepts of Kolmogorov complexity theory, extending principles of Levin´s non-incremental universal search, Hutter´s asymptotically ``fastest´´ algorithm for all well-defined problems, Schmidhuber´s Optimal Ordered Problem Solver OOPS and Goedel machine, and recent work on online time allocation to learning algorithms. In theoretical work we will study certain limits of asymptotically optimal search algorithms, related to the constants hidden in the asymptotic O()-notation. Furthermore, we will try to prove exact coding theorems for generalized Turing machines.Subgoals include: (1) Find general theoretical limitations for the constant slowdown of asymptotically optimal search and identify special classes of tasks that allow for more efficient solutions than the general case. (2) Analyze which conditions a sequence of tasks and an incremental learning mechanism have to satisfy such that a universal incremental learner can indeed expect to profit from experience. (3) Address the problem of search in program space from the time allocation point of view, extending and applying search methods that fit our recent frameworks. (4) Apply variants of our methods to challenging problems, automatically collecting experience with simpler tasks such that hard tasks become solvable.