Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

113 views

Skip to first unread message

May 12, 2003, 7:59:50 PM5/12/03

to

The set of outer totalistic CA rules in the 4-neighbor von Neumann

neighborhood is rather poorer than that for the 8-neighbor Moore

neighborhood, both in terms of size (there are only 512 essentially

different rules) and of asymptotic behavior.

neighborhood is rather poorer than that for the 8-neighbor Moore

neighborhood, both in terms of size (there are only 512 essentially

different rules) and of asymptotic behavior.

Given that it's rather simple to prove that any 4-neighbor rule which

allows patterns of active cells to grow or move without bound must

result in any such pattern exploding quadratically, it seems difficult

to see how such rules could sustain gliders. In fact, they can't, not

unless one cheats a little.

The cheat is to consider rules which feature cell birth on 0 active

neighbors (and death on 4). In such rules, the background does not stay

inactive, but will alternate between inactive and active on successive

generations. If the rule is further chosen so that active cells can

(and must) expand on an inactive background but inactive cells can't do

so on an active background (or vice versa), then non-explosive growth

becomes possible.

There are further constraints which reduce the number of rules even

theoretically capable of supporting gliders down to just 32, and likely

even further. Of those rules, most still explode or don't grow at all.

Nonetheless, I've found at least two in which glider-like behavior is

possible and even emerges spontaneously.

In the 4-neighbor rule B024/S1 (that is, birth on 0, 2 or 4 active

neighbors, survival on 1) the following period 4 orthogonal c/2 glider

occasionally emerges (hash marks are active cells, periods inactive):

#..

#.#

Most starting patterns will explode in this rule, but the average growth

rate is not quite c/2, so gliders that form spontaneously can escape.

The rule also supports the following extended form of the glider:

..#..

#.#.#

The closely related rule B04/S1 is also interesting. It, too, typically

produces quadratic growth, but the growth rate is much lower. However,

if a pattern is allowed to grow, the following diagonal puffer will

often spontaneously emerge at its edge:

#.##.

..#..

.....

....#

This puffer moves much faster than patterns normally grow, so it will

rapidly escape its parent, leaving behind it a narrow, tapering "spike"

sticking out of the growing mass. It seems entirely possible that the

trail of this puffer could be stabilized, perhaps producing a diagonal

spaceship.

Ps. There is, of course, another way to extend the definition of a

glider in such a way as to potentially allow them in 4-neighbor rules.

That is to consider non-uniform backgrounds, i.e. ones consisting of

various stable (or even oscillating) periodic tilings of the grid. I've

yet to find any gliders on such backgrounds, although I find it likely

that they should exist.

--

Ilmari Karonen

Jun 1, 2003, 5:03:56 PM6/1/03

to

On Mon, 12 May 2003 23:59:50 GMT, Ilmari Karonen <il...@sci.invalid>

wrote:

wrote:

>The set of outer totalistic CA rules in the 4-neighbor von Neumann

>neighborhood is rather poorer than that for the 8-neighbor Moore

>neighborhood, both in terms of size (there are only 512 essentially

>different rules) and of asymptotic behavior.

>

>Given that it's rather simple to prove that any 4-neighbor rule which

>allows patterns of active cells to grow or move without bound must

>result in any such pattern exploding quadratically, it seems difficult

>to see how such rules could sustain gliders. In fact, they can't, not

>unless one cheats a little.

>

>The cheat is to consider rules which feature cell birth on 0 active

>neighbors (and death on 4). In such rules, the background does not stay

>inactive, but will alternate between inactive and active on successive

>generations. If the rule is further chosen so that active cells can

>(and must) expand on an inactive background but inactive cells can't do

>so on an active background (or vice versa), then non-explosive growth

>becomes possible.

Neat. I never thought I'd see gliders in a four cell universe. Your

cheat leads to flashy demonstrations, as the quick and dirty java

simulations I've thrown together and referenced below demonstrate.

>

>There are further constraints which reduce the number of rules even

>theoretically capable of supporting gliders down to just 32, and likely

>even further. Of those rules, most still explode or don't grow at all.

>Nonetheless, I've found at least two in which glider-like behavior is

>possible and even emerges spontaneously.

>

>In the 4-neighbor rule B024/S1 (that is, birth on 0, 2 or 4 active

>neighbors, survival on 1) the following period 4 orthogonal c/2 glider

>occasionally emerges (hash marks are active cells, periods inactive):

>

> #..

> #.#

>

>Most starting patterns will explode in this rule, but the average growth

>rate is not quite c/2, so gliders that form spontaneously can escape.

>The rule also supports the following extended form of the glider:

>

> ..#..

> #.#.#

>

>The closely related rule B04/S1 is also interesting. It, too, typically

>produces quadratic growth, but the growth rate is much lower. However,

>if a pattern is allowed to grow, the following diagonal puffer will

>often spontaneously emerge at its edge:

>

> #.##.

> ..#..

> .....

> ....#

>

This is really neat too! Unlike other puffers which I have seen, this

one apparently explodes into an irregular shape. Let it run long

enough in a large enough universe (1600x1250) and it looks like a

wierd mutant turnip waiting to be garbage collected:

www.collidoscope.com/modernca/b04s1turnip.html

>This puffer moves much faster than patterns normally grow, so it will

>rapidly escape its parent, leaving behind it a narrow, tapering "spike"

>sticking out of the growing mass. It seems entirely possible that the

>trail of this puffer could be stabilized, perhaps producing a diagonal

>spaceship.

>

Here's a smaller (800x500) simulation which usually demonstrates

puffer emergence:

www.collidoscope.com/modernca/b04s1escape.html

>Ps. There is, of course, another way to extend the definition of a

>glider in such a way as to potentially allow them in 4-neighbor rules.

>That is to consider non-uniform backgrounds, i.e. ones consisting of

>various stable (or even oscillating) periodic tilings of the grid. I've

>yet to find any gliders on such backgrounds, although I find it likely

>that they should exist.

George Maydwell

--

Modern Cellular Automata: www.collidoscope.com/modernca

Collidoscope Hexagonal Screensaver: www.collidoscope.com

Jun 2, 2003, 12:20:56 PM6/2/03

to

For those of you who may wish to see Ilmari Karonen's gliders and

puffer running under MCell, you can download a DLL and example

patterns from here:

puffer running under MCell, you can download a DLL and example

patterns from here:

http://linuxenvy.com/cgi-bin/bprentice/DirIndex?MCell/WG4.zip

Jun 2, 2003, 2:25:52 PM6/2/03

to

bpre...@webenet.net (Brian Prentice) wrote:

The link doesn't work. I've downloaded it from this link:

http://linuxenvy.com/bprentice/MCell/WG4.zip

But you don't need a new DLL, because you can use "General binary". This

is your P001.mcl example (survival: 1, birth: 0 and 4):

#MCell 4.20

#GAME General binary

#RULE C0,NN,Sabbab3ab7a,Bb14ab

#BOARD 200x200

#CCOLORS 2

#L A.AA$..A$$4.A

and this is your S001.mcl example (survival: 1, birth: 0, 2 and 4):

#MCell 4.20

#GAME General binary

#RULE C0,NN,Sabbab3ab7a,Bbaababbaabbabaab

#BOARD 200x200

#CCOLORS 2

#L A29.A$A.A25.A.A.A

But it's easier with your DLL to configure the totalistic rules.

--

Frank Buß, f...@frank-buss.de

http://www.frank-buss.de, http://www.it4-systems.de

0 new messages

Search

Clear search

Close search

Google apps

Main menu