Re: Permutation City

From: Matt Gingell (
Date: Sat Apr 22 2000 - 15:40:51 MDT

On Wed, 19 Apr 2000, you wrote:
>mjg223 <> writes:
>> On Wed, 19 Apr 2000, Anders Sandberg wrote:
>> > I have spent this weekend attempting to evolve causality in a
>> > cellular automaton (I wanted to find a 2D automaton rule that
>> > generated patterns corresponding to the space-time diagrams of a 1D
>> > automaton), and it was definitely tricky.
>> Interesting stuff. A rule like: 'fire if my right-hand neighbor is firing'
>> would generate leftwards trajectories. You could elaborate on that to get
>> traces to bounce off each other is you added a second class of firing
>> mode. Are you looking for something deeper than that - what's the target
>> you're trying to fit? Are you just doing thresholding on local neighbors
>> or are you using a more sophisticated class of 1D automation?
>The origin of the experiment is a cosmological idea I have been
>playing around with: the entire 4-D history of the universe is a
>stable state of a 4-D cellular automaton. If this hypothetical CA is
>started with a random state, then it will converge to an allowable
>history of the universe.

Why would the stability matter? Couldn't each time step of the 4-D
automata be a universe, or do you see some reason to require that
the world be persistent over a 5th dimension?

>My experiment was far simpler, I used a 2D automaton with binary
>states and the Moore neighborhood and a 2^9 bit rule denoting the
>result of every possible local state (this was the genes I ran the GA
>on). After running the automaton for a few steps, I calculated fitness
>from the final state. At first I tried to make the fitness function
>depend on how well the pattern fitted a predetermined 1-D rule, but
>right now I'm just contenting myself trying to get a causal evolution
>(i.e. a one-to-one mapping of states in the previous row to the
>next). So far I have not yet succeeded.

I'm not sure that - in general - GAs are appropriate for finding CAs
with particular stable states, though it's not something I've ever
tried. Intuitively it seems the mutating a transition rule either
won't make a difference to a particular stable configuration or it'll
change it completely. What you really want is small incremental
changes you can hill-climb over. Do you get that under the description
system you describe above?

>As I see it, the interesting question is if you can get the 2D
>automaton to evolve a consistent state from a random state. It would
>also incorporate the possibility of "synchronicity" and nonlocal
>interactions, as two separated patterns in the 1D world could have
>been affected by precursor states at early steps in the 2D world.

I'm not sure what you mean by consistent state. If initial conditions
are irrelevant then every terminal state is determined by the
transition rules, which puts an upper bound on what you can represent
of 2^9 terminal 'images.' Vastly fewer in practice - but I'm sure you
could map any stable state you want onto cellular rules given a
sufficiently powerful computational cell model.

The idea that non-locality is explainable in terms of CA is appealing,
but how does it differ from assuming some other kind of hidden state?


This archive was generated by hypermail 2b29 : Thu Jul 27 2000 - 14:09:43 MDT