Life 2x2: long oscillator

53 views
Skip to first unread message

umg...@attglobal.net

unread,
Nov 2, 2001, 2:13:55 PM11/2/01
to
Hi,
I'm new to this list but I've been playing around with Life for a while
using Life32 and recently MCell. I've looked around various Life / CA
web pages to see if anybody else has discovered this and couldn't find
anything.

In exploring the 2x2 rule of Life, I came across this oscillator. It has
a period of 4194302 (verified with MCell 4.20) or 2^22-2. This
oscillator is not constructed with ships of any sort. There are some
other interesting (I think anyway) properties that are described in the
file included below.

I have a theory about this oscillator that would need proof and a
question about this oscillator (see file below for more info):

Theory: Solid (rectangular) blocks of cells form only at generations
2^N-2 where 1<=N<22 for the oscillation period.

Question: Why are 3 block combinations missing?

Eric Weddington

MCell file below:
#Life 1.05
#R 125/36
#D The large 4x94 block is an interesting oscillator:
#D 1. period 4194302 or 2^22-2
#D 2. solid blocks, such as the 4x94 block at generation 0, seem to only
form at generations
#D 2^N-2, where 1<= N < 22.
#D 3. The height and width values of the solid blocks are even numbers
that range from 2 to 96
#D and always sum to 98.
#D 4. There are 3 width / height combinations of solid blocks that are
missing: 84x14, 28x70, 56x42.
#D 5. If all the areas of the solid blocks are factored, all the primes
from 2 to 51 are present, except
#D for 7. The missing blocks above all contain 7 in the
factorization of their areas.
#D Eric B. Weddington, 2001.10.31
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****
****


Dean Hickerson

unread,
Nov 16, 2001, 1:19:39 PM11/16/01
to
Eric Weddington (umg...@attglobal.net) wrote:

> I'm new to this list but I've been playing around with Life for a while
> using Life32 and recently MCell. I've looked around various Life / CA
> web pages to see if anybody else has discovered this and couldn't find
> anything.

It's been known for several years at least, but I don't know of any
published descriptions of it.

> In exploring the 2x2 rule of Life,

That name is unclear, since there are many Moore-neighborhood, totalistic
rules in which patterns made of 2x2 blocks in gen 0 are made of 2x2 blocks
in every generation. The specific rule that you're using is B36/S125 in
standard notation; i.e. birth occurs if there are 3 or 6 neighbors,
survival if there are 1, 2, or 5. (But it works the same in all rules
between B3/S5 to B3678/S012567.)

> I came across this oscillator. It has
> a period of 4194302 (verified with MCell 4.20) or 2^22-2. This
> oscillator is not constructed with ships of any sort. There are some
> other interesting (I think anyway) properties that are described in the
> file included below.

In RLE notation your pattern is:

x = 4, y = 94, rule = B36/S125
4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
4o$4o!

This pattern emulates one in the 1-dimensional XOR CA, also known as Rule 90
in Wolfram's notation. In each phase, your pattern is an exclusive-or of a
bunch of concentric rectangles of size N x (98-N) for even numbers N.
Here are the first few phases:

gen 0: 94x4
gen 1: 96x2 + 92x6
gen 2: 90x8
gen 3: 92x6 + 88x10
gen 4: 94x4 + 86x12
gen 5: 96x2 + 92x6 + 88x10 + 84x14
gen 6: 82x16

Using a 1 to indicate the presence of a rectangle and a 0 to indicate its
absence, this becomes:

gen 0: 01000000000...000
gen 1: 10100000000...000
gen 2: 00010000000...000
gen 3: 00101000000...000
gen 4: 01000100000...000
gen 5: 10101010000...000
gen 6: 00000001000...000

Here the first position represents a 96x2 rectangle, the next represents
a 94x4 rectangle, and so on; the 48'th position represents a 2x96 rectangle.
Each 0 or 1 above is the XOR of its two immediate neighbors in the preceding
generation, except for the end cells, where we must imagine that there are
permanent 0's to the left of the leftmost cell and to the right of the
rightmost cell.

We can eliminate the inelegance of those permanent 0's by reflecting the
entire pattern about each of them, infinitely often:

