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

Thread for basic questions

For general discussion about Conway's Game of Life.

Re: Thread for basic questions

Postby AforAmpere » February 12th, 2018, 8:07 pm

I have that downloaded, but is there a way to find specific reactions?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 709
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Postby dvgrn » February 13th, 2018, 2:49 am

AforAmpere wrote:I have that downloaded, but is there a way to find specific reactions?

Not without some kind of post-processing script, depending on what you're looking for.

It wouldn't take much to modify chris_c's gencols output processing script to read lines of RLE from that text file, and look for population sequences.

Or we could speed things up a lot by building another file, or extending the original one, to record all the population sequences, or better something like a one- or two- or four-byte hash of each generation. It wouldn't actually be much larger than the current file, but searches could be done really quickly.
User avatar
dvgrn
Moderator
 
Posts: 4696
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby Apple Bottom » February 15th, 2018, 1:16 pm

A question regarding glider syntheses--

There's Gardens of Eden, and there's patterns that (provably) cannot be constructed using gliders. Obviously, the former are a subset of the latter, but are they a strict subset? Put another way, is there a pattern that has a parent, yet is provably inconstructible using gliders?

If yes: is there a known example? If no: can it be proven that "Garden of Eden" and "not glider-constructible" are the same? (And if "we don't know", but also otherwise: is there any published research on this?)

Thanks. :)
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 948
Joined: July 27th, 2015, 2:06 pm

Re: Thread for basic questions

Postby Macbi » February 15th, 2018, 1:50 pm

Apple Bottom wrote:There's Gardens of Eden, and there's patterns that (provably) cannot be constructed using gliders. Obviously, the former are a subset of the latter, but are they a strict subset? Put another way, is there a pattern that has a parent, yet is provably inconstructible using gliders?

If yes: is there a known example? If no: can it be proven that "Garden of Eden" and "not glider-constructible" are the same? (And if "we don't know", but also otherwise: is there any published research on this?)
There's a pattern that has a parent but no grandparent. So it has a parent but no glider construction. So really you want to ask if there is a pattern which has an infinite chain of ancestors (each with finitely many cells) but no glider synthesis. As far as I know this problem is completely open, and no one knows any ways to approach it.

You might begin by working on an easier problem: does every still life have a glider synthesis? We can imagine a sort of "still life printer" that builds up any given still life piece by piece, based on a finite number of recipes that cover every possible way it could want to expand the part it has built so far.
User avatar
Macbi
 
Posts: 473
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Postby Majestas32 » February 15th, 2018, 2:02 pm

I suspect that the answer to the unique father problem is in the affirmative.
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Thread for basic questions

Postby Macbi » February 15th, 2018, 2:35 pm

Majestas32 wrote:I suspect that the answer to the unique father problem is in the affirmative.

If this is true one might be able to find it using the same incremental SAT methods people use to find small orphans.
User avatar
Macbi
 
Posts: 473
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Postby dvgrn » February 15th, 2018, 3:12 pm

Majestas32 wrote:I suspect that the answer to the unique father problem is in the affirmative.

These days I'm leaning toward taking the other side of that bet. It's not quite clear yet that no such still life exists, but it seems like it would have to be very big and very delicately balanced, and therefore probably really difficult to find. We don't have any examples of Gardens of Eden that are anywhere near stability.

The last time the question came up in this thread, it turned out that it was possible to build still lifes that contained large regions that had surprisingly few predecessors besides themselves. We didn't get the number of predecessors down to 1, but we didn't try really hard.

However, there's a problem with the formulation of the unique father problem: it asks for a "stable configuration", which could be read as a requirement for a complete still life. It seems pretty likely that it will always be possible to find one ON cell somewhere around the edge of a still life, where you can run a search to find a predecessor that restores that ON cell and produces the still life.

-- I was thinking that I'd like the unique-father problem to say "a stable configuration that contains a region whose only parent is itself"... but then I think the above link shows that that problem has already been answered in the affirmative. Assuming my JLS search was done right, there's no way to modify the S-shaped tetromino pieces in this still life, so maybe that could be considered a 2x3 region with a unique father? These were the only predecessor options that JLS found:

