Dominant and Universal (Semi)Measures
Next: Universal Cumulatively Enumerable Measure Up: Measures and Probability Distributions Previous: Measures and Probability Distributions

## Dominant and Universal (Semi)Measures

The next three definitions concerning semimeasures on B* are almost but not quite identical to those of discrete semimeasures [#!LiVitanyi:97!#, p. 245 ff] and continuous semimeasures [#!LiVitanyi:97!#, p. 272 ff] based on the work of Levin and Zvonkin [#!Zvonkin:70!#].

Definition 4.1 (Semimeasures)   A (binary) semimeasure is a function that satisfies:

 (17)

where is a function satisfying .

A notational difference to the approach of Levin [#!Zvonkin:70!#] (who writes ) is the explicit introduction of . Compare the introduction of an undefined element u by Li and Vitanyi [#!LiVitanyi:97!#, p. 281]. Note that . Later we will discuss the interesting case , the a priori probability of x.

Definition 4.2 (Dominant Semimeasures)   A semimeasure dominates another semimeasure if there is a constant such that for all

 (18)

Definition 4.3 (Universal Semimeasures)   Let be a set of semimeasures on B*. A semimeasure is universal if it dominates all .

In what follows, we will introduce describable semimeasures dominating those considered in previous work ([#!Zvonkin:70!#], [#!LiVitanyi:97!#, p. 245 ff, p.272 ff]).

Next: Universal Cumulatively Enumerable Measure Up: Measures and Probability Distributions Previous: Measures and Probability Distributions
Juergen Schmidhuber
2001-01-09

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI