# Re: Predictions & duplications

From: Russell Standish <R.Standish.domain.name.hidden>
Date: Wed, 17 Oct 2001 08:53:54 +1000 (EST)

juergen.domain.name.hidden wrote:
>
>
> 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.

This sounds more like a probability distribution than a measure. In
the set of all descriptions, we only consider infinite length
bitstrings. Finite length bitstrings are not members. However, we can
identify finite length bitstrings with subsets of descriptions. The
empty string corresponds to the full set of all descriptions, so the
first line M(empty string)=1 implies that the measure is normalisable
(ie a probability distribution).

As I said before, non-normalisable measures are considered measures by
the mathematical community - and the uniform measure over the set of
all descriptions is well defined.

>
> 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/
>
>

----------------------------------------------------------------------------
Dr. Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967, 8308 3119 (mobile)
UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")
Australia R.Standish.domain.name.hidden
Room 2075, Red Centre http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
Received on Tue Oct 16 2001 - 16:12:22 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST