Introduction and Outline

We extend the theory of algorithmic probability [40,25,13,31,41,45,28,29,16,14,17,37,1,30,39,9,42,24,23] by studying nonenumerable priors computable in the limit [19,33,15]. This leads to a hierarchy of generalizations of the concepts of universal prior and Kolmogorov complexity. For instance, many objects with high traditional Kolmogorov complexity have low generalized Kolmogorov complexity; many objects with low traditional algorithmic probability have high generalized algorithmic probability.

To set the stage for our main results, Section 2 (Preliminaries) introduces universal Turing Machines (TMs) more general than those considered in previous related work: unlike traditional TMs, General TMs or GTMs may edit their previous outputs (compare Burgin's inductive TMs [6]), and Enumerable Output Machines (EOMs) may do this provided the output does not decrease lexicographically. In the spirit of computability in the limit [19,33,15] we will define: a formally describable bitstring $x$ has a finite, never halting GTM program that computes $x$ such that each output bit is revised at most finitely many times; that is, each finite prefix of $x$ eventually stabilizes (Defs. 2.1-2.5); describable functions can be implemented by such programs (Def. 2.10); weakly decidable problems have solutions computable by never halting programs whose output is wrong for at most finitely many steps (Def. 2.11). This constructive notion of formal describability is less restrictive than the traditional notion of computability [43], mainly because we do not insist on the existence of a halting program that computes an upper bound of the convergence time of the $n$-th bit of $x$. Formal describability thus pushes constructivism [5,2] to the extreme, barely avoiding the nonconstructivism embodied by even less restrictive concepts of describability -- compare $Delta^0_n$-describability [34]. Theorem 2.1 will generalize the weakly decidable halting problem by demonstrating that it is not weakly decidable whether a finite string is a description of a describable object (there is a related insight for analytic TMs with real-valued inputs by Hotz, Vierke and Schieffer [21]).

Outline of main results. Section 3 generalizes the traditional concept of Kolmogorov complexity or algorithmic information [25,40,13] of finite $x$ (the length of the shortest halting program computing $x$) to the case of objects describable by nonhalting programs on EOMs and GTMs (Defs. 3.2-3.3). It is shown that the generalization for EOMs is describable, but the one for GTMs is not (Theorem 3.1). Certain objects are much more compactly encodable on EOMs than on traditional monotone TMs, and Theorem 3.3 shows that there are also objects with short GTM descriptions yet incompressible on EOMs and therefore ``more random'' than Chaitin's $Omega$ [14,10,39,9,42], the halting probability of a TM with random input, which is incompressible only on monotone TMs. This leads to a natural TM type-specific Kolmogorov complexity hierarchy expressed by Inequality (12).

Section 4 introduces the nondescribable convergence probability of a GTM (Def. 4.14) as well as very general formally describable (semi)measures that are computable in the limit. Unfortunately, Theorem 4.2 (proof by M. Hutter) shows that there is no universal describable measure that dominates all others, in the sense that it assigns higher probability to any bitstring $x$, save for a constant factor independent of $x$. In our search for universal measures we introduce cumulatively enumerable measures (CEMs, Def. 4.5), where the cumulative probability of all strings lexicographically greater than a given string $y$ is EOM-computable or computably enumerable (c.e.). In general the CEMs are not c.e., but they are computable in the limit, and they dominate the traditional c.e. priors studied in classic work by Solomonoff, Levin and others [40,45,29,16,17,37,41,14,30]. Theorem 4.1 shows that there is indeed a universal nonenumerable CEM. It is also shown that this CEM assigns to $x$ the probability that a universal EOM whose input bits are chosen randomly produces an output starting with $x$ (Corollary 4.3 and Lemma 4.2).

Section 5 establishes relationships between generalized Kolmogorov complexity and generalized algorithmic probability, extending previous work on c.e. semimeasures by Levin, Gács, and others [45,29,16,14,17,30]. For instance, Theorem 5.3 shows that the universal CEM assigns a probability to each c.e. object proportional to $frac{1}{2}$ raised to the power of the length of its minimal EOM-based description, times a small corrective factor. For GTMs there is no analogue statement, but at least we can show that objects with approximable probabilities yet without very short descriptions on GTMs are necessarily very unlikely a priori (Theorems 5.4 and 5.5). Additional suspected elegant links between generalized Kolmogorov complexity and probability are expressed in form of Conjectures 5.1-5.3.