gen 0: ... 0 000...00000000010 0 01000000000...000 0 000...00000000010 0 ...
gen 1: ... 0 000...00000000101 0 10100000000...000 0 000...00000000101 0 ...
gen 2: ... 0 000...00000001000 0 00010000000...000 0 000...00000001000 0 ...
gen 3: ... 0 000...00000010100 0 00101000000...000 0 000...00000010100 0 ...
gen 4: ... 0 000...00000100010 0 01000100000...000 0 000...00000100010 0 ...
gen 5: ... 0 000...00001010101 0 10101010000...000 0 000...00001010101 0 ...
gen 6: ... 0 000...00010000000 0 00000001000...000 0 000...00010000000 0 ...

Now we're dealing with an infinite, spatially periodic pattern in Rule 90.

This rule has been studied quite a bit, and can be understood by algebraic
techniques related to binary polynomials. See, for example, section 4 of
the article "Algebraic Properties of Cellular Automata" by Stephen Wolfram,
at:

www.stephenwolfram.com/publications/articles/ca/84-properties/index.html

> I have a theory about this oscillator that would need proof and a
> question about this oscillator (see file below for more info):
>
> Theory: Solid (rectangular) blocks of cells form only at generations
> 2^N-2 where 1<=N<22 for the oscillation period.

I'm sure this can be explained using the algebraic method, but I haven't
tried to work through the details.

Incidentally, rule 90 can be emulated more directly in the rule B7/S23457.
For example, the pattern below also has period 4194302; each cell in its
central row (except the ends) corresponds to one rectangle in your pattern:

.oooooooooooooooooooooooooooooooooooooooooooooooooo.
o..o...............................................o
.oooooooooooooooooooooooooooooooooooooooooooooooooo.

In RLE notation that's:

x = 52, y = 3, rule = B7/S23457
b50o$o2bo47bo$b50o!

Dean Hickerson
de...@math.ucdavis.edu

E. Weddington

unread,
Nov 19, 2001, 2:14:38 PM11/19/01
to de...@math.ucdavis.edu

Dean Hickerson wrote:

> Eric Weddington (umg...@attglobal.net) wrote:
>
> > I'm new to this list but I've been playing around with Life for a while
> > using Life32 and recently MCell. I've looked around various Life / CA
> > web pages to see if anybody else has discovered this and couldn't find
> > anything.
>
> It's been known for several years at least, but I don't know of any
> published descriptions of it.
>

Thanks for letting me know that it's already been known.


>
> > In exploring the 2x2 rule of Life,
>
> That name is unclear, since there are many Moore-neighborhood, totalistic
> rules in which patterns made of 2x2 blocks in gen 0 are made of 2x2 blocks
> in every generation. The specific rule that you're using is B36/S125 in
> standard notation; i.e. birth occurs if there are 3 or 6 neighbors,
> survival if there are 1, 2, or 5. (But it works the same in all rules
> between B3/S5 to B3678/S012567.)
>

The name "2x2 rule variant of Life" is what I've seen using the programs MCell
and Life32. I agree, that it's not a very descriptive or mnemonic name.


>
> > I came across this oscillator. It has
> > a period of 4194302 (verified with MCell 4.20) or 2^22-2. This
> > oscillator is not constructed with ships of any sort. There are some
> > other interesting (I think anyway) properties that are described in the
> > file included below.
>
> In RLE notation your pattern is:
>
> x = 4, y = 94, rule = B36/S125
> 4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
> 4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
> 4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
> 4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$4o$
> 4o$4o!
>

I should've put the rle notation in the message, as it's shorter. Instead I just
cut and pasted directly from MCell.

But now this is what I find odd.... If the theory holds that blocks *only* form
at generations 2^N-2 then there are 3 blocks missing in the (N x (98-N) for even
N) pattern.
The blocks missing are (width x height): 84x14, 28x70, and 56x42. It's
interesting to note that each of those dimensions are some multiple of 7.

The reasoning (accurate or not) behind listing the dimensions above in that
manner is that for all blocks that are formed at g 2^N-2, the width mod 4 = 0 and
the height mod 4 = 2. The above missing blocks would fit this pattern.

How does this mesh with what you described above about Wolfram rule 90?


>
> Incidentally, rule 90 can be emulated more directly in the rule B7/S23457.
> For example, the pattern below also has period 4194302; each cell in its
> central row (except the ends) corresponds to one rectangle in your pattern:
>
> .oooooooooooooooooooooooooooooooooooooooooooooooooo.
> o..o...............................................o
> .oooooooooooooooooooooooooooooooooooooooooooooooooo.
>
> In RLE notation that's:
>
> x = 52, y = 3, rule = B7/S23457
> b50o$o2bo47bo$b50o!
>

Thanks for the pattern!

Eric

Reply all
Reply to author
Forward
0 new messages