Suppose TM T's input bits are obtained by tossing an unbiased coin
whenever a new one is requested.
Levin's universal discrete enumerable semimeasure
[#!Levin:73a!#,#!Chaitin:75!#,#!Gacs:74!#]
or semidistributionm
is limited to B* and halting programs:
Note that
if T universal.
Let us now generalize this to
and nonhalting programs:
Definition 4.12 (tex2html_wrap_inline$P_T, KP_T$)
Suppose T's input bits are obtained by tossing an unbiased coin
whenever a new one is requested.
(26)
where
.
Program Continua.
According to Def. 4.12, most
infinite x 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 2-l(q) computed by the following class of
uncountably many infinite programs with a common finite prefix q: ``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 feel uncomfortable
with this -- the theorems in the remainder of the paper
will focus on those
with P(x)>0; density-like nonzero sums
over uncountably many bitsrings, each
with individual measure zero, will not play any critical role in the proofs.
Definition 4.13 (Universal TM-Induced Distributions tex2html_wrap_inline$P^C;KP^C$)
If C denotes a set of TMs with universal element UC, then we write
PC(x) = PUC(x);
KPC(x) := -lgPC(x) forPC(x)>0.
(27)
We have
PC(x) > 0 for
,
the subset of C-describable
.
The attribute universal is justified, because
of the dominance
PT(x) = O(PC(x)),
due to the Invariance Theorem
(compare Def. 3.3).
Since all programs of EOMs and MTMs
converge, PE and PM are proper probability distributions on
.
For instance,
.
PG, however, is just a semidistribution.
To obtain a proper probability
distribution PNT, one might think of normalizing
by the convergence probability :
Definition 4.14 (Convergence Probability)
Given GTM T, define
where
Describability issues.
Uniquely encode each TM T as a finite bitstring,
and identify M, E, G with the corresponding sets of bitstrings.
While the function
is describable, even enumerable,
the function
is not, essentially due to Theorem 2.1.
Even PE(x) and PM(x) are generally not describable for
,
in the sense
that there is no GTM T that takes as an input a finite description (or
program) of any M-describable or E-describable
and
converges towards PM(x) or PE(x). 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 B* are describable, as will be seen next.
Definition 4.15 (TM-Induced Cumulative Distributions)
If C denotes a set of TMs with universal element UC, then we write
(compare Def. 4.10):
Proof. The following algorithm computes CPE(x) (compare
proof of Theorem 3.3):
Initialize the
real-valued variable V by 0, run all possible programs of EOM T dovetail
style; whenever the output of a program prefix q starts with some
for the first time, set
V:= V+ 2-l(q);
henceforth ignore continuations of q.
In this way V enumerates
CPE(x). Infinite p are not
problematic as only a finite prefix of p 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 ,
PE(x) is approximable or describable as the difference of two enumerable values:
(29)
Now we will make the connection to the previous subsection
on semimeasures on B*.