## 3 History and State-of-the-Art  
The theory of UAI and AIXI build on the theories of universal induction, universal prediction, universal decision making, and universal agents. From a historical and research-field perspective, the _AIXI model_ is based on two otherwise unconnected fundamental theories:  
1. The major basis is _Algorithmic information theory_[41], initiated by [37; 38; 57], which builds the foundation of complexity and randomness of individual objects. It can be used to quantify [PERSON]'s razor principle (use the simplest theory consistent with the data). This in turn allowed _[PERSON]_ to come up with a _universal theory of induction_[37; 50]. 2. The other basis is the theory of optimal _sequential decisions_, initiated by [PERSON] [58] and [PERSON] [30]. This theory builds the basis of modern _reinforcement learning_[59]. This section outlines the history and state-of-the-art of the theories and research fields involved in the AIXI model. **Algorithmic information theory (AIT). ** In the 1960's [37; 38; 57] introduced a new machine independent complexity measure for arbitrary computable data. The Kolmogorov complexity \(K(x)\) is defined as the length of the shortest program on a universal Turing machine that computes \(x\). It is closely related to [PERSON]'s universal a-priori probability \(M(x)\!\approx\!2^{-K(x)}\) (see above), Martin-Lof randomness of individual sequences [60], time-bounded complexity [61], universal optimal search [62], the speed prior [63], the halting probability \(\Omega\)[64], strong mathematical undecidability [65], generalized probability and complexity [66], algorithmic statistics [67; 68; 69], and others. Despite its incomputability, AIT found many applications in philosophy, practice, and science: The minimum message/description length (MML/MDL) principles [70; 71; 72] can be regarded as a practical approximation of Kolmogorov complexity. MML&MDL are widely used in machine learning applications [73; 74; 75; 76; 77; 6; 77]. The latest, most direct and impressive applications are via the universal similarity metric [46; 78]. [PERSON] produced another range of impressive applications to neural networks [79; 80], in search problems [81], and even in the fine arts [82]. By carefully approximating Kolmogorov complexity, AIT sometimes lead to results unmatched by other approaches. Besides these practical applications, AIT is used to simplify proofs via the incompressibility method, improves Shannon information, is used in reversible computing, physical entropy and Maxwell daemon issues, artificial intelligence, and the asymptotically fastest algorithm for all well-defined problems [27, 40, 41, 83, 84]. **Universal Solomonoff induction. ** How and in which sense induction is possible at all has been subject to long philosophical controversies [1, 27, 85]. Highlights are [PERSON] principle of multiple explanations [34], [PERSON]'s razor (simplicity) principle [33], and [PERSON] rule for conditional probabilities [5, 36]. [PERSON] [37] elegantly unified these aspects with the concept of universal Turing machines [35] to one formal theory of inductive inference based on a universal probability distribution \(M\), which is closely related to Kolmogorov complexity \(K\) (\(M(x)\approx 2^{-K(x)}\)). The theory allows for optimally predicting sequences without knowing their true generating distribution \(\mu\)[50], and presumably solves the induction problem. The theory remained for more than 20 years at this stage, till the work on AIXI started, which resulted in a beautiful elaboration and extension of [PERSON]'s theory.