Re: Predictions & duplications

From: Juergen Schmidhuber <>
Date: Fri, 26 Oct 2001 15:45:48 +0200

> From: Juho Pennanen <>
> So there may be no 'uniform probability distribution' on the set of all
> strings, but there is the natural probability measure, that is in many
> cases exactly as useful.

Sure, I agree, measures are useful; I'm using them all the time. But in
general they are _not_ the same thing as probability distributions.

> From: Russell Standish <>
> The only reason for not accepting the simplest thing is if it can be
> shown to be logically inconsistent. This far, you have shown no such
> thing, but rather demonstrated an enormous confusion between measure
> and probability distribution.

Russell, this is really too much; please read any intro to measure
e.g., the one by Halmos. Measures in general are _not_ probability
distributions. They are more than that; you can view them as _sets_ of
probability distributions on sets that are related to each other in a
specific way. Probability density functions define measures and
in general aren't probability distributions either. The uniform PDF on
[0..1] yields the perfect trivial example; that's exactly why I used it
before. In the computability context, compare LI/Vitanyi 1997, chapters
4.3 (discrete sample space with (semi)distribution m(x)) vs chapter 4.5
(continuous sample space with (semi)measure M(x)).

> 1) Halting theorem implies the set of halting programs is of measure
> zero within the set of all programs

You mean, given a uniform measure? But why should you need the halting
theorem for this trivial statement? In fact, what exactly do you mean
halting theorem? (Schoenfield's book provides a good intro to
logic and computability theory.)

> The GP program (aka Universal Dovetailer) is not the simplest
> thing. The simplest describable thing is the set of all descriptions,
> that simply exist without being generated. That has precisely zero
> information or complexity, whereas the UD has some complexity of the
> order of a few 100 bits. The simplest prior is the uniform one, ie
> there is no bias whatsoever in the selection.

Exist without being generated? Precisely zero information or
complexity? But with respect to what? Any traditional definition of
information/simplicity requires the specification of a formal
method, such as a Turing machine. You don't need one? Then how do you
define information or complexity? How exactly do you define "simple" ?
Received on Fri Oct 26 2001 - 06:46:43 PDT

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