It provides, for the first time, a mathematically sound theory of general AI and optimal decision making based on experience, identifying the limits of both human and artificial intelligence, and a yardstick for any future, scaled-down, practically feasible approach to general AI.

## 2.6 Optimal Curiosity And Creativity

No theory of AI will be convincing if it does not explain curiosity and creativity, which many consider as important ingredients of intelligence. We can provide an explanation in the framework of optimal reward maximizers such as those from the previous subsection.

It is possible to come up with theoretically optimal ways of improving the predictive world model of a curious robotic agent [28], extending earlier ideas on how to implement artificial curiosity [25]: The rewards of an optimal reinforcement learner are the predictor's improvements on the observation history so far. They encourage the reinforcement learner to produce action sequences that cause the creation and the learning of new, previously unknown regularities in the sensory input stream. It turns out that art and creativity can be explained as by-products of such intrinsic curiosity rewards: good observer-dependent art deepens the observer'sinsights about this world or possible worlds, connecting previously disconnected patterns in an initially surprising way that eventually becomes known and boring. While previous attempts at describing what is satisfactory art or music were informal, this work permits the first technical, formal approach to understanding the nature of art and creativity [28].

## 2.7 Computable, Asymptotically Optimal General Problem Solver

Using the Speed Prior [26] one can scale down the universal approach above such that it becomes computable. In what follows we will mention general methods whose optimality criteria explicitly take into account the computational costs of prediction and decision making—compare [15].

The recent asymptotically optimal search algorithm for all well-defined problems
[11] allocates part of the total search time to searching the space of proofs for provably correct candidate programs with provable upper runtime bounds; at any given time it focuses resources on those programs with the currently best proven time bounds. The method is as fast as the initially unknown fastest problem solver for the given problem class, save for a constant slowdown factor of at most 1 + ǫ, ǫ > 0, and an additive constant that does not depend on the problem instance!

Is this algorithm then the *holy grail* of computer science? Unfortunately not quite, since the additive constant (which disappears in the O()-notation of theoretical CS)
may be huge, and practical applications may not ignore it. This motivates the next section, which addresses all kinds of formal optimality (not just asymptotic optimality).

## 2.8 Fully Self-Referential, Self-Improving Godel Machine ¨

We may use G¨odel's self-reference trick to build a universal general, fully self-referential, self-improving, optimally efficient problem solver [29]. A G¨odel Machine is a com7