ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Natural spaceships beyond the glider and *WSS's ?

For general discussion about Conway's Game of Life.

Natural spaceships beyond the glider and *WSS's ?

Postby Lewis » June 14th, 2009, 8:19 am

Are any other spaceships or puffers known to occur naturally, apart from the 4 standard spaceships and the 2 switch engines? And Could a program be made that detects all spaceships given off by random starting patterns?
User avatar
Lewis
 
Posts: 316
Joined: March 17th, 2009, 5:26 pm
Location: UK

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

Postby Nathaniel » June 14th, 2009, 9:15 am

Lewis wrote:Are any other spaceships or puffers known to occur naturally, apart from the 4 standard spaceships and the 2 switch engines? And Could a program be made that detects all spaceships given off by random starting patterns?


Achim Flammenkamp did some searches (results) but didn't find a single occurrence of anything except for the objects you mentioned. I'm not sure if his software is available anywhere or not.
User avatar
Nathaniel
Site Admin
 
Posts: 407
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada

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

Postby PM 2Ring » June 15th, 2009, 12:55 pm

The Oscar script supplied with Golly can find oscillators, including spaceships & knightships.
For each generation, calculate a hash value for the pattern.
[...]
When the current hash matches one of the saved hashes, it is highly likely the pattern is oscillating. By keeping a corresponding list of generation counts we can calculate the period. We also keep lists of population counts and bounding boxes; they are used to reduce the chance of spurious oscillator detection due to hash collisions. The bounding box info also allows us to detect moving oscillators (spaceships/knightships).

FWIW, I discovered a natural LWSS recently in debris from multiple glider gun collisions (not using Oscar, though). Here's the progenitor:
Image

Edit. Actually, that's a MWSS, as Lewis kindly pointed out below.
Last edited by PM 2Ring on June 19th, 2009, 10:11 am, edited 1 time in total.
User avatar
PM 2Ring
 
Posts: 152
Joined: March 26th, 2009, 11:18 am

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

Postby Nathaniel » June 15th, 2009, 2:05 pm

PM 2Ring wrote:The Oscar script supplied with Golly can find oscillators, including spaceships & knightships.


Is there a (feasible) way to modify the script so that it can detect gliders in the presence of other stuff? For example, if you run the R-pentomino under that script it goes forever because hashes never match because gliders go out in all directions. Is there a simple fix for that?
User avatar
Nathaniel
Site Admin
 
Posts: 407
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada

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

Postby Lewis » June 15th, 2009, 2:59 pm

PM 2Ring wrote:FWIW, I discovered a natural LWSS recently in debris from multiple glider gun collisions (not using Oscar, though). Here's the progenitor:
(image)

Isn't that a MWSS?

Here is a HWSS occuring from some debris, similar to the one posted above:
Image
bo$2o6$11bo$10b2o$9b2o$10bo2bo$11b2o4$9bo$8b2o$10bo
User avatar
Lewis
 
Posts: 316
Joined: March 17th, 2009, 5:26 pm
Location: UK

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

Postby MadMan » June 17th, 2009, 8:59 am

Only the glider and the familiar P4 spaceships seem to occur naturally in Life.
Recently a possible infinity of mega-gliders have been found (P4 diagonal spaceships with glider reflection each 2 gen.), all having 1 or more basic gliders towing (by induction) a shapeless mass behind them. In one at least, the glider never frees itself from the raw matter. These mega-gliders never occur naturally. But, then again, virtually all the oscillators are artificial. Whether any P6 diagonal spaceships show glide reflection, I don't know. Calling such gliders would require relaxing the definition a bit.

Tagalongs, sidecars, and pushalongs that behave like spaceships due to induction from the spaceship core (the simplest examples are the OWSS's that run because the convoy spaceships suppress their sparks, and Schick's Flying Machine where a T-tetronimo is inducted into being pulled along by 2 spaceships at period 12) make this class unbounded. They do NOT appear naturally in a random broth. The regular spaceships occasionally do, and, while ancestors have been found by me, they reach maturity too quickly.

