Page 36 of 190

Re: Thread for basic questions

Posted: February 12th, 2018, 8:07 pm
by AforAmpere
I have that downloaded, but is there a way to find specific reactions?

Re: Thread for basic questions

Posted: February 13th, 2018, 2:49 am
by dvgrn
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 1:16 pm
by Apple Bottom
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. :)

Re: Thread for basic questions

Posted: February 15th, 2018, 1:50 pm
by Macbi
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 2:02 pm
by Majestas32
I suspect that the answer to the unique father problem is in the affirmative.

Re: Thread for basic questions

Posted: February 15th, 2018, 2:35 pm
by Macbi
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 3:12 pm
by dvgrn
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:

Code: Select all

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.

Re: Thread for basic questions

Posted: February 15th, 2018, 3:35 pm
by Apple Bottom
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 3:40 pm
by Macbi
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 3:55 pm
by dvgrn
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 4:13 pm
by dvgrn
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?

Re: Thread for basic questions

Posted: February 15th, 2018, 4:48 pm
by Macbi
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 6:11 pm
by Gamedziner
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.

Re: Thread for basic questions

Posted: February 15th, 2018, 6:17 pm
by 77topaz
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?

Re: Thread for basic questions

Posted: February 15th, 2018, 6:18 pm
by Gamedziner
77topaz wrote:That was already addressed a few posts above yours
Oops.

Re: Thread for basic questions

Posted: February 15th, 2018, 6:32 pm
by dvgrn
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 --

Code: Select all

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:

Code: Select all

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.

Re: Thread for basic questions

Posted: February 17th, 2018, 6:49 pm
by AforAmpere
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:

Code: Select all

./knightt -e -p 7 -x 2 -w 9

Re: Thread for basic questions

Posted: February 18th, 2018, 11:31 pm
by dani
What's the biggest notable pattern that has ever been constructed in an OCA?

Re: Thread for basic questions

Posted: February 19th, 2018, 12:29 am
by wildmyron
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.

Re: Thread for basic questions

Posted: February 19th, 2018, 5:03 am
by 77topaz
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

Re: Thread for basic questions

Posted: February 19th, 2018, 6:18 am
by Sokwe
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).

Re: Thread for basic questions

Posted: February 22nd, 2018, 8:11 pm
by AforAmpere
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?

Re: Thread for basic questions

Posted: February 22nd, 2018, 9:02 pm
by 77topaz
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).

Re: Thread for basic questions

Posted: February 24th, 2018, 12:20 pm
by AforAmpere
In what LTL rules are ships impossible? Are R2 rules with B2 impossible to have spaceships?

Re: Thread for basic questions

Posted: February 24th, 2018, 4:16 pm
by dani
Are spaceships faster than c/3 really impossible in justfriends? Is there a proof?