Next: A Novel Universal Cumulatively Up: Measures and Probability Distributions Previous: Measures and Probability Distributions

## Dominant and Universal (Semi)Measures

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 2003-02-13