Re: *THE* PUZZLE (was: ascension, Smullyan, ...)

From: Russell Standish <>
Date: Wed, 21 Jun 2006 13:09:44 +1000

On Thu, Jun 22, 2006 at 11:24:22AM +0200, Bruno Marchal wrote:
> > Whereas I don't think it does. It can be applied in an absolute way
> > (such as you refer) or in a relative subjective way (which is how I do
> > it). In fact I make the point that absolute measures aren't meaningful
> > - there just isn't an absolutely given UTM.
> From a recursive or computationalist standpoint there is. In particular
> "absolute measure" *can* be defined up to a constant.

The constant, unfortunately, is infinity! What is true is that the
complexity of two strings x and y will differ by no more than a
constant independent of the strings x and y when measured by two
different machines.

But the reverse case is where the strings x and y are fixed, and the
machines variables. For any two strings x, y, it is possible to find
machines U & V that give different answers to the question K(x) > K(y).

Consequently, the universal prior is not absolute, but dependent on a
chosen U.

> > The dovetailing provides the simpler ensemble from which the specific
> > computation is selected. This is right there in the first
> > [Schmidhuber] paper.
> I don't see it.

Its right there on the second line of page 2 of his 1997 paper:
"Computing all universes. One way of sequentially computing all
computable universes is dove-tailing. A_1 ..."

So he does use the term dovetailer. He doesn't qualify it with
"universal", mind you I'm not entirely sure it isn't universal. Its
hard to read everything into one single line of prose. However, you
certainly have published on the UD prior to this.

> > In the second paper, the dovetailing is assumed to run on an actual
> > resource limited computer - hence the speed prior.
> But that dovetailing is not related to the universal one. Which is all
> normal given that Schmidhuber does not base his reasoning on the 1-3
> distinction. His ensemble or his "great programmer" is thus enough for
> his purpose.
> Bruno

He talks about the dovetailer on page 28 on that paper, and it is
running every possible program. He also notes that Li and Vitanyi
introduce such an algorithm (which they call SIMPLE) in Lemma 7.5.1 on
page 503.

How are these algorithms not "universal"?

*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
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to
For more options, visit this group at
Received on Thu Jun 22 2006 - 19:36:04 PDT

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