Re: Is the universe computable?

From: Hal Finney <hal.domain.name.hidden>
Date: Tue, 13 Jan 2004 14:30:26 -0800

Jesse Mazer wrote:
> Hal Finney wrote:
> >Suppose we sought to construct a consistent history of such a CA system
> >by first starting with purely random values at each point in space and
> >time. Now, obviously this arrangement will not satisfy the CA rules.
> >But then we go through and start modifying things locally so as to
> >satisfy the rules. We move around through the mesh in some pattern,
> >repeatedly making small modifications so as to provide local obedience
> >to the rules. Eventually, if we take enough time, we ought to reach a
> >point where the entire system satisfies the specified rules.
>
> Would this be guaranteed to work? You might get local regions of space and
> time that internally follow the rules but that are incompatible at their
> boundaries, like domains in a magnet. The algorithm would keep trying to
> modify things to make them globally consistent of course, but isn't it
> possible it'd get stuck in a loop?

Yes, you might have to do it carefully in order to avoid that. I think
that if you had a stochastic (random) element to the algorithm then it
would avoid loops. And you'd also have to be prepared to change your
boundary conditions so that you weren't trying to solve an impossible
state. (I think this part is implicit in Georges' idea of maximizing
some criterion rather than using fixed boundary conditions.)

Wolfram observationally divided CA universes (and more general
computational systems) into four categories: static, cyclic, random
and structured. Only the last class would allow for computation.
I suspect that those universes capable of computation would be among
the hardest ones to solve in this non-sequential way, that they would
have the most global dependencies. Universes which were restricted to
regular patterns would be easy. (Maybe the random ones would be hard,
too, since they tend to be chaotic.)

> >Now, I'm not sure how to combine this process with Georges' proposal to
> >maximize some criterion such as the gradient of orderliness. I suppose
> >you could simply repeat this process many times, saving or remembering
> >the best solution found so far.
>
> As long as everything that happens in the universe's history can be
> represented by a finite string, this brute-force method is one that's
> guaranteed to work...the ultimate version of this would just be to generate
> all possible strings of that length, then throw out all the ones that don't
> match the laws/boundary conditions you've chosen. This method could also be
> used to generate histories satisfying global constraints that could be hard
> to simulate in a sequential way, like a universe where backwards time travel
> is possible but history must be completely self-consistent, where it is
> possible to influence the past but not to change it.

Yes, that's a good idea, and it would probably be a shorter and simpler
program than my suggestion. I like your idea of time travel universes;
this is a mechanism for generating them that shows that they are not
logically impossible or contradictory. Several science fiction writers
have explored this concept, that time travel is possible and paradoxes
will not occur, no matter how unlikely are the events which conspire to
keep things consistent.

I'm not sure how to estimate the measure of time travel universes.
The program to generate them is not necessarily large, but there would
be many fewer consistent solutions to the equations than in universes
without time travel. So perhaps there would be fewer observers in
time travel universes compared even to ones that might have ad hoc
rules forbidding time travel. Such rules might make non time travel
universes' programs more complex and the universes of lower measure,
but this might be more than compensated for by the greater numbers of
observers in universes that forbid time travel.

Hal Finney
Received on Tue Jan 13 2004 - 17:32:49 PST