Thread for basic questions
-
- Posts: 1334
- Joined: July 1st, 2016, 3:58 pm
Re: Thread for basic questions
I have that downloaded, but is there a way to find specific reactions?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Re: Thread for basic questions
Not without some kind of post-processing script, depending on what you're looking for.AforAmpere wrote:I have that downloaded, but is there a way to find specific reactions?
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.
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
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.
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
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.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?)
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.
- Majestas32
- Posts: 549
- Joined: November 20th, 2017, 12:22 pm
- Location: 'Merica
Re: Thread for basic questions
I suspect that the answer to the unique father problem is in the affirmative.
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i
Currently looking for help searching these rules.
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i
Currently looking for help searching these rules.
Re: Thread for basic questions
If this is true one might be able to find it using the same incremental SAT methods people use to find small orphans.Majestas32 wrote:I suspect that the answer to the unique father problem is in the affirmative.
Re: Thread for basic questions
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.Majestas32 wrote:I suspect that the answer to the unique father problem is in the affirmative.
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!
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.
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
Ah, yes -- you're right, of course. That's indeed what I should've asked.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.
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.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.
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?
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.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.
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
Maybe a good phrasing would be
This would guarantee that such a still life was unsynthesisable.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?
Re: Thread for basic questions
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.Macbi wrote:Maybe a good phrasing would beThis would guarantee that such a still life was unsynthesisable.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?
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
The answer to the first question may possibly be "yes", but we're a long long way from having all the tools needed.Apple Bottom wrote:I'd expect that the answer to this is "yes", but I couldn't really justify 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.
...
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?
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.
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?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?
Re: Thread for basic questions
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.
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.
-
- Posts: 795
- Joined: May 30th, 2016, 8:47 pm
- Location: Milky Way Galaxy: Planet Earth
Re: Thread for basic questions
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.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?
A still-life with no parents other than itself would answer the unique father problem.
Code: Select all
x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!
Re: Thread for basic questions
That was already addressed a few posts above yours: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.
dvgrn wrote: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?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?
-
- Posts: 795
- Joined: May 30th, 2016, 8:47 pm
- Location: Milky Way Galaxy: Planet Earth
Re: Thread for basic questions
Oops.77topaz wrote:That was already addressed a few posts above yours
Code: Select all
x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!
Re: Thread for basic questions
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.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.
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!
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!
-
- Posts: 1334
- Joined: July 1st, 2016, 3:58 pm
Re: Thread for basic questions
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:
This command ends prematurely:
Code: Select all
./knightt -e -p 7 -x 2 -w 9
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Re: Thread for basic questions
What's the biggest notable pattern that has ever been constructed in an OCA?
Re: Thread for basic questions
"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.danny wrote:What's the biggest notable pattern that has ever been constructed in an OCA?
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.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.
Semi-active here - recovering from a severe case of LWTDS.
Semi-active here - recovering from a severe case of LWTDS.
Re: Thread for basic questions
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.
Re: Thread for basic questions
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).wildmyron wrote:"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.danny wrote:What's the biggest notable pattern that has ever been constructed in an OCA?
-Matthias Merzenich
-
- Posts: 1334
- Joined: July 1st, 2016, 3:58 pm
Re: Thread for basic questions
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?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Re: Thread for basic questions
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).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?
-
- Posts: 1334
- Joined: July 1st, 2016, 3:58 pm
Re: Thread for basic questions
In what LTL rules are ships impossible? Are R2 rules with B2 impossible to have spaceships?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Re: Thread for basic questions
Are spaceships faster than c/3 really impossible in justfriends? Is there a proof?