Spaceships of periods 2, 3, 5,6,7 and 9 never appear naturally. The last mentioned has a P3 body, BUT a blinker is produced and then re-ingested in the next 2 periods, making it a FAILED puffer and its period is now 9 (nine). Many of these can be endlessly extended. I conjecture that not only are there an infinity of different spaceships, but an infinity of spaceships for each period. These spaceships are all large complex engines, and the Caterpillar is literally the size of the late World Trade Center if attempted on 10 boxes/ inch graph paper -which I can no longer find in stores (Mr. Turner, my only sourse, did the skip around 2000 and the store was finally sold at a Sheriff's Auction months later).
MadMan
 
Posts: 21
Joined: June 14th, 2009, 11:40 am

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

Postby Macbi » June 17th, 2009, 10:46 am

The spaceship/pseudospaceship issue is probably even more subtle than it is with stable patterns.
User avatar
Macbi
 
Posts: 161
Joined: March 29th, 2009, 4:58 am

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

Postby calcyman » June 17th, 2009, 10:55 am

Whether any P6 diagonal spaceships show glide reflection, I don't know.


Have you encountered Nicolay Beluchenko's 'Seal' spaceship? That's p6 and glide-reflects every three generations.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1348
Joined: June 1st, 2009, 4:32 pm

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

Postby MadMan » June 18th, 2009, 9:28 am

I think I found what you're talking about.

It was NOT called the Seal and the brief description did NOT say it glide reflects. That -and its large size- prevented me from considering it. Also, the patterns in this website have had mistakes: there was a P37 oscillator, the first known, BUT I could not see it for all the rubbish in the picture. Also a P6 spaceship could not be made to work -I tried ! Another pattern I rejected -the author said it turns out to not work -a spark malignantly attacks and wrecks it instead of vanishing. He neglected to play-test it or he'd have saved space by throwing it in the trash. There were times I had lost a promising pattern because my memory pffted on me or my notes were garbled, and usually after over an hour of struggle, I would lose my temper and tear up the notes !

After 51 volumes of life patterns, it got somewhat galling. Everytime I found a good ancestor or diehard -and didn't lose it- I had to check it against already graphed patterns -and I began doing that after finding a few doops that were a waste of space & time to have done all over again. I was also getting annoyed at finding legions of new stuff instead of substantial improvements of old. There finally came the day when I just put down the pen and stopped. Also Turner did the skip about that time. The volumes went into the cellar and years later...

Now I am finishing repairs and updates. My Master Index (vol.0) which was on a higher shelf and didn't get soaked (the marker ink washed off, esp. in the current vol. 5) alone made it feasible to repair things.

This Seal spaceship (and P6 glider) may complete Vol. 21. I am now about to key it into a life program I have on desktop. It runs outside the net and is far superior to the ones I wrote years ago, when the APPLE ][ was the vogue. Thanks to Bill Gates, it's gone, my software is useless and my software company (Wilsoft EnterpriZes) is out of business. Not one sale made ! I wish Bill Gates all the bad luck in the world ! And my curses have a habit of coming true ! :evil: :twisted:
MadMan
 
Posts: 21
Joined: June 14th, 2009, 11:40 am

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

Postby MadMan » June 18th, 2009, 9:46 am

I wonder why "Machi" includes a pic of the MONSTROUS spaceship mercifully cloaked under the name "Caterpillar" in his posts...
MadMan
 
Posts: 21
Joined: June 14th, 2009, 11:40 am

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

Postby Macbi » June 18th, 2009, 11:30 am

Someday I'll marshal enough computer power to watch what happens when a caterpillar hits a solitary block...
User avatar
Macbi
 
Posts: 161
Joined: March 29th, 2009, 4:58 am

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

Postby calcyman » June 18th, 2009, 12:04 pm

It was NOT called the Seal and the brief description did NOT say it glide reflects.



Are we talking about the same spaceship? I'm referring to this one:

http://www.conwaylife.com/wiki/index.php?title=Seal

which is called the Seal and does glide-reflect.


If you've found a different p6 diagonal glider-reflecting spaceship, then by all means share it with us.


Another pattern I rejected -the author said it turns out to not work...


You're talking about the AK47 reaction, aren't you? That's been stabilised into a functioning gun.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1348
Joined: June 1st, 2009, 4:32 pm

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

Postby MadMan » June 18th, 2009, 5:15 pm

Yes, that's the huge shapeless diagonal spaceship I just graphed into what is now vol. 21 of my books, replacing an ungainly pattern that wasn't edifying but was space-wasting. That bled onto the other side of the page and I used chlorox to clean up the graph paper and to help fix the wonderful bookends ancestor ( 155gen.) on the other side. The uggy pattern was NOT worth repairing. IF I give the wonderful bookends ancestor pattern, it won't be in the gibberish strings of 0's that this site is so fond of, and which I can NOT understand or use.

The file you directed me to also named a tagalong which makes it even more shapeless and artificial.I found the P6 diagonal spaceship (and seal-glider) in the archives of this web-site but it was NOT described as glide-reflecting. The file you directed me to didn't either, but it gave a tagalong mess. Now I'll add that and close the gap left by chloroxing those pages.

I am happy that after several years I am at last once again conversing with somebody knowledgable with Conway's "game" of life. Everybody else has drifted on or become too old. My father was a good listener, but he was just being friendly. He died in 2003. My mother wasn't at all interested. She died in 2007. I am all alone. I got this laptop to help recover from my grief and the burdens of responsibility I must deal with. Nobody to field phone calls for me...
MadMan
 
Posts: 21
Joined: June 14th, 2009, 11:40 am

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

Postby PM 2Ring » June 19th, 2009, 10:09 am

Lewis wrote:
PM 2Ring wrote:FWIW, I discovered a natural LWSS recently in debris from multiple glider gun collisions (not using Oscar, though). Here's the progenitor:
(image)

Isn't that a MWSS?

Oops! You're right, Lewis. Thanks! I better fix the original post.
User avatar
PM 2Ring
 
Posts: 152
Joined: March 26th, 2009, 11:18 am

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

Postby calcyman » June 19th, 2009, 12:10 pm

I found the P6 diagonal spaceship (and seal-glider) in the archives of this web-site but it was NOT described as glide-reflecting.


True, the article doesn't directly describe it as glide-reflecting (although it is categorised under 'glide symmetric spaceships').


When you say 'P6 diagonal spaceship and seal-glider', you mean that there is another p6 diagonal spaceship? I thought that the seal (and optionally the tagalong) is the only c/6 diagonal spaceship. If you've discovered another spaceship that fulfils those criteria, then please could you publish it?



it won't be in the gibberish strings of 0's that this site is so fond of, and which I can NOT understand or use.


If you are talking about RLE, for example:

x = 52, y = 45, rule = S23/B3
obo$boo$bo10$22bo$21bobo$21bobo$22bo12$31boo$31boo$$13boo$12bobo$12bo$
11boo$42boo$41bobbobboo$41bobo4bo$22boo18bo5boboo$21bobo21boobobo$21bo
23bobbobbo$20boo20bo4bobboo$42b5o$$44boobo$44boboo!


then you can copy and paste it into practically any Life editor.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1348
Joined: June 1st, 2009, 4:32 pm

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

Postby PM 2Ring » June 19th, 2009, 3:34 pm

MadMan wrote:IF I give the wonderful bookends ancestor pattern, it won't be in the gibberish strings of 0's that this site is so fond of, and which I can NOT understand or use.

I assume you are talking about RLE encoding. I agree that it's not easy to tell what a pattern looks like in this notation, but that is not its purpose. It's a fairly simple format for programs to read & write, it offers moderate compression for small to medium patterns, and it's suitable for pasting into emails or forums like this one.

If you post patterns here, most of us would prefer if you use RLE format, although simple text format (as used in the Life Lexicon) is ok for small patterns. Alternatively, you can upload the pattern as a GIF or PNG graphic file to an image hosting site like PhotoBucket and link to it, or inline it using the "Img" tags.

As calcyman mentioned, most modern Life programs can read & write life patterns in RLE. What Life software do you use, MadMan?

There is also a simple CLI program by Mark D. Niemiec which converts RLE to plain text. Unfortunately, there's a bug in that program that causes it to make errors on some patterns. But fortunately, Mark supplies the source code for this program, and I've fixed the bug. I was planning to make a few enhancements but I haven't gotten around to it yet; I got side-tracked. :) But I can post the modified C source code if you (or anyone) is interested. I can also post a Linux executable, but I don't have the tools to build one for Windows, sorry.

From the docs:
M. Niemiec wrote:NAME
RLE2TXT - Life RLE file conversion utility, by Mark D. Niemiec

SYNOPSIS
RLE2TXT [-C[.[o[x[y[z]]]]]] infile.rle outfile.txt

DESCRIPTION
RLE2TXT converts a Life file in RLE format into a plain text file.
By default, dead cells are displayed as periods, while living cells
are displayed as Os. If multiple living states exist in the RLE
file, the first four such states are displayed as O, X, Y, and Z.
Other codes in the RLE file are displayed as-is without translation.

The output characters can be overridden by the -C command:

FWIW, here's the link to the original version.

One thing that I don't like about this program is that it doesn't pad the ends of lines to the same width, but that's just a minor quibble.

(I suppose the best place to post this program will be in the Scripts subforum).
User avatar
PM 2Ring
 
Posts: 152
Joined: March 26th, 2009, 11:18 am

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

Postby MadMan » June 19th, 2009, 6:07 pm

For examples of patterns I posted -please refer to "Stable Life?", the forum next door. I am proud of my super-diehard and I feel I have a lead towards finding a P19 oscillator. I used an "applet" from a Life website and one of the editable work spaces of another.
I find the article on "IceNine" quite suspect and a joke. The SpaceFiller is not a joke, but a monstrosity of unlimited growth and void of any & all stable stagnant matter - eternally ! The monstrosity called a Wick Generator (one side oscillates at P4, the other at P5 and moves as a spaceship, gradually grows ever longer and never generates any stable stagnant matter.
I have another less elegant super-diehard that was almost wiped by the cellar flood that demolished my archival volumes. It was redone by hand, save for 50 gen. near the start, that had to be recomputed on my laptop: the info was corrupted by bleed-thru from a diehard on the opposite side of the page.
MadMan
 
Posts: 21
Joined: June 14th, 2009, 11:40 am

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

Postby Lewis » June 20th, 2009, 4:45 am

MadMan wrote: I find the article on "IceNine" quite suspect and a joke. The SpaceFiller is not a joke, but a monstrosity of unlimited growth and void of any & all stable stagnant matter - eternally

I thought the same way when I read the 'IceNine' post. It seems too much of a coincidence that both the file and the search program were lost wthin a few days of eachother, and before anyone else was sent a copy of the pattern file.
User avatar
Lewis
 
Posts: 316
Joined: March 17th, 2009, 5:26 pm
Location: UK

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

Postby Macbi » June 20th, 2009, 5:31 am

I'm sure it wasn't meant to be taken seriously.
User avatar
Macbi
 
Posts: 161
Joined: March 29th, 2009, 4:58 am

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

Postby DivusIulius » June 20th, 2009, 6:14 am

Let me rephrase Lewis' question:
"What is the smallest spaceship that is not a glider or a light/medium/heavy spaceship?"

Note: smallest in terms of number of alive cells, size of the bounding box, or both.

Got any clue? :?:
User avatar
DivusIulius
 
Posts: 89
Joined: April 1st, 2009, 11:23 am

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

Postby Macbi » June 20th, 2009, 6:38 am

Aside from *WSS derivatives, I think this might be the winner on all those counts:
x = 12, y = 11, rule = B3/S23
3bo$2b3o$bo3bo$b2ob2o$9bo$4obo2bobo$bo2bo2bo3bo$7b2obo$8b2o$8b2o$9bo!
User avatar
Macbi
 
Posts: 161
Joined: March 29th, 2009, 4:58 am

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

Postby Lewis » June 20th, 2009, 7:07 am

The spaceships at http://www.conwaylife.com/wiki/index.php?title=25P3H1V0.1 (c/3) are smaller in terms of population and boundinx box than the 2c/5.
User avatar
Lewis
 
Posts: 316
Joined: March 17th, 2009, 5:26 pm
Location: UK

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

Postby calcyman » June 20th, 2009, 11:34 am

I thought the same way when I read the 'IceNine' post. It seems too much of a coincidence that both the file and the search program were lost wthin a few days of each other, and before anyone else was sent a copy of the pattern file.


The point is that he did upload the pattern - only it was censored automatically because 11.9 MB of 'gibberish', as MadMan calls it, could be a virus. Of course a Life pattern isn't a virus, but the protection system didn't know that.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1348
Joined: June 1st, 2009, 4:32 pm

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

Postby hkoenig » June 20th, 2009, 11:45 am

Here are other spaceships of 30 or fewer bits:

x=73, y=33
8b2o11b3o16bob2ob3o14bo$7b2o11bo2bo6b3o6b2ob2o4b2obo6b3ob3o$9bo10bo4bo4bo2b
o4bo2bobo2bo3b3o4bo6b2o$11b2o10bobo2bo4bo5bo5bo3bo3bo4b2o3bo2bo3bo$10bo9b
2o4bobobo21bo15b4o$25bobo4b2o34bo3bo$9bo2bo10bo4bo37bo2bobo$b2o5b2o14bo5b
o36bo$2o5bo21bo$2bo4bobo$4b2o2bo$4b2o6$7b3o15b2o19bo$7bo16b2o18b4o$8bo17b
o13b2ob2o3bo3bo$10b2o16b2o10b2o2bo5b4o$9b2o16bo11bo2bo7bo3bo$48bo2bobo$8b
o17bo2bo19bo$3o5bo2bo11b2obo$o7bo13b2o4bo$bo2b5obo13bobo2bo$3bo25bo$4b2o20b
o2bo$27bobo$27bobo$28b2o$28bo!
hkoenig
 
Posts: 57
Joined: June 20th, 2009, 11:40 am

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

Postby H. V. McIntosh » June 21st, 2009, 1:45 am

Lewis wrote:Are any other spaceships or puffers known to occur naturally, apart from the 4 standard spaceships and the 2 switch engines? And could a program be made that detects all spaceships given off by random starting patterns?


"Natural" probably means artifacts which manifest after a certain lapse of time starting from a random initial configuration of a certain density (can we also choose its variance?); if so there have been numerous experiments, as other replies have indicated. But there is also a substantial lore with respect to possible shift periodic entities, such as "Searching for Spaceships" by David Eppstein (arXiv:cs/0004003v2 from April 26, 2000) which can be found by using Google on the Internet.

De Bruijn diagrams are an excellent tool for such a search, although to use them effectively for a two dimensional automaton such as Life they should be rendered one dimensional by searching either a periodic strip or an isolated strip. Completely finite objects are readily extracted from isolated strips, although the width of the strip will limit the size of the bounding box in that direction. The other would be as large as necessary, depending upon the length of a maximum loop in a finite diagram. Google will also reveal my articles, "Life's Still Lifes" and "A Zoo of Life Forms," wherein some examples are given.

The reason that these results, which are now ten years old, are not more extensive is the enormous amount of computation involved; think of 2^49 for c/3 results. Nowadays there is so much computer power going to waste that a new attempt might be worthwhile. However, still lifes and light speed objects were feasible, as were third generation objects such as c/2 space ships and phoenixes. Mostly, they verified Dean Hickerson's grammars, but with the reassurance there probably weren't still undiscovered objects lying about. Certainly not small ones.

The fourth generation could have encompassed David Bell's c/3 grammars, but we never made the attermpt. And no matter what, that is not the way to attack really large bounding boxes. Eppstein mentions more limited tactics, such as working incrementally with a de Bruijn fragment, but directly in two dimensions. And of course, there are still the brute force searches.
H. V. McIntosh
 
Posts: 49
Joined: June 20th, 2009, 5:26 pm
Location: Mexico

Next

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests

cron