Wanted: 2D CA, "as complex" but "denser" than Life
John Ladasky
I've been playing around with Conway's Life and other cellular
automata, using Mirek's Cellebration program.
http://psoup.math.wisc.edu/mcell/mjcell/mjcell.html
Life is well-studied, it has gliders and oscillators, and space-
fillers, it's Turing-complete -- it's known that you can do
interesting things with it. However, it's a rather sparse CA. On a
Life grid, most of the cells are empty. I'm seeing an equilibrium
density of around 3.5% populated cells. Because things are so spread
out, it's hard to watch the activities of a complex structure.
Cellebration implements many alternative 2D CA rules, many of which
have the "chaotic" rule character and thus are potential replacements
for Life. Some rules produce denser patterns than Life and thus are
more "watchable." I find densities of around 10% live cells to be
appealing. Weighted CA and generational CA extend the range of
possibilities.
What I would like to know is which of these alternative rules are, in
fact, adequate substitutes for Life. What criteria must a CA meet in
order to be computationally interesting? Is there a shorter way to
answer that question than to undertake a search for, or a proof of the
existence of, a Turing machine using that rule set?
Thanks for your suggestions!
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| Ladasky Home Solar, Inc.: blowing sunshine up your |
| power grid since March 24, 2005. Fiat lux! |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| Uptime Downtime kWh generated kWh consumed |
| 772.5 days 13 hours 13485 14875 |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
Dave Greene
> which have the "chaotic" rule character and thus are potential
> replacements for Life. Some rules produce denser patterns
> than Life and thus are more "watchable." I find densities of
> around 10% live cells to be appealing. Weighted CA and
> generational CA extend the range of possibilities.
That's an interestingly offbeat angle of approach... I can't
immediately come up with anything very near to your 10% target, at
least for CA rules that I know to be "interesting". Have you looked
at Day & Night -- B3678/S34678? There are some good pattern links in
the Wikipedia article:
http://en.wikipedia.org/wiki/Day_%26_Night
-- or MCell has a pretty good subset of David Bell's and other
people's patterns.
To try another angle, at the bottom of http://entropymine.com/jason/life/alt/
there's a list of rules with known guns, which is a fairly good rough
measure for interestingness.
There seems to be something of a gap between rules that tend to die
out or stabilize over time -- which tend to settle into densities
lower than 10% -- versus rules where an initial seed pattern usually
grows indefinitely, where the density tends to end up a lot higher.
However, if you pick your Conway's Life patterns carefully you'll
often see densities around 10% -- for example, many of the lower-
period glider guns in Jason Summers' collection are about that dense.
Once you isolate reactions with signal-processing capability and
deliberately arrange them, you may see very different densities than
you'll ever run across in experiments with random starting states.
I've seen 2.8% as an average figure for Life patterns that have
"burned out" into random ash, so your 3.5% figure must be patterns
that are well on their way there. But by definition burned-out
patterns won't be particularly interesting to watch. The trick in
Life is to avoid burnout...
There was a previous posting here about mean field analysis, which
might possibly be useful in deciding which rules will naturally settle
into an average 10%-ON state. Might be simpler just to run random
fields in various rules and see what happens, though (!):
http://groups.google.com/group/comp.theory.cell-automata/browse_thread/thread/93afbe463f6b4ef8
-- I'm not sure this kind of statistical approach will tell you much
about the emergent behavior of a rule, which can have big implications
for its information-processing ability. In Conway's Life, for
example, a surprising number of small patterns serendipitously create
R-pentominos and/or B-heptominos, which are "tamable" and happen to
travel very well; this is what allows Herschel circuitry to be built.
Some Herschel tracks do look a lot like random ash, come to think of
it, but the ones supported by oscillators and custom welded eaters are
a lot denser.
So what you get out of Life depends on what you put into it; I take it
you're mostly interested in experiments with random starting states?
Keep the cheer,
Dave Greene
Dave Greene
> are, in fact, adequate substitutes for Life. What criteria
> must a CA meet in order to be computationally interesting?
Ouch, that's a tough one... mostly because the detailed reactions that
make most rules computationally interesting haven't been discovered
yet. But here are a few random thoughts, which (fair warning) I can
explain at length if someone asks about them --
John Conway picked B3/S23 Life after looking at a large field of
similar rules; his choice got into Martin Gardner's _Scientific
American_ column and triggered a worldwide research spree on that
particular rule that has lasted thirty-seven years and counting. But
if you pick another promising Life-like rule and "live with it" for a
long time, as per Conway's suggestion -- invest a similar amount of
research in it -- the odds are fairly good that you can figure out
some way to make it computationally interesting, too.
However, the result may look nothing like what you expect. It may be
necessary to build stable or oscillating "wires" or "tracks" to carry
information, for example. Even in Life, signals and transmission
speeds vary widely according to the medium they're travelling in: you
can't get a signal across empty space faster than half a cell per
second, but you can send information at 2/3 cells per second
diagonally or even one cell per second orthogonally through a re-
usable wire. There are also patterns with arbitrarily large empty
spaces at their centers, that can swim at lightspeed or 2/3 lightspeed
orthogonally through a striped "agar" of half ON and half OFF cells:
http://pentadecathlon.com/lifenews/2006/05/2c3_perpendicular_signals_thro.html
It's almost as if these "anti-spaceships" belong to a different
universe altogether; I suppose an empty CA universe could be designed
that these creatures could be transplanted into, where alternate
strips of cells follow different rules. This is getting a little far
afield -- but the point is just that it's very easy for a rule to be
computationally interesting in weird and unexpected ways, as when
someone figures out how to seed the universe with a background pattern
that makes it simulate a completely different rule.
> Is there a shorter way to answer that question than to
> undertake a search for, or a proof of the existence of,
> a Turing machine using that rule set?
Well, not that I know of. Langton's lambda parameter can apparently
be a useful rule of thumb, but it may miss a lot of good stuff. Along
similar lines, here's David Eppstein's critique of Wolfram's four
classes of CA rules:
http://www.ics.uci.edu/~eppstein/ca/wolfram.html
You could definitely get a good sense of relative probabilities,
though, just by seeing how easy it is to find various features that
would be useful in computation. Here are some of the useful features
of Conway's Life that one could hunt for elsewhere:
1) Stable structures and small oscillators are plentiful, and both can
come in contact with active reactions and can modify them without
being permanently harmed. This allows the creation of reusable
circuitry.
2) There are several small moving objects available -- gliders,
lightweight, middleweight, and heavyweight spaceships, and (arguably)
r-pentominoes/b-heptominoes/Herschels -- each of which can be
constructed using objects of each of the other types. This allows for
an unusual amount of flexibility in getting information from one place
to another.
3) The average random Life pattern settles down instead of exploding
(if you ignore output gliders and spaceships). There are exceptional
quadratic-growth cases, mostly involving switch engines, but most
random patterns affect only their immediate area. Thus when you're
looking for useful reactions, there's a very, very large search space
to play around in. By contrast, consider a rule like Seeds (B2/S)
that has "gliders" and oscillators and so forth, so theoretically it
might support universal computation somehow. But random interactions
between its "gliders" generally result in nearly-unstoppable supernova
explosions -- so the search space in which one might find
conventional* signal-processing reactions is much, much smaller than
in Life.
4) The average random Life pattern stays active for a good number of
generations before it settles down -- Langton's lambda parameter is
near the "sweet spot". The longer the settling process takes, the
more opportunities there are to widen the search space by modifying
reactions in midstream. Actually long-lived activity in one place
isn't so useful -- e.g., it's hard to figure out how to do information
processing in LongLife [B345/S5] -- but I don't think there's a
parameter like Langton's that measures an active pattern's tendency to
move into new areas.
5) It was proven, very early on, that all the stable structures and
oscillators that you need to build a self-replicating pattern in Life
can be created by bashing gliders together. By now it's pretty clear
that a Life universal constructor doesn't even need any oscillators:
a constructor could be built with just five types of still lifes (plus
an input glider). I don't think a similar claim can be made for any
other simple CA rule -- yet. But most likely that's just because the
research that's been done is so heavily skewed toward B3/S23, not
because Conway's Life is somehow uniquely suited for this kind of
thing.
Keep the cheer,
Dave Greene
* It's always possible that someone will figure out how to model
universal computation in the heart of one of those Seeds supernovas,
or on its expanding perimeter. But I'll believe that kind of wild
hand-waving speculation when someone shows me a working example...!
Ilmari Karonen
>
> What I would like to know is which of these alternative rules are, in
> fact, adequate substitutes for Life. What criteria must a CA meet in
> order to be computationally interesting? Is there a shorter way to
> answer that question than to undertake a search for, or a proof of the
> existence of, a Turing machine using that rule set?
Well, you don't need to actually construct a Turing machine, all you
need to do is find all the parts that would be necessary to build one.
Of course, doing that rigorously essentially amounts to an existence
proof, but for less rigorous purposes, just finding a set of patterns
that lets you construct nontrivial logic operations is probably enough
to let you wave your hands and state that the rule has a good chance
of being Turing-complete.
Even less rigorously, just finding, say, nontrivially interacting
gliders -- or even just any gliders at all -- is probably enough to
mark a rule as "interesting", for some values thereof. Note that,
while gliders are the usual way of implementing logic in Conway's Life
and related rules, they are by no means the only possible one.
Also note that the _existence_ of computationally useful patterns in a
given rule doesn't necessarily have much to do with the odds of their
spontaneous emergence. In Life, simple nontrivially interacting
gliders do appear frequently from chaos, hinting at the possibility of
computation, but most of the more complex patterns used for logic
contructions have a vanishing probability of emerging spontaneously.
Conversely, the Seeds rule (B2/S-) does feature gliders, which (IIRC)
can even be made to interact in a controlled manner to some extent,
even though most starting configurations and interactions explode into
chaos. Meanwhile, the closely related 3-state rule Brian's Brain has
gliders galore, with the main difficulty being the construction of
patterns that _don't_ glide away. Indeed, even rules where almost all
patterns vanish entirely can support computation, as long as there are
enough building blocks among the few that don't.
And, of course, the final caveat is that there can, in fact, be quite
a few definitions of "interesting" that _don't_ equate to Turing
completeness. Feel free to pick yours as you like.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
John Ladasky
I am familiar with pentadecathlon.com. I know about the propagation
of alternative gliders through substrates consisting of something
other than 100% dead cells. It's true that there are ways to effect
an apparent change to the rules of Life with a suitable substrate.
It's a somewhat artificial situation. Still, I should go back and see
whether components which exist in non-zero substrates are denser than
those in regular Life.
Following up on Day and Night was fruitful. To my eye, it is easier
to follow the workings of Day and Night than Life. After watching Day
and Night for a while, I realized that D&N's greater density was not
the only thing making it easier for me to follow the action -- the
fact that even the smallest gliders were objects comparable in size to
objects that operated on them was also helpful. In Life, gliders are
usually tiny, and other objects are typically much larger.
Plus, D&N's property of invertibility is really cool!
Previously, I did spend some time looking at Diamoeba. Yes, it's
"dense," which is what I asked for. But it's difficult to watch
nonetheless, and for a different reason. Computation, if it's even
occurring, appears only on the transient fringes of the amoeboid
shapes. It's as if each amoeba has a 1D automaton wrapped around its
edge.
Langton's lambda parameter is new to me. Wolfram's CA classification
scheme clearly was not new to me, but David Eppstein's critique was,
as was his summary of what conditions must be met in order for gliders
to form.
Thanks for all the new leads!
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| Ladasky Home Solar, Inc.: blowing sunshine up your |
| power grid since March 24, 2005. Fiat lux! |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| Uptime Downtime kWh generated kWh consumed |
| 778.5 days 13 hours 13636 14992 |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
Dave Greene
> Following up on Day and Night was fruitful. To my eye, it is easier
> to follow the workings of Day and Night than Life. After watching Day
> and Night for a while, I realized that D&N's greater density was not
> the only thing making it easier for me to follow the action -- the
> fact that even the smallest gliders were objects comparable in size to
> objects that operated on them was also helpful. In Life, gliders are
> usually tiny, and other objects are typically much larger.
Good -- I thought Day & Night might be a good match. Mind you, I'm
still a little puzzled by the characterization of Conway's Life as
having "operators" much larger than what they're operating on. Here
again I suppose it depends a lot on what types of patterns you're
looking at.
Many, many more large patterns have been constructed in B3/S23 than in
any other rule, and the individual gliders certainly do fade into the
background in the bigger patterns. For example, Brice Due's latest
creation along "metapixel" lines (for Golly 1.2) is a huge two-digit
hexadecimal counter where only large-scale behavior is visible at all,
unless you zoom way in:
http://b3s23life.blogspot.com/2007/04/hex-counter-and-cells-within-cells.html
But the various p46 oscillators that make up the low-level circuitry
seem only a few steps up in size from the signals they're processing.
It's just that once you've strung enough circuitry together, when
you're looking at the big picture you just have to trust that the
gliders and spaceships and so on are still down there, doing their job
at the molecular level.
Golly 1.2 also has some support for multiple tiled views of one
universe now; it's nice being able to zoom in on one tile while
keeping an overview visible in another tile.
Herschels, R's and B's (oh, my!)
-----------------------------------------------
I've been trying for years now, off and on, to drum up more interest
in the awkward but fascinating field of Herschel-track engineering in
Conway's Life, where the "signal" objects -- mostly Herschels, R-
pentominoes, and B-heptominoes -- are larger on average than the
catalysts operating on them. Not much success so far, I must say; I
think you can probably still count on your fingers all the card-
carrying members of Herschel Engineers of the World (or maybe it
should be "Herschel Plumbers Anonymous"...)
Here's a sample Herschel-track pattern that I finally got around to
finishing recently:
http://b3s23life.blogspot.com/2007/06/new-kind-of-signal-though-not-useful.html
This is a working draft of a Herschel-to-switch-engine signal
converter made out of stable pieces. Signals can follow each other
after a minimum of 629 ticks.
Previous efforts along these lines used p30 oscillators, which allowed
the reaction to be repeated more quickly but put constraints on the
timing. The stable switch-engine track comes from David Bell's
"swimmer" oscillator --
http://pentadecathlon.com/lifeNews/2005/09/bobsled_run_update.html
-- but that was really two independent signals running in opposite
directions on the same track, created and destroyed by separate high-
period shotguns.