Re: Turing vs math

From: Russell Standish <>
Date: Mon, 25 Oct 1999 10:30:40 +1000 (EST)

> 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 must admit I had hoped that the "scale factor" issue had been taken
into account. I had hoped to chase this up when I got a chance to
borrow Li and Vitanyi from the library (requiring the conjunction of
the book actually being returned to the shelf, and me taking some
holidays). However, my naive approach to the problem is to assert that
every UTM can be specified as a program in a "most basic" UTM, which
is in itself is simply a transition table in the most basic
architecture. These bits of information can be prepended to the
bitstring of interest. The most basic architecture to me seems to be a
device that has one internal state (a bit), and takes one bit of
input, then writes one bit of output, possibly changing the internal
state. Thus the transition table is a 4x4 table. Maybe this scheme is
too basic. I leave it up to you computer scientists to refine or
refute this notion.

> 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.
> Then,
> 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
> TM.
> > 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
> them.
> >
> > Hal
> --
> Chris Maloney
> "Donuts are so sweet and tasty."
> -- Homer Simpson

Dr. Russell Standish Director
High Performance Computing Support Unit,
University of NSW Phone 9385 6967
Sydney 2052 Fax 9385 6965
Room 2075, Red Centre
Received on Sun Oct 24 1999 - 17:28:38 PDT

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