Re: Program for UD

From: Marchal <marchal.domain.name.hidden>
Date: Fri May 4 07:24:58 2001

Hal Finney wrote also:

>This leads to three questions:
>
> - Would all UD programs correspond to the universal measure,
>asymptotically?

Universal measure defined on what ? (Well this is an ongoing
important discussion ...)

I do think that, for constructive universal measure whatsoever,
you can build, by diagonalisation, pathological
UD such that they will make that universal mesure biased .
The mesure could depend on some "natural" universal dovetailer
loosing only against *initial* pathological UD.
Actually I am not quite sure about that.
The difficulty of this question is one of my motivation to ask the
machines from "inside" (despite that UDA forces us to take that
inside view and only that inside view into account. (This will
hopefully be clearer later ...)


> - Is there a way to retain state for all the programs so that you don't
>have to start over from the beginning? (Although Chaitin's way may
>be simpler, and if it gives the same probability distribution then we
>couldn't tell the difference).


The UD I send you in my preceding post (in this thread) does that.
Perhaps you have already noticed. It never do the same computation
twice. Precisely it never run two times the execution of the i-th
programs Pi (the UD memorises the needed continuations). Of course, it
computes infinitely often all programs, because for all i there is
necessarily a bigger j such that Pi and Pj computes the same
functions. But then this is necessary for all possible UDs.


> - Is it necessary to use self-delimiting programs in order for the
>notion of running all programs to be well defined, and recover the
>universal distribution?


I don't think so. Of course LISP programs are self-delimiting, so my UD is
not a counter-exemple.
If you are using non self-delimiting programs the UD will dovetail on each
runnable initial segments of the programs.
And you will probably recover the universal distribution,
if this one makes sense!
Perhaps you cannot compute in this way Chaitin's OMEGA because you cannot
know a priori if the UD execute a "correct non halting program" or just
some code which does not belong to a program (which cannot be extended in
a program code), so that I am not sure you can define when you must
add the 1/2^{-k} ...

Bruno
Received on Fri May 04 2001 - 07:24:58 PDT