Next: Universal TM-Induced Measures Up: Measures and Probability Distributions Previous: Approximable and Cumulatively Enumerable

## TM-Induced Distributions and Convergence Probability

Suppose TM 's input bits are obtained by tossing an unbiased coin whenever a new one is requested. Levin's universal discrete enumerable semimeasure [28,14,16] or semidistribution is limited to and halting programs:

Definition 4.11 (m)
 (23)

Note that if universal. We will now generalize this in obvious but nontraditional ways to and nonhalting programs for MTMs, EOMs, and GTMs.

Definition 4.12 ()   Suppose 's input bits are obtained by tossing an unbiased coin whenever a new one is requested.
 (24)

where .

Program Continua. According to Def. 4.12, most infinite have zero probability, but not those with finite programs, such as the dyadic expansion of . However, a nonvanishing part of the entire unit of probability mass is contributed by continua of mostly incompressible strings, such as those with cumulative probability computed by the following class of uncountably many infinite programs with a common finite prefix : repeat forever: read and print next input bit.'' The corresponding traditional measure-oriented notation for

would be

For notational simplicity, however, we will continue using the sign to indicate summation over uncountable objects, rather than using a measure-oriented notation for probability densities. The reader should not worry about this -- the theorems in the remainder of the paper will focus on those with ; density-like nonzero sums over uncountably many bitstrings, each with individual measure zero, will not play any critical role in the proofs.

Definition 4.13 (Universal TM-Induced Distributions )   If denotes a set of TMs with universal element , then we write
 (25)

We have for , the subset of C-describable . The attribute universal is justified, because of the dominance , due to the Invariance Theorem (compare Proposition 3.1).

Since all programs of EOMs and MTMs converge, and are proper probability distributions on . For instance, . , however, is just a semidistribution. To obtain a proper probability distribution , one might think of normalizing by the convergence probability :

Definition 4.14 (Convergence Probability)   Given GTM T, define

where

not describable. Uniquely encode each TM as a finite bitstring, and identify with the corresponding sets of bitstrings. While the function is c.e., the function is not even describable, essentially due to Theorem 2.1.

Even and are generally not describable for , in the sense that there is no GTM that takes as an input a finite description (or program) of any M-describable or E-describable and converges towards or . This is because in general it is not even weakly decidable (Def. 2.11) whether two programs compute the same output. If we know that one of the program outputs is finite, however, then the conditions of weak decidability are fulfilled. Hence certain TM-induced distributions on are describable, as will be seen next.

Definition 4.15 (TM-Induced Cumulative Distributions)   If denotes a set of TMs with universal element , then we write (compare Def. 4.10):
 (26)

Lemma 4.1   For , is c.e.

Proof. The following algorithm computes (compare proof of Theorem 3.3):

Initialize the real-valued variable by 0, run all possible programs of EOM dovetail style; whenever the output of a program prefix starts with some for the first time, set ; henceforth ignore continuations of .
In this way enumerates . Infinite are not problematic as only a finite prefix of must be read to establish if the latter indeed holds.

Similarly, facts of the form can be discovered after finite time.

Corollary 4.1   For , is approximable or describable as the difference of two c.e. values:
 (27)

Now we will make the connection to the previous subsection on semimeasures on .

Next: Universal TM-Induced Measures Up: Measures and Probability Distributions Previous: Approximable and Cumulatively Enumerable
Juergen Schmidhuber 2003-02-13