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 has a finite, never halting GTM
program that computes such that each output bit is revised at most
finitely many times; that is, each finite prefix of 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 -th bit of . Formal describability
thus pushes constructivism [5,2] to the extreme,
barely avoiding the nonconstructivism embodied by even less restrictive
concepts of describability -- compare -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
(the length of the shortest halting program computing ) 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
[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
, save for a constant factor independent of . 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 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 the
probability that a universal EOM whose input bits are chosen randomly
produces an output starting with (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
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.