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
