Re: Turing vs math

From: Juergen Schmidhuber <juergen.domain.name.hidden>
Date: Mon, 25 Oct 1999 10:14:34 +0200

You guys are too fast for me! Let me try to answer to earlier messages.

Hal:

> 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.
> You can try to say that this program doesn't count because it creates more
> than one universe,

Exactly.

> but as I suggested earlier this requires an objective
> formulation.

There is one. The info content of a computable object such as a
particular universe is the size of the shortest program that computes
it and nothing else.

> Which programs count and which ones don't?

Those that compute your universe AND NOTHING ELSE.

> 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.

No, everything is already in place. It's basic ingredients of Kolmogorov
complexity theory. Of course there are many UTMs whose output can be
interpreted as several different universes. E.g., the infinite computation
of Pi produces all beginnings of all universes as a side-product, because
every bitstring occurs somewhere in Pi's dyadic expansion. This doesn't
mean much though, because the interpreter that singles out any a single
universe (and represents it as, say, a movie) requires additional
information that may not be neglected. For example, the interpreter
may identify n bits of universe U somewhere in the output. But this will
cost additional bits beyond those in the original Pi-computing algorithm.

To avoid such issues, bitstrings are represented by themselves; we do
not have to worry about additional interpreter algorithms - they are
already implicit in the original list of all possible programs.

>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.

Sure, you can build a UTM with millions of states (as opposed to the 10
states or so necessary for the smallest UTMs) to encode flying rabbits.
Even on the flying rabbit machine, however, the shortest algorithms
of almost all possible universes will have almost the same size as the
corresponding algorithms on any other UTM. That's what the invariance
theorem is about: you can create a few exceptions to the rule, but you
cannot bend the rule.


Chris:

>....But my
>argument still stands that the UTM is a very specific (sequence-based) way
>of mapping from one n-tuple (ordered list) to another (m-tuple; m>>n), and
>so could not be considered to provide a reliable universal measure this
>way.)

The point is that each UTM can simulate any other device for describing
universes with constant costs independent of the size of the universes.

> 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).

But if you want to make predictions about the future of particular
universes that's not enough. Bayes' rule for making predictions requires
a prior on particular universes. "Prior" always means "prior for Bayes".
You have observed the past of a given universe, what's the probability
distribution on the possible futures?

P(past + future | past) =
P(past | past + future) * P(past + future) / P (past)

The first factor is 1. P(past) is a normalizing constant. The entire thing
is proportional to P(past + future). That's where you need the prior. The
universal prior prefers complete universes "past+future" whose shortest
algorithms are short. Since the shortest algorithm describing the past
of our own particular universe seems pretty short I can write in the 1997
paper: "...there will be less than maximal randomness in our future, and
more than vanishing predictability. We may hope that our universe will
remain regular, as opposed to drifting off into irregularity."

Note that the anthropic principle by itself is not enough to make such
predictions. There are many complex universes that start like ours and
then become very irregular. But U predicts ours won't. And every new
day brings a new confirmation.

All of this is essentially just the old theory of inductive inference
applied to the possible universes. I cannot really see major
conceptual problems here.


Juergen


Juergen Schmidhuber www.idsia.ch
Received on Mon Oct 25 1999 - 01:48:24 PDT

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