Dear Bruno,

I have been guilty of responding a little too quickly to your posts :).

I want to just focus on the following exchange about the
Universal dovetailer, and put aside questions of ontology, measure,
induction, anthropic principle, etc.

On Sun, Oct 16, 2011 at 04:51:20PM +0200, Bruno Marchal wrote:
> >>>>>I know there are only a countable number of programs. Does
> >>>>>this entail
> >>>>>only a countable number of histories too? Or a continuum of
> >>>>>histories?
> >>>>>I did think the latter (and you seemed to agree), but I am
> >>>>>partially
> >>>>>influenced by the continuum of histories available in the "no
> >>>>>information" ensemble (aka "Nothing").
> >>>>
> >>>>It is a priori a continuum, due to the dovetailing on the infinite
> >>>>real input on programs by the UD.
> >>>>
> >>>
> >>>IIUC, the programs dovetailed by the UD do not take inputs.
> >>
> >>Why. By the SMN theorem, this would not be important, but to avoid
> >>its use I always describe the dovetailing as being done on one input
> >>programs.
> >>
> >>For all i, j, k
> >>compute the kth first steps of phi_i(j)        (and thus all
> >>programs dovetailed by the UD have an input (j))
> >>End
> >>
> >>The UD has no input, but the programs executed by the UD have
> >>one input.
> >>
> >
> >OK - but this is equivalent to dovetailing all zero input programs of
> >the form \psi_k() = \phi_i(j) where k is given by the Cantor pairing
> >function of (i,j).
> >
> >No matter, but there's still only a countable number of machines
> >being run.
> You need to use the SMN theorem on phi_u(<i,j>). But your conclusion
> is exact.
> Unless you take some no-comp notion of 'machines', machines are
> always countable. Their histories and their semantics, and
> epistemologies, are not.
> >
> >>
> >>>
> >>>I'm not sure what you mean by random inputs.
> >>
> >>The exact definition of random does not matter. They all work in
> >>this context. You can choose the algorithmic definition of Chaitin,
> >>or my own favorite definition where a random sequence is an
> >>arbitrary sequence. With this last definition, my favorite example
> >>of random sequence is the sequence 111111111.... (infinity of "1").
> >>The UD dovetails on all inputs, but the dovetailing is on the non
> >>random answers given by the programs on those possible arbitrary
> >>inputs.
> >
> >Sorry - I know what you mean by random - its the inputs part that was
> >confusing me (see above).
> By dovetailing on the reals, which is 3-equivalent with dovetailing
> on larger and larger arbitrary finite input, there is a sense to say
> that from their 1-views, the machines are confronted with the
> infinite bitstrings (a continuum), but only as input to some
> machine, unless our substitution level is infinitely low, like if we
> need to be conscious the exact real position of some particles, in
> which case our bodies would be part of the oracle (infinite
> bitstring). This gives a UD* model of NOT being a machine. Comp is
> consistent with us or different creature not being machine, a bit
> like PA is consistent with the provability of 0=1. (but not with 0=1
> itself. For the machine '0=1' is quite different from B'0=1').

Schmidhuber's description of the UD in his 1997 paper is clear. His
dovetailer runs all zero input programs. To be more precise, he
dovetails a universal machine on all finite strings (or equivalently
all strings with a finite number of '1' bits). In this state of
affairs, there can only ever be a countable number of universes.

In your Brussells thesis, on page 11 you describe the UD. You start of
by limiting your programs to no input programs ("sans entrees"). Then
you argue that the UD must also be dovetailing all 1 input programs,
n-input programs etc - by virtue of eg a LISP interpreter being
written in FORTRAN.

Fair enough, but whilst it is possible to convert a one input program
into a zero input program by concatenating the program and the input
(with the possible addition of a prefix the tells the UTM where the
program ends and the data starts), by dovetailing over all zero input
programs, one is not actually dovetailing over the reals. One cannot
say one is running all programs with random oracles - the "oracles"
can at best be simply the output of some zero input machine.

However, just recently, you introduced a new dovetailer, which does
dovetail over the reals. For program i when reading bit k of the
input, you split the program into two instances, and execute both
instances with the bit being '0' or '1'.

This, ISTM, is a completely different, and more wonderful beast, than
the UD described in your Brussells thesis, or Schmidhuber's '97
paper. This latter beast must truly give rise to a continuum of
histories, due to the random oracles you were talking about.

I am wondering if this is the heart of the disagreement you had with
Schmidhuber 10 years ago, about (amongst other things) the cardinality
of the histories.

My idea of the "no information" ensemble (aka Nothing in my book) was
very strongly influenced by that discussion you had with
Schmidhuber. Yet, until now, I would say I had the misconception of
the dovetailer running just the no input programs.

Lets leave the discussion of the universal prior to another post. In a
nutshell, though, no matter what prior distribution you put on the "no
information" ensemble, an observer of that ensemble will always see
the Solomonoff-Levin distribution, or universal prior.


Prof Russell Standish                  Phone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Professor of Mathematics
University of New South Wales

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

Reply via email to