Next: A Novel Universal Cumulatively
Up: Measures and Probability Distributions
Previous: Measures and Probability Distributions
Traditionally, the algorithmic probability of is
defined as the probability of producing by a halting program
for a universal TM whose input bits are selected randomly.
Since some of the possible input sequences cause nonhalting
computations, the individual probabilities do not add up to 1.
This and related issues inspired work on semimeasures
[40,45,41,17,30]
as opposed to classical measures considered in traditional statistics.
The next three definitions concerning semimeasures on are almost
but not quite identical to those of discrete semimeasures
[30, p. 245 ff]
and continuous semimeasures
[30, p. 272 ff]
based on the work of Levin and Zvonkin
[45].
Definition 4.1 (Semimeasures)
A (binary) semimeasure
is a function
that satisfies:

(15) 
where
is a function
satisfying
.
A notational difference to the approach of Levin
[45]
(who writes
)
is the explicit introduction of . Compare the
introduction of an undefined element by Li and
Vitanyi [30, p. 281].
Note that
.
Later we will discuss the interesting case
,
the a priori probability of .
Definition 4.2 (Dominant Semimeasures)
A semimeasure
dominates another semimeasure
if
there is a constant
such that for all

(16) 
Definition 4.3 (Universal Semimeasures)
Let
be a set of semimeasures on
.
A semimeasure
is universal if it
dominates all
.
In what follows,
we will introduce novel, nonenumerable but describable semimeasures dominating the
c.e. ones considered
in previous work [45][30, p. 245 ff, p.272 ff].
Next: A Novel Universal Cumulatively
Up: Measures and Probability Distributions
Previous: Measures and Probability Distributions
Juergen Schmidhuber
20030213