Natural spaceships beyond the glider and *WSS's ?

For general discussion about Conway's Game of Life.
User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: Natural spaceships beyond the glider and *WSS's ?

Post by DivusIulius » June 21st, 2009, 5:32 am

The links at
Life's Still Lifes http://delta.cs.cinvestav.mx/~mcintosh/ ... still.html
and
A Zoo of Life Forms http://delta.cs.cinvestav.mx/~mcintosh/ ... tzool.html
point to the same PDF document: http://delta.cs.cinvestav.mx/~mcintosh/ ... ol/zoo.pdf

Fortunately, the HTML version is different... :D

Interesting documents, even for brute force search lovers like me.

MadMan
Posts: 21
Joined: June 14th, 2009, 11:40 am

Re: Natural spaceships beyond the glider and *WSS's ?

Post by MadMan » June 21st, 2009, 8:46 am

I am also quite amazed & astounded at the terrible Greyships researched by Holwart Hazmat, which are traveling agars !! :o I was able to graph the smallest one, but the others are 6-10 feet long and suggest cockroaches or centipedes in shape. The agar may be horizontal, vertical or chicken wire type. One looks like a copepod and another like a Christmas tree. Names I suggest include: Christmas Tree, copepod (sowbug), inflexible flyer, squatty, Awry, Diamond in the rough,Girdle ... You may view all these in the Life News of which this forum is a link. (Some oscillator patterns can not be seen under all the rubbish in the pic). :(

I find that the larger the pattern, the more likely intractible graphing & plotting probs will give me grief. Patterns can get fouled (can't be repaired, errors out of control...) especially if the graph paper has very small resolution. I work best at 10 squares/inch. You spoke to me earlier,'bout printing my own graph paper: I attempted that, BUT the grid was so stretched horizontally that I just gave up. I do not know how to deal with that.

I don't have these AI search programs for oscillators, spaceships, etc., and must rely on my own personal research (ended c.2000 due to the permanent shutdown of my trusty APPLE ][, Mr. Turner's doing the skip, and increasing problems managing growing archives) & finding pub. archived findings. I also had limited input facilities. My self-esteem was also not helped by life websites minimizing & rejecting the very things I worked so hard on (they were NOT interested in diehards, long-term ancestors, all-glider censuses....) :cry:

These greyship monstrosities just do NOT appear naturally. I never even found the 6-bit Clock in all my estimated 10-20,000 patterns. I did find a few bizarre still-lifes, but NO new oscillators or the like (except the P30 shuttle-driven Repulsar oscillators of which the variety is endless (they do NOT occur naturally and had to be laboriously designed and built.). I wonder if there's a parallel between this & the random banging & thumping of random elements & molecules in the dawn of earth producing the complex systems of organic life.

User avatar
PM 2Ring
Posts: 152
Joined: March 26th, 2009, 11:18 am

Re: Natural spaceships beyond the glider and *WSS's ?

Post by PM 2Ring » June 22nd, 2009, 8:57 am

MadMan wrote:I find that the larger the pattern, the more likely intractible graphing & plotting probs will give me grief. Patterns can get fouled (can't be repaired, errors out of control...) especially if the graph paper has very small resolution. I work best at 10 squares/inch. You spoke to me earlier,'bout printing my own graph paper: I attempted that, BUT the grid was so stretched horizontally that I just gave up. I do not know how to deal with that.
Do you have this stretching problem when printing other images or PDF files? If so, it sounds like there's something wrong with your printer settings. But if you're interested, I can create a PDF of 10 squares/inch on the paper size of your choice.

But I'm intrigued at why you feel the need to use graph paper. Computers are so much more convenient.

BTW, I had a look at your diehard pattern, but it didn't die. Maybe it got corrupted in the copying & pasting.

MadMan
Posts: 21
Joined: June 14th, 2009, 11:40 am

Re: Natural spaceships beyond the glider and *WSS's ?

Post by MadMan » June 22nd, 2009, 6:21 pm

OK, PM 2Ring, here's the skinny on both...

(1) I use graph paper, to create a personal record of my discoveries. Whenever I discovered a wonderful pattern , back in last century, I would carefully re-input it and make certain of how it's going to grow before reaching its final fate (and to confirm my notes: a few patterns were lost and could NOT be recovered...). Then I would take marker pen and draw each stage in a gen. by gen. record. Junk parts (destined to die without affecting any other part of the pattern) that spin off got jotted down in red while parts destined to survive got indited to paper in either black or blue or maybe green ! It was a personal human touch that no computer program could do ! I used a feltmarker that did not do instant bleedthru like Sharps does. I can no longer find it. I can no longer find the right graph paper, either. It's Turner: the clunk did the skip c.2000. At the time, I felt little 'bout it as I had tired of all the graphing. Now that I had spent 3 years fixing my archives (only 2 GREAT patterns were lost and they are in the Master Index which had been stuck on a higher shelf one night some time BEFORE that flood !).

(2) Now as the Diehard. Mayhaps you had trouble with the diagram. Here it is again...

OOOOOOOOOO
0X00000000000
0XXX0XX000000
000000XX00000
00X0000000000
0000000000000

Thye X's are on cells.'s
Last edited by MadMan on June 22nd, 2009, 7:33 pm, edited 1 time in total.

MadMan
Posts: 21
Joined: June 14th, 2009, 11:40 am

Re: Natural spaceships beyond the glider and *WSS's ?

Post by MadMan » June 22nd, 2009, 6:26 pm

.............
.o...........
.ooo.oo....
........oo..
..o.........
............

Mebbe you had probs reading the 0's and X's, so I used lower case...

It'll grow to 40 units tall, but by then it's decaying downwards and will become compact again.

User avatar
Andrew
Moderator
Posts: 911
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Natural spaceships beyond the glider and *WSS's ?

Post by Andrew » June 22nd, 2009, 7:52 pm

MadMan's last pattern has 2 too many dots in the 4th line. Here is the correct pattern in rle format:

Code: Select all

x = 7, y = 4, rule = B3/S23
o$3ob2o$5b2o$bo!
Quite an interesting diehard. MadMan, throw away your graph paper and start using Golly!
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Natural spaceships beyond the glider and *WSS's ?

Post by Elithrion » June 22nd, 2009, 8:04 pm

Andrew wrote:MadMan's last pattern has 2 too many dots in the 4th line.
I think he meant to indicate the relative position, but the variable-width font messed it up, making him add two dots for clarity. It would have been more easily done with the Code tags, by the way, like so:

Code: Select all

[code]
............
.o..........
.ooo.oo.....
......oo....
..o.........
............
[/code]
Alternatively, Nath's site makes for convenient linking once you save patterns, e.g. http://www.conwaylife.com/?p=madmansdiehard
Vi veri veniversum vivus vici.

MadMan
Posts: 21
Joined: June 14th, 2009, 11:40 am

Re: Natural spaceships beyond the glider and *WSS's ?

Post by MadMan » June 22nd, 2009, 10:15 pm

I wish to thank you, for calling my attention to that P6Diagonal Spaceship that glide-reflects.

By the way, ANDREW, Kok's Galaxy is one of my favorite oscillators -tho it does NOT occur naturally. It has no stagnant inductors, braces, etc.,...

It also proved effective as a hassler or perturber (catalytic inductor of stable matter into an active form that eventually turns back into the old still-lifes.)
in a P24 oscillator. The perturbed or hassled core takes 20 gen., to settle after being riled up, and then the 2 Kok's Galaxies attack shortly...

I apologize if I got this forum off-track, tho.

I use graph paper as a PERMANENT record of all my research triumphs as artistic work , once my old APPLE ][ went to work, using a program I co-authored !(wrote graphics conversion, added pack & load, wrote an attract mode,demos,etc.)

I call my baby the Diehard Supreme !

User avatar
PM 2Ring
Posts: 152
Joined: March 26th, 2009, 11:18 am

Re: Natural spaceships beyond the glider and *WSS's ?

Post by PM 2Ring » June 28th, 2009, 10:25 am

I have done some simple Life patterns on graph paper, but that was many years ago, when I didn't have much access to computers.

Here's a simple 10 square / inch graph paper in PostScript. I tried to attach the PDF version, but the forum doesn't like PDFs. I haven't tested it on a printer yet; we use metric paper here in Australia, so I couldn't really test it properly anyway. If you use Linux, the PostScript file should present no problems. Otherwise, you may need to install ghostscript or some other PostScript interpreter. Or maybe I can just store the PDF in an archive.

Code: Select all

%!PS-Adobe-3.0
%%BoundingBox: 0 0 612 792
%%Title: (Traditional squared graph paper: GraphPaper0.ps)
%%Creator: (PM 2Ring)
%%Creationdate: (19:43:00 Apr  9 1999)
%%EndComments

16 dict begin

%Page size: US letter
/XM 612 def
/YM 792 def

%One inch in PostScript points
/inch {72 mul}bind def        

%Bottom left margin 
/MARGIN .25 inch def

% Grid increments
/dBig 1 inch def
/dSmall .1 inch def

% Grid colour in HSB form
/Colour {.5 1 1 } bind def  %Cyan
/Colour {0 0 0.5 } bind def  %Gray

% ------------------------------------------------------------

%Grid size 
/XLO MARGIN def
/YLO MARGIN def

/XR 8 inch def
/YR 10 inch def

/XHI XLO XR add def
/YHI YLO YR add def

% ------------------------------------------------------------

gsave
    Colour sethsbcolor
    
    %Minor gridlines
    .1 setlinewidth
    %Uncomment one of the lines below to use dashed lines for the small squares
    %[2 2] 0 setdash
    [1 1] 0 setdash
    
    YLO dSmall YHI
    {
        XLO exch moveto
        XR 0 rlineto stroke
    } for
    
    XLO dSmall XHI
    {
        YLO moveto
        0 YR rlineto stroke
    } for
    
    %Major gridlines
    .25 setlinewidth
    [] 0 setdash
    
    YLO dBig YHI
    {
        XLO exch moveto
        XR 0 rlineto stroke
    } for
    
    XLO dBig XHI
    {
        YLO moveto
        0 YR rlineto stroke
    } for    
grestore
showpage

end
%%EOF
I'm thinking it might be a nice idea to write a program that reads Life patterns (probably in RLE format) & prints them nicely using PostScript. If anyone wants to encourage me in this endeavour, feel free. :)

H. V. McIntosh
Posts: 49
Joined: June 20th, 2009, 5:26 pm
Location: Mexico

Re: Natural spaceships beyond the glider and *WSS's ?

Post by H. V. McIntosh » July 10th, 2009, 12:20 am

DivusIulius wrote:The links at ..... and ..... point to the same PDF document: Fortunately, the HTML version is different ...
That is true, although the error is not so easy to fix. It manifests when the documents are reached through the abstracts; the other entry points work as they should.
Interesting documents, even for brute force search lovers like me.
Looking over these articles after so many years, I wonder whether some commentary and further explanation might not be worthwhile. There are many search strategies, amongst which constructing de Bruijn diagrams can give exhaustive answers, although in a rather limited domain. A relative disadvantage is the huge size of the diagrams, although compared to what Google has done with the Internet database, it is nothing. Since a two-dimensional diagram is unknown, the first step in the process is to find a suitable one-dimensional diagram, done by taking neighborhoods along a single stripe. That gets enough overlap between 2x3 blocks to get consecutive 3x3 neighborhoods along with their central cells. It might be interesting to try diagonal stripes or maybe other curves, but that is speculative. The process is similar to forming what Wainwright called ripples, where identical cells run along parallel lines projecting the automaton onto one dimension. For Conway's Life, that yields Wolfram's Rule 22, which is quite complicated although not of Class IV, and itself much studied.

The de Bruijn scheme does not involve projection; rather the first stage creates a linear automaton with first neighbors and eight states. There are 8^3 = 512 neighborhoods, 8^2 = 64 semineighborhoods, and 8^512 evolutionary choices. Although the scheme applies equally well to any "Life" rule with a Moore neighborhood, we are only interested in Conway's Life and a few variants. So we only need to think of a de Bruijn diagram with 64 nodes each having 8 links. Cumbersome as it may be, it already yields interesting information. Having labelled the links, paths through the diagram define sequences of labels and conversely. Since labels can convey information about the neighborhood and/or its evolution, paths can compare this information. For example, the Boolean label "the evolved cell is the same as the central cell" will describe still life within the stripe. Similarly a uniform shift would be revealed by always comparing the central cell to one of the other cells in the neighborhood. Many other predicates are possible: evolution to constancy, complementation, comparisons involving several cells one of which is central and so on.

Given that the de Bruijn diagram, labels and all, is finite paths must necessarily return to a previous vertex. That vertex is not necessarily the starting vertex; moreover if only paths bearing specified labels, there may be no vertex with such a label entering, leaving or both. Subsets may have a similar variety of mutual links. Graph theory has a whole vocabulary and lore describing all this detail. So examination of the de Bruijn diagram may reveal that there are no paths of the desired type, and the conjectured evolution is impossible without ever having to search two dimensions. Given the repetition inherent in long paths, any type of infinite variety is excluded. As an example, the more modest de Bruijn diagram for Rule 22 excludes ripples of period 3. Even without exclusion, the loops in the diagram foreshadow regularities in the larger diagram. It would be nice to get a good drawing of the first stage diagram; in years past we had a nice NeXtStep program G'ph which could attempt that, but that was then.

Going on to the second stage diagram, it is a question of aligning successive stripes to get admissible bands. A whole stripe being infinite, a single loop of a given length from the first level diagram can be chosen as a basis for a cross band. Two choices are evident; get a periodic configuration or get an isolated configuration. The first is a consequence of using a loop which is already periodic, although the existence, periodicities, and the rest are awaiting a fresh determination in the cross band. Since it can readily extend to infinity the necessity of repetition arises anew; in principle all finite x infinite configurtations can be foreseen. The second choice for the second level diagram is to select only loops from the connected component of the first level vacuum. That will enable cross bands of finite width and potentially infinite height. But if the connected component of the second level vacuum is nontrivial, configurations of finite extent will be revealed. All of them.

The Zoo article contains details and shows some examples.

Could we derive the "maximum still life density 1/2" from the statistics of de Bruijn diagrams? I ran some monte carlo tests back when this was a topic of active discussion; since solved by Noam Elkies with Voronoi diagrams, I think.
-hvm

H. V. McIntosh
Posts: 49
Joined: June 20th, 2009, 5:26 pm
Location: Mexico

Re: Natural spaceships beyond the glider and *WSS's ?

Post by H. V. McIntosh » July 14th, 2009, 3:28 am

The Zoo article contains details and shows some examples.
David Eppstein's arXiv article "Searching for Spaceships" contains an excellent account of the construction and usage of de Bruijn-like diagrams, making it clear that some search programs, at least, use them, perhaps only implicitly. If one understands "brute force" search as setting up all possible bit patterns in a given region, watching their evolution, and hoping for recognizable results, then de Bruijn searches anticipate the results by trying to extend small regions already known to exhibit the desired behavior. Programming such a search is more complicated, but is guaranteed of success and should procede much faster. Of course such flagrant statements have details which can be quibbled over.

Looking over the Wiki portion of this forum or the other catalogues of Life patterns which can be found on and off the Internet, most of the patterns are grouped in families. Their existence is mostly known to Life practicioners, but their existence does not show up when the patterns are simply catalogued by live cell content; trying to give a whole Wiki page to each pattern is grossly extravagant. An avatar, together with a regular expression characterizing the family, would be more informative and produce a more concise catalog. Regular expressions are the way to characterize graphs, with their loops and all. Equivalent to regular expressions are grammars, such as those Dean Hickerson and David Bell have used to characterize their c/2 and c/3 spaceship families.

Beyond grammars, de Bruijn diagrams, as do graphs in general, have other properties which can be helpful in classify Life objects. For example, the idea of a connected component, in which every vertex can be reached from any other vertex by at least one path. Components are isolated when there is no path from any vertex in one of them to any vertex in the other. An intermediate degree if connectedness arises when there are links from one component to the other, but not in the reverse direction. This idea should be contrasted with the distinction between figures and pseudofigures in the Life classifications.

Aside from the issue of whether some figures can be joined to others, note that the existence of loops implies that the structure defined by the contents of the loop can be repeated at will, giving extensible figures. Viz: boats, long boats, really long boats, tremendously long boats, and so on. The loops correspond to the regular expression operator *, concatination follows the loop and sum makes branches in the path. What might be worth checking in the published and posted literature is whether searches have simply been used to turn up an interesting result, or whether their progress has been mapped with a view to finding families.

Turning to the Zoo article, it was not so easy to read it after two decades; conventions which were obvious at the time weren't so obvious after all. To start with, there are misprints in the table on page 3 - the entry at row ij and column k should always be jk unless it is absent (no link). The same comment evidently applies to the other tables.
The indices themselves are octal numbers referring to the occupancy of the semineighborhoods, 2 wide and three high, so the matching middle index registers an admissible overlap. The decision to include or reject a link follows some boolean property of the neighborhood; for a still life, the predicate is "the evolved cell is the same as the
original." To go further than first neighbors, larger cells ought to be chosen; for example to accomodate several generations of evolution and study shift-periodicity. The Zoo article was only interested in first (Moore) neighbors and one generation.

Whether or not one is willing to lay the diagram out on a large sheet of paper, there are reasonable matrix programs to calculate powers of the matrix: a shortest path is revealed by the first power at which the link in the power matrix deviates from zero, the main diagonal reveals closed loops - both the shortest and the multiplicity, and so on. Components result in a block matrix, and even the eigenvalues and eigenvectors may have some use. All of this gives a first stage de Bruijn diagram, but one wonders of there aren't something like two-dimensional diagrams for something akin to Wang tiles.

Life having a vacuum, zero tiles connect to themselves via a null loop. The connected component of the zero tile reveals potential freestanding configurations, since tile sequences beginning and ending on zero semineighborhoods cannot interact and can go on and on to infinity. Full loops should be chosen, since otherwise joining sequences might be ambiguous; they will lead to periodic structures (agars, most likely) at the second stage.

To get second stage tiles, a 3 high x n strip is chosen with the aid of the first level de Bruijn diagram; indeed several according to the number of distinct loops of length n in that diagram. Supposing thatthose strips have run along horizontally, the time has come to stack copies of them vertically. Their semineighborhoods are 2xn, so it is convenient to describe them by a string of hexadecimal digits taking clusters of four cells starting at the left and ending with an octal digit if the length is odd. The second stage de Bruijn diagram first of all records whether the top row of the bottom strip matches the bottom row of the top strip and so on vertically. It is then a given that the middle row behaves properly.

Again, components are to be sought, loops identified, the zero tile examined and whatever else comes to mind. If zero tiles were present at both levels, freestanding configurations can be found and enumerated. Otherwise agars will result; note that the Wiki only lists only three, but there are ever so many more.

To give a concrete example, take the width 1 still life on page 4. That is too short to make anything but a degenerate example. a column of three zeroes can be copied to maintain zeroes, but copying anything but a central 1 will overcrowd the central 1, giving the three tiles in the figure. At the second stage the zeroes stack vertically, the vertical fibres stack horizontally by periodicity and the result is pure vacuum. The middle 1 can be either at the top or the bottom of its semineighborhood, Tile 1 connects to tile 2 by overlaying the 1's, 2 connects to 1 by overlaying the 0's. Copying the alternating vertical column horizontally results in an agar, wherein rows of live cells alternate vertically with rows of inert cells.

Although this example seems rather contrived, it nevertheless illustrates the scheme which is followed for all greater widths. For example, at width 4, tiles 00, 50, F0, and A0 will make a thick column ending in two single columns of zeroes. This is the mechanism which embeds freestanding in periodic. Furthermore since these tiles are part of the second level zero component, the sequence .. 00 50 F0 A0 00 ... isolates a freestanding block. So it is possible to find all the still lifes according to given freestanding or periodic widths, and entirely arbitrary heights (depths are gotten by reading the links backwards).
-hvm

edwin
Posts: 20
Joined: November 21st, 2014, 4:22 pm

Re: Natural spaceships beyond the glider and *WSS's ?

Post by edwin » August 13th, 2017, 8:21 pm

Elithrion wrote:I think he meant to indicate the relative position, but the variable-width font messed it up, making him add two dots for clarity. It would have been more easily done with the Code tags, by the way, like so:

Code: Select all

[code]
............
.o..........
.ooo.oo.....
......oo....
..o.........
............
[/code]
Alternatively, Nath's site makes for convenient linking once you save patterns, e.g. http://www.conwaylife.com/?p=madmansdiehard
I found a variation on this one. Dies after 215 iterations, though it starts with a slightly bigger bounding box.

x = 8, y = 4, rule = B3/S23
o$b2o3b2o$3bob2o$2bo!

wwei23

Re: Natural spaceships beyond the glider and *WSS's ?

Post by wwei23 » August 17th, 2017, 8:22 pm

MadMan wrote:OK, PM 2Ring, here's the skinny on both...

(1) I use graph paper, to create a personal record of my discoveries. Whenever I discovered a wonderful pattern , back in last century, I would carefully re-input it and make certain of how it's going to grow before reaching its final fate (and to confirm my notes: a few patterns were lost and could NOT be recovered...). Then I would take marker pen and draw each stage in a gen. by gen. record. Junk parts (destined to die without affecting any other part of the pattern) that spin off got jotted down in red while parts destined to survive got indited to paper in either black or blue or maybe green ! It was a personal human touch that no computer program could do ! I used a feltmarker that did not do instant bleedthru like Sharps does. I can no longer find it. I can no longer find the right graph paper, either. It's Turner: the clunk did the skip c.2000. At the time, I felt little 'bout it as I had tired of all the graphing. Now that I had spent 3 years fixing my archives (only 2 GREAT patterns were lost and they are in the Master Index which had been stuck on a higher shelf one night some time BEFORE that flood !).

(2) Now as the Diehard. Mayhaps you had trouble with the diagram. Here it is again...

OOOOOOOOOO
0X00000000000
0XXX0XX000000
000000XX00000
00X0000000000
0000000000000

Thye X's are on cells.'s

Code: Select all

x = 7, y = 4, rule = B3/S23
o$3ob2o$5b2o$bo!

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Natural spaceships beyond the glider and *WSS's ?

Post by Majestas32 » November 27th, 2017, 5:47 pm

edwin wrote:
Elithrion wrote:I think he meant to indicate the relative position, but the variable-width font messed it up, making him add two dots for clarity. It would have been more easily done with the Code tags, by the way, like so:

Code: Select all

[code]
............
.o..........
.ooo.oo.....
......oo....
..o.........
............
[/code]
Alternatively, Nath's site makes for convenient linking once you save patterns, e.g. http://www.conwaylife.com/?p=madmansdiehard
I found a variation on this one. Dies after 215 iterations, though it starts with a slightly bigger bounding box.

x = 8, y = 4, rule = B3/S23
o$b2o3b2o$3bob2o$2bo!
Wow, 8 YEAR necropost???
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

Post Reply