Re: Turing vs math

From: Christopher Maloney <>
Date: Fri, 22 Oct 1999 23:17:05 -0400 wrote:
> Juergen Schmidhuber,, writes, quoting Hal:
> > > I do think that this argument has some problems, but it is appealing and
> > > if the holes can be filled it seems to offer an answer to the question.
> > > What do you think?
> >
> > Where exactly are the holes?
> One is what I mentioned earlier, that a trivial program which enumerates
> and executes (in dovetailing, interleaved form) all possible programs
> will create every mind in every possible situation. This is a very
> short program and hence is the most likely universe for us to live in.

I don't see this as a hole at all. Maybe I'm missing something, but I
thought the whole point of postulating a universal dovetailer was that
it creates "everything" from zero information (or as near as dammit).

This, combined with Bruno's computational indeterminism (thanks for
quoting your previous post Bruno -- I hadn't read that) provides the
basis for predictions of our future observations.

> You can try to say that this program doesn't count because it creates more
> than one universe, but as I suggested earlier this requires an objective
> formulation. Which programs count and which ones don't? How can we
> know whether a program creates a single universe or more than one?
> We need something more in the theory to solve this problem.

I would be inclined to reject any theory that threw ad hoc rationalizations
for rejecting some universes and accepting others. The whole appeal of
"everything exists" is its zero information.

> Another problem is that the Kolmogorov measure is defined only up to
> an additive constant. Given a specific, large, program which runs on
> universal TM "T", we can construct a different UTM T' on which that
> program is very small. (In essence we hard-wire the program into the
> T' definition.) This means that I can create a UTM where a magical
> flying-rabbit universe is more probable than the one we live in.

I agree that this is a hole, and it has bothered me (sort of in the
back of my mind) for some time. In Juergen's paper, he says

    Under different universal priors (based on different universal
    machines), probabilities of a given string differ by no more
    than a constant factor independent of the string size, due to the
    compiler theorem (the constant factor corresponds to the
    probability of guessing a compiler). This justifies the name
    ``universal prior,'' also known as Solomonoff-Levin distribution.

I don't know what this means exactly. It worries me that the
probabilities are not completely well defined. It seems to me that
Hal is correct that certain UTM's can be contrived to make certain
bit strings very likely.

We could borrow the section from Tegmark's paper on making
predicitions, and apply it to this discussion.
I'll assume Bruno's computational indeterminism, and restrict the
discussion to just two consecutive time steps in the computation.
We want to predict the probability of our seeing Y at time t1,
given that we now see X at time t0. As Bruno often points out, we
have no way of knowing exactly who we are or what bit strings we
are represented by, but we do know that at time t0, we see X.

Let Si be a bit string within a single time snapshot of a universe
history. Let's also assume that it's possible, in principle, to
evaluate Si to see if it qualifies as an observer, and if it observes
X or Y.


  P(Y,t1|X,t0) =
    Sum j { Sum i { P(Y|Sj) P(Sj,t1|Si,t0) P(X|Si) } }

In words, the probability that I'll see Y at t1, given that I see X
at t0, equals the sum of all probabilities that Sj sees Y, that Sj is
a computational continuation of Si, and that Si sees X.

Now, being able to determine what a "bit string observes" depends,
of course, on the TM. The TM "breathes life" into the bit strings.
Also, the determination of the middle term depends on the TM.
I'm just thinking out loud, here, really, but it seems to me that
even a "constant" factor will throw this equation out of whack. We
should be able to show that this probability is independent of the

> A related problem is the uncomputability of the Kolmogorov measure.
> There is no way in general to know what is the shortest program to
> construct a given string or a given universe. Yet probabilities are
> real and so apparently someone/something is in effect computing them.
> In other words, our observations of probability imply that uncomputable
> values are being computed. This is at least a bit paradoxical.

I don't see this as a problem, on the other hand. Just because
probabilities exist doesn't mean that anyone or anything is computing

> Hal

Chris Maloney
"Donuts are so sweet and tasty."
-- Homer Simpson
Received on Fri Oct 22 1999 - 20:27:01 PDT

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