x = 26, y = 19, rule = B3/S23
3b2ob2o10b2ob2o$4b2obo10bo3bo$5b2o12b3o2$2o3b2o2b2o4b2o2b3o2b2o$o2bobo
2bobo4bo2bobo2bobo$2b2obob2o8b2o3b2o$obo4bo2bo4bobo2bobo2bo$2o2b2o3b2o
4b2o2b3o2b2o$5bo$2o3b2o2b2o4b2o2b3o2b2o$o2bo4bobo4bo2bobo2bobo$2b2obob
2o8b2o3b2o$obo2bobo2bo4bobo2bobo2bo$2o2b2o3b2o4b2o2b3o2b2o2$4b2o13b3o$
3bob2o11bo3bo$3b2ob2o10b2ob2o!

Intuitively I'd expect that a provably inconstructible pattern would be more likely to be an oscillator or spaceship. Maybe a big high-volatility p2 or p3 oscillator? Offhand I can't see how to constrain a search to find a periodic pattern whose only predecessors are its own evolutionary sequence (last unproven conjecture in the list). But "space dust" oscillators and spaceships sometimes do seem to need every bit to be in the right place on every tick.

Seems like there was some further discussion about these problems, but I can't find it offhand, and probably it was mostly high-level theoretical hand-waving anyway. I don't think there have been many published hard results from actual searches.
User avatar
dvgrn
Moderator
 
Posts: 4696
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby Apple Bottom » February 15th, 2018, 3:35 pm

Macbi wrote:There's a pattern that has a parent but no grandparent. So it has a parent but no glider construction. So really you want to ask if there is a pattern which has an infinite chain of ancestors (each with finitely many cells) but no glider synthesis. As far as I know this problem is completely open, and no one knows any ways to approach it.


Ah, yes -- you're right, of course. That's indeed what I should've asked.

You might begin by working on an easier problem: does every still life have a glider synthesis? We can imagine a sort of "still life printer" that builds up any given still life piece by piece, based on a finite number of recipes that cover every possible way it could want to expand the part it has built so far.


I'd expect that the answer to this is "yes", but I couldn't really justify it. There's no reason to assume that you couldn't construct every still life this way, but on the other hand, with Gardens of Edens existing, there's no reason (that's immediately obvious to me) why there couldn't be a (possibly very large) Garden of Eden that's a still life, either.

Speaking of which, are there any known properties that Gardens of Eden must possess? Something that would contradict a (finite) GoE also being a still life, perhaps?

On the flip side -- re: the possibility of a "still life printer", are all still lifes (finite still lifes of sufficient size, anyway) variants/extensions of earlier still lifes, or is there always, for any n, a still life with of population not below n that is not "based on" smaller still lifes, whatever that means?

So many questions, and answers are so scant and elusive. That's life (and Life) for you, eh?

dvgrn wrote:Seems like there was some further discussion about these problems, but I can't find it offhand, and probably it was mostly high-level theoretical hand-waving anyway. I don't think there have been many published hard results from actual searches.


That's the best kind of hand-waving, though. :) In fact I wouldn't be surprised if, if and when we'll be able to answer these sorts of questions, it'll be based on abstract considerations applying to large classes of CAs (or some generalization thereof that is, as of yet, entirely unconceived), and if the answers thus obtained were highly non-constructive, merely (say) proving the existence of certain objects without providing any clue as to how to actually construct them.

In fact I could see this happening right now -- say, someone publishes a paper proving in a neat, novel, non-constructive manner that CAs satisfying ${WEAK_CRITERION} (including Conway Life) are necessarily omniperiodic, or some such thing, and we'd have an abstract result but not be any wiser as to how to actually capture that elusive object that we now know is indeed out there, somewhere.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 948
Joined: July 27th, 2015, 2:06 pm

Re: Thread for basic questions

Postby Macbi » February 15th, 2018, 3:40 pm

