## 4 Open Problems in Universal Induction
Strictly speaking, a Bayesian needs to choose the hypothesis/model class before seeing the data, which seldom reflects scientific practice [5]. * **Other issues/problems**. Comparison to [PERSON]'s confirmation theory [149] and Laplace rule [150], allowing for continuous model classes, how to incorporate prior knowledge [151, 152], and others. [PERSON]'s theory has already been intensively studied in the predictive setting [18, 50, 89, 91, 94] mostly confirming its power, with the occasional unexpected exception [103]. Important open questions are:  
* **Prediction of selected bits. ** Consider a very simple and special case of problem 5.i, a binary sequence that coincides at even times with the preceding (odd) bit, but is otherwise incomputable. Every child will quickly realize that the even bits coincide with the preceding odd bit, and after a while perfectly predict the even bits, given the past bits. The incomputability of the sequence is no hindrance. It is unknown whether [PERSON] works or fails in this situation. I expect that a solution of this special case will lead to general useful insights and advance this theory (cf. problem 5.i). * **Identification of \"natural\" Turing machines. ** In order to pin down the additive/multiplicative constants that plague most results in AIT, it would be highly desirable to identify a class of \"natural\" UTMs/USMs which have a variety of favorable properties. A more moderate approach may be to consider classes \({\cal C}_{i}\) of universal Turing machines (UTM) or universal semimeasures (USM) satisfying certain properties \({\cal P}_{i}\) and showing that the intersection \(\cap_{i}{\cal C}_{i}\) is not empty. Indeed, very occasionally results in AIT only hold for particular (subclasses of) UTMs [153]. A grander vision is to find the single \"best\" UTM or USM [154] (a remarkable approach). * **Martin-Lof convergence. ** Quite unexpectedly, a loophole in the proof of Martin-Lof (M.L.) convergence of \(M\) to \(\mu\) in the literature has been found [101]. In [102] it has been shown that this loophole cannot be fixed, since M.L.-convergence actually can fail. The construction of non-universal (semi)measures \(D\) and \(W\) that M.L. converge to \(\mu\)[103] partially rescued the situation. The major problem left open is the convergence rate for \(W\frac{M.L.}{\longrightarrow}\mu\). The current bound for \(D\frac{M.L. }{\longrightarrow}\mu\) is double exponentially worse than for \(M\frac{w.p.1}{\longrightarrow}\mu\). It is also unknown whether convergence in ratio holds. Finally, there could still exist _universal_ semimeasures \(M\) (dominating all enumerable semimeasures) for which M.L.-convergence holds. In case they exist, they probably have particularly interesting additional structure and properties. * **Generalized mixtures and convergence concepts. ** Another interesting and potentially fruitful approach to the above convergence problem is to consider other classes of semimeasures \(\mathcal{M}\)[63, 66, 86], define mixtures \(\xi\) over \(\mathcal{M}\), and (possibly) generalized randomness concepts by using this \(\xi\) to define a generalized notion of randomness. Using this approach, in [87] it has been shown that convergence holds for a subclass of Bernoulli distributions if the class is dense, but fails if the class is gappy, showing that a denseness characterization of \(\mathcal{M}\) could be promising in general. See also [155, 156]. * **Lower convergence bounds and defect of \(M\). ** One can show that \(M(\bar{x}_{t}|x_{<t})\geq 2^{-K(t)}\), i.e. the probability of making a wrong prediction \(\bar{x}_{t}\) converges to zero slower than any computable summable function. This shows that, although \(M\) converges rapidly to \(\mu\) in a cumulative sense, occasionally, namely for simply describable \(t\), the prediction quality is poor. An easy way to show the lower bound is to exploit the semimeasure defect of \(M\). Do similar lower bounds hold for a proper ([PERSON]) normalized measure \(M_{norm}\)? I conjecture the answer is yes, i.e.