Re: Predictions & duplications

From: <juergen.domain.name.hidden>
Date: Tue, 16 Oct 2001 17:40:03 +0200

Confusion about what's a measure?
What's a distribution?
Simple but important!
For bitstrings x:

M measure:
M(empty string)=1
M(x) = M(x0)+M(x1) nonnegative for all finite x.

P probability distribution:
Sum_x P(x) = 1; P(x) nonnegative

---
M semimeasure - replace "=" by ">=":
M(x) >= M(x0)+M(x1) 
P semidistribution - replace:
Sum_x P(x) <= 1
---
Examples:
1. Distribution: E.g., integers n: P(n) = 6/(Pi n^2)
2. Semidistribution: m(x) = probability of guessing a halting program 
   for x (BTW, Hal, this was first published by Levin in 1974, not by 
   Chaitin in 1975)
3. Measure: E.g., each x of size n gets weight 2^-n 
4. Semimeasure: E.g., mu^M(x) = probability of guessing a halting or 
   nonhalting monotone TM program whose output starts with x 
Check out: Measures and Probability Distributions
Section 4 of "Algorithmic TOEs"
http://www.idsia.ch/~juergen/toesv2/node15.html
Juergen Schmidhuber
http://www.idsia.ch/~juergen/
http://www.idsia.ch/~juergen/everything/html.html
http://www.idsia.ch/~juergen/toesv2/

Received on Tue Oct 16 2001 - 08:49:08 PDT