Maybe a good phrasing would be
Is there an assignment of alive or dead to a finite number of cells such that (a)the assignment can be extended to a still life and (b)any predecessor (with a finite number of cells) of any pattern (with a finite number of cells) containing those cells also contains those cells?
This would guarantee that such a still life was unsynthesisable.
User avatar
Macbi
 
Posts: 473
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Postby dvgrn » February 15th, 2018, 3:55 pm

Macbi wrote:Maybe a good phrasing would be
Is there an assignment of alive or dead to a finite number of cells such that (a)the assignment can be extended to a still life and (b)any predecessor (with a finite number of cells) of any pattern (with a finite number of cells) containing those cells also contains those cells?
This would guarantee that such a still life was unsynthesisable.

Yes, that sounds good... and it also sounds much less likely than the weaker formulations. We know that there isn't anything really small that fits this criterion -- and the bigger a cell group is, the more edges and corners it has that are likely to be vulnerable to an "attack" to find a repairable change for one cell in the group.

My "unique parent of a 2x3 region" example above definitely only handles immediate one-tick predecessors, by the way. Once the region around the target area has changed, at time T-1 let's say, then it (probably) becomes possible to find different predecessors for the target area as well, at time T-2 or earlier.
User avatar
dvgrn
Moderator
 
Posts: 4696
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby dvgrn » February 15th, 2018, 4:13 pm

Apple Bottom wrote:
You might begin by working on an easier problem: does every still life have a glider synthesis? We can imagine a sort of "still life printer" that builds up any given still life piece by piece, based on a finite number of recipes that cover every possible way it could want to expand the part it has built so far.

I'd expect that the answer to this is "yes", but I couldn't really justify it.
...
On the flip side -- re: the possibility of a "still life printer", are all still lifes (finite still lifes of sufficient size, anyway) variants/extensions of earlier still lifes, or is there always, for any n, a still life with of population not below n that is not "based on" smaller still lifes, whatever that means?

The answer to the first question may possibly be "yes", but we're a long long way from having all the tools needed.

This is mostly because you can't just throw in a recipe to change the state of one bit at a corner of your object under construction, the way you can in a JvN or other specialty replicator-supporting rule.

First you'd usually have to carefully remove some customized stabilizing superstructure (the details of which may depend the states of nearby bits, up to at least six cells away according to Paul Callahan's recent research)

Then -- because the old superstructure was there for a reason! -- you have to instantly build a new stabilizing superstructure, which probably has to be completely different from the previous one, to support the new state of your latest printed cell.

You'd need a toolkit made up of recipes to handle every possible before and after superstructure. Seems like that would easily run into the billions or trillions of recipes. And that means it's really just plain not within reach at the moment. It's hard to see how to even meaningfully work toward it. In practice we can't do still life constructions one bit at a time.

On the variant/extension question: well, there's some not-too-big still life that includes every possible stable-compatible neighborhood of ON and OFF cells -- didn't a challenge show up in the Sandbox about this recently? But the big blobby still lifes are really hard to organize into families... or rather, organization is perfectly possible, but no two people will do it the same way.

Apple Bottom wrote:Speaking of which, are there any known properties that Gardens of Eden must possess? Something that would contradict a (finite) GoE also being a still life, perhaps?

Can't think of anything besides the obvious stuff -- must be bigger than 6x6, must contain more than ten ON cells (I have no proof, but I think I'm pretty safe on this one). A GoE can't be a still life, oscillator, or spaceship, so I think you must be intending to say "(finite) unique-parent pattern" or something like that?
User avatar
dvgrn
Moderator
 
Posts: 4696
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby Macbi » February 15th, 2018, 4:48 pm

Here's something I realised the other day: Agar crawlers can't travel along the stripes of the zebra agar (lightspeed wire) slower than light.

Imagine the stripes are horizontal and all the cells of the crawler are to the left of a vertical line, travelling towards the line. Then there has to be an earliest generation at which cells to the right of the line change. None of the dead ones can become alive in this generation, they have four live neighbours. So some of the live ones have to become dead. But then it's easy to see that the cells to the right of these die in the next generation, and so on. So the changes propagate to the right at the speed of light.

