Re: Questions on Russell's "Why Occam" paper

From: Russell Standish <>
Date: Tue, 7 Jun 2005 10:19:49 +1000

On Mon, Jun 06, 2005 at 01:51:36PM -0700, "Hal Finney" wrote:
> Another area I had trouble with in Russell's answer was the concept of
> a prefix map. I understand that a prefix map is defined as a mapping
> whose domain is finite bit strings such that none of them are a prefix
> of any other. But I'm not sure how to relate this to the infinite bit
> strings that are "descriptions".

A prefix map attaches the same output to all strings that share a
common finite length prefix.

> In particular, if "an observer attaches sequences of meanings to sequences
> of prefixes of one of these strings", then it seems that he must have a
> domain which does allow some inputs to be prefixes of others. Isn't that
> what "sequences of prefixes" would mean? That is, if the infinite string
> is 01011011100101110111..., then a sequence of prefixes might be 0, 01,
> 010, 0101, 01011, .... Does O() apply to this sequence of prefixes? If
> so then I don't think it is a prefix map.

Yes I agree this is vague, and seemingly contradictory. I'm not sure
how to make this more precise, but one way to read the paper is to
treat observers as prefix maps for section 2 (Occam's razor), and then
for section 3 (White Rabbit problem) ignore the prefix property.

It could be that the way of making this more precise is to assume
observers have some internal state that is constantly updated (a time
counter perhaps), so actually going through a sequence of prefix maps
in (psychological) time, but at this stage I don't have an answer.

> I want to make it clear by the way that my somewhat pedantic and labored
> examination of this page is not an attempt to be difficult or
> stubborn.

Even being difficult and stubborn has its place (to help winkle out
subtle errors of logic eg), so long as you relax enough at other times to
obtain understanding. I appreciate the effort in any case.

> Rather, I find that by the third page, I don't understand what is going
> on at all! Even the very first sentence, "In the previous sections, I
> demonstrate that formal mathematical systems are the most compressible,
> and have highest measure amongst all members of the Schmidhuber ensemble,"
> has me looking to see if I skipped a page! I don't see where this is
> discussed in any way.

This is pretty much a tautology. Formal mathematical systems are a
means of compressing data in the form of facts about numbers. If one
were to include all such possible compression schemes, rather than
just the systems studies by mathematicians to date, one would end up
with the set of Turing machines, or equivalently of computable
functions. The Occam's razor result clearly relates measure to the
amount of compressibility in the description.

Perhaps such a view of mathematics is strange. Certainly I find it
strange when Stephen Wolfram says mathematics is incapable of
understanding complex phenomena, and one should cellular automata
instead. To me, cellular automata are just another example of a
mathematical system.

> So I hope that by pinning down and crystalizing
> exactly what the first page is claiming, it will help me to see what
> the more interesting third page is actually able to establish. I think
> Paddy is in much the same situation.
> Hal Finney

I hope so too.

*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
A/Prof Russell Standish                  Phone 8308 3119 (mobile)
Mathematics                         	       0425 253119 (")
UNSW SYDNEY 2052                      
            International prefix  +612, Interstate prefix 02

Received on Mon Jun 06 2005 - 21:20:44 PDT

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