This surprised me because I used to think it would be possible to create a slowly travelling agar crawler. You could have a large bubble containing a universal constructor that deconstructed the agar in front of it and repaired the wire in front of it.

Only you can't, because "deconstructing the agar in front of it" is impossible do do in a controlled fashion.

This shows that you can't do arbitrary tweaks to still lives with gliders. But it doesn't necessarily rule out the constructibility of any still life in particular.
User avatar
Macbi
 
Posts: 473
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Postby Gamedziner » February 15th, 2018, 6:11 pm

Apple Bottom wrote:Speaking of which, are there any known properties that Gardens of Eden must possess? Something that would contradict a (finite) GoE also being a still life, perhaps?

By definition, a GoE has no parents. A still-life is its own parent, and thus always has a parent. These two statements thus show that a still-life GoE is contradictory, and therefore cannot exist.

A still-life with no parents other than itself would answer the unique father problem.
Gamedziner
 
Posts: 485
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: Thread for basic questions

Postby 77topaz » February 15th, 2018, 6:17 pm

Gamedziner wrote:By definition, a GoE has no parents. A still-life is its own parent, and thus always has a parent. These two statements thus show that a still-life GoE is contradictory, and therefore cannot exist.

A still-life with no parents other than itself would answer the unique father problem.


That was already addressed a few posts above yours:

dvgrn wrote:
Apple Bottom wrote:Speaking of which, are there any known properties that Gardens of Eden must possess? Something that would contradict a (finite) GoE also being a still life, perhaps?

Can't think of anything besides the obvious stuff -- must be bigger than 6x6, must contain more than ten ON cells (I have no proof, but I think I'm pretty safe on this one). A GoE can't be a still life, oscillator, or spaceship, so I think you must be intending to say "(finite) unique-parent pattern" or something like that?
User avatar
77topaz
 
Posts: 709
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Postby Gamedziner » February 15th, 2018, 6:18 pm

77topaz wrote:That was already addressed a few posts above yours

Oops.
Gamedziner
 
Posts: 485
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: Thread for basic questions

Postby dvgrn » February 15th, 2018, 6:32 pm

Macbi wrote:Here's something I realised the other day: Agar crawlers can't travel along the stripes of the zebra agar (lightspeed wire) slower than light.
...
... "deconstructing the agar in front of it" is impossible do do in a controlled fashion.

This shows that you can't do arbitrary tweaks to still lives with gliders. But it doesn't necessarily rule out the constructibility of any still life in particular.

The proof about minimum speed of negative spaceships parallel to zebra stripes has been around quite a while. See, e.g., the with the grain article.

That's a nice application to incremental still-life construction -- or in this case,
incremental destruction.

But for the construction problem, maybe a finite patch of zebra stripes agar --

x = 54, y = 53, rule = B3/S23
bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo$b52o2$b52o$o52bo
$b52o2$b52o$o52bo$b52o2$b52o$o52bo$b52o2$b52o$o52bo$b52o2$b52o$o52bo$b
52o2$b52o$o52bo$b52o2$b52o$o52bo$b52o2$b52o$o52bo$b52o2$b52o$o52bo$b
52o2$b52o$o52bo$b52o2$b52o$o52bo$b52o2$b52o$o52bo$b52o2$b52o$bo2bo2bo
2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo!

-- would be a relatively simple test case that might show that the "still life printer" bit-by-bit construction method can't be made universal, maybe because some incremental changes have no viable stabilization. (?)

The blocks agar might be another case worth investigating. Back in 2014 Calcyman sent me a pattern that might hint at an incremental construction:

x = 29, y = 54, rule = B3/S23
2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob
2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2ob2ob2ob
2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2ob2ob2ob2ob2ob2ob
2o$2ob2ob2ob2obo3bob2ob2ob2ob2o$12bo3bo$2ob2ob2ob3o3b2o$2ob2ob2obo7$2o
b2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2o
b2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2ob2ob2ob2o
b2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o
$2ob2ob2ob2obo3bobo3bob2ob2o$12bo3bobo3bo$2ob2ob2ob3o5bo3b2o$2ob2ob2ob
o7$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob
2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2ob2ob
2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2o2$2ob2ob2ob2ob2ob2ob2ob2ob
2ob2o$2ob2ob2ob2ob2ob2obo3bob2ob2o$18bo3bo$2ob2ob2ob2ob2ob3o3b2o$2ob2o
b2ob2ob2obo!

Now, I definitely don't see how to apply sparks to complete those transitions. That doesn't mean it can't be done -- could try asking WLS/JLS/lifesrc, maybe. But I suppose a negative answer to that search wouldn't help much, unless there's a way to show that there are no other possible options for incrementally adding a block.
User avatar
dvgrn
Moderator
 
Posts: 4696
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby AforAmpere » February 17th, 2018, 6:49 pm

How does depth work in knightt? How do you search for a ship with depth, because I get different final partials with different depths.

This command ends prematurely:
./knightt -e -p 7 -x 2 -w 9
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 709
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Postby danny » February 18th, 2018, 11:31 pm

What's the biggest notable pattern that has ever been constructed in an OCA?
get down with the sickness.
User avatar
danny
 
Posts: 593
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

Re: Thread for basic questions

Postby wildmyron » February 19th, 2018, 12:29 am

danny wrote:What's the biggest notable pattern that has ever been constructed in an OCA?

"Biggest" and "notable" are rather vague in this context, however, one pattern which might qualify is calcyman's c/24 backward glider rake in HighLife which has a population of >10^6 cells. I'm sure there are larger patterns to be found in the CA literature.

The difficulty with this kind of question is that there's no limit to how big you can go, particularly with rules such as Emmanual Sapin's Rule R which have an explicit unit cell for B3/S23*. For any large, non-expanding, notable pattern in B3/S23, you could emulate the pattern in Rule R and hey presto, you've got a large, notable pattern in an OCA. Whether anyone has actually done this I'm not sure.

* It is unfortunate that that post and dvgrn's conversion of the gun collection are buried in the Sandbox, but they're there.
wildmyron
 
Posts: 790
Joined: August 9th, 2013, 12:45 am

Re: Thread for basic questions

Postby 77topaz » February 19th, 2018, 5:03 am

I was about to suggest the tDryLife pondlayer-based spaceship (population varying between 6800-7000 cells), but that HighLife rake rather blows that out of the water. :P
User avatar
77topaz
 
Posts: 709
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Postby Sokwe » February 19th, 2018, 6:18 am

wildmyron wrote:
danny wrote:What's the biggest notable pattern that has ever been constructed in an OCA?

"Biggest" and "notable" are rather vague in this context, however, one pattern which might qualify is calcyman's c/24 backward glider rake in HighLife which has a population of >10^6 cells.

It depends on what "constructed" means. That link mentions the c/69 basilisk in HighLife, which is much larger than the c/24 rake, but it was never put into a form that could be run with Golly (it's just too large).
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1255
Joined: July 9th, 2009, 2:44 pm

Re: Thread for basic questions

Postby AforAmpere » February 22nd, 2018, 8:11 pm

What speed waves have been found? I know of C, the 12c/28 wave, but that is all I know for orthogonal waves. Is a 2c/3 wave possible?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 709
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Postby 77topaz » February 22nd, 2018, 9:02 pm

AforAmpere wrote:What speed waves have been found? I know of C, the 12c/28 wave, but that is all I know for orthogonal waves. Is a 2c/3 wave possible?


There's also a c/4 wave which can be supported by various spaceships, plus a (2,1)c/6 wave (knightwave) and an 8c/96 (c/12) wave (switchwave).
User avatar
77topaz
 
Posts: 709
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Postby AforAmpere » February 24th, 2018, 12:20 pm

In what LTL rules are ships impossible? Are R2 rules with B2 impossible to have spaceships?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 709
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Postby danny » February 24th, 2018, 4:16 pm

Are spaceships faster than c/3 really impossible in justfriends? Is there a proof?
get down with the sickness.
User avatar
danny
 
Posts: 593
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

PreviousNext

Return to General Discussion

Who is online

Users browsing this forum: wildmyron and 2 guests