Re: Thread for basic questions
Posted: April 10th, 2016, 11:25 am
Thanks — I have to say, though, I didn't find the "diagram that illustrates the idea" at all enlightening.dvgrn wrote: See the Life Lexicon definition for starters.
ConwayLife.com
Forums for Conway's Game of Life
https://conwaylife.com/forums/
Thread for basic questions
Page 3 of 246
Re: Thread for basic questions
Posted: April 10th, 2016, 11:50 am
Understandable. It's really a subject that needs a full article, not a dictionary definition -- see the article that codeholic recommended. Also compare the helices in the Caterloopillar and in the waterbear.Rich Holmes wrote:Thanks — I have to say, though, I didn't find the "diagram that illustrates the idea" at all enlightening.dvgrn wrote: See the Life Lexicon definition for starters.
The key idea is to find the advertised period of a helix, T. Run the helix for exactly T ticks, and notice that the active reaction that's "burning" at the front of the helix is in exactly the same state as it was T ticks ago -- but the reaction has moved a certain (X, Y) distance. The helix will always be carefully designed so that (X, Y, T) exactly matches the direction and speed of motion of the spaceship that the helix is part of, so that the whole structure becomes self-supporting.
I have a note in my Life Lexicon update project to mention the period and speed for that illustration, which is 65c/213 I believe. That is, the helix returns to its original state in 213 ticks, at which time the glider has moved 65 ticks forward:
Code: Select all
x = 47, y = 206, rule = LifeHistory
37.2D$37.D.D$37.D60$32.A$18.A12.3A$17.3A4.3A3.2A.A$10.3A3.2A.A3.A2.A
3.3A4.2C$9.A2.A3.3A7.A4.2A4.C.C$12.A4.2A3.A3.A10.C$8.A3.A9.A3.A$.3A4.
A3.A13.A$A2.A8.A10.A.A$3.A5.A.A$3.A$A.A3$11.A$10.3A$9.2A.A$9.3A$10.2A
3$16.3A$15.A2.A5.A5.3A$18.A4.3A3.A2.A5.A$18.A4.A.2A5.A4.3A$5.3A7.A.A
6.3A5.A4.A.2A$4.A2.A16.3A2.A.A6.3A$7.A16.3A11.3A$7.A16.2A12.3A$4.A.A
31.2A$44.A$43.3A$43.A.2A$44.3A$44.2A7$42.A$31.3A7.3A$17.3A5.A5.A2.A6.
A.2A$11.A5.A2.A3.3A4.A10.3A$10.3A4.A5.2A.A4.A10.3A$9.2A.A4.A5.3A6.A.A
7.2A$9.3A6.A.A2.3A$2.A6.3A11.3A$.3A5.3A12.2A$2A.A6.2A$3A40.A$.2A39.3A
$42.A.2A$43.3A$43.2A$10.3A$10.A2.A$10.A$10.A$11.A.A2$17.A$16.3A12.A$
15.2A.A4.3A4.3A$15.3A4.A2.A3.2A.A4.3A$6.A9.2A7.A3.3A4.A2.A$5.3A13.A3.
A4.2A7.A$4.2A.A13.A3.A9.A3.A$4.3A18.A9.A3.A$5.2A15.A.A14.A$36.A.A$43.
3A$42.A2.A$45.A$45.A$42.A.A7$32.A8.3A$18.A12.3A6.A2.A$17.3A4.3A4.A.2A
8.A$10.3A4.A.2A3.A2.A4.3A4.A3.A$10.A2.A4.3A3.A7.2A9.A$10.A7.2A4.A3.A
11.A.A$10.A3.A9.A3.A$.3A6.A3.A9.A$.A2.A5.A14.A.A$.A9.A.A$.A40.3A$2.A.
A36.A2.A$44.A$44.A$11.A29.A.A$10.3A$10.A.2A$11.3A$11.2A3$16.3A$16.A2.
A4.A5.3A$16.A6.3A4.A2.A4.A$16.A5.2A.A4.A6.3A$5.3A9.A.A2.3A5.A5.2A.A$
5.A2.A13.3A6.A.A2.3A$5.A16.3A11.3A$5.A17.2A11.3A$6.A.A28.2A$44.A$43.
3A$42.2A.A$42.3A$43.2A7$42.A$31.3A7.3A$17.3A5.A4.A2.A6.2A.A$11.A4.A2.
A4.3A6.A6.3A$10.3A6.A4.A.2A5.A6.3A$10.A.2A5.A5.3A2.A.A8.2A$11.3A2.A.A
6.3A$2.A8.3A11.3A$.3A7.3A11.2A$.A.2A6.2A$2.3A38.A$2.2A38.3A$41.2A.A$
41.3A$42.2A$10.3A$9.A2.A$12.A$12.A$9.A.A!
[[ STOP 213 ]](Drat, another item for the Life Lexicon to-do list...!)
Re: Thread for basic questions
Posted: April 10th, 2016, 12:09 pm
Theoretically, sure! Searching is easy (to paraphrase a line from _Hamilton_) -- actually finding something is harder.gmc_nxtman wrote:Would it be possible to search for a small glider gun of period < 20 by searching for oscillators which emit gliders as "sparks"? As in, a small billiard-ish oscillator-like thing emitting gliders, akin to oscillators emitting large sparks.
A decade ago I tried setting up WinLifeSearch to find a p14 gun along those exact lines. At that time, the top reasonable period to search for such things was probably p8, or maybe p9 with very well-chosen constraints -- and of course you can't have a p9 glider gun.
Unfortunately each increment to the period adds at least a couple of orders of magnitude to the difficulty of the search, probably more but it depends on the size of the object you're looking for. An algorithm that's searching for, say, a p10 oscillator with a specific spark, will have to hunt through a search space that's probably 1000 times as large as the search space for a p9 oscillator with the same spark.
It's always possible that someone will trip over a solution in the first 0.000001% of a given search space... but the odds are pretty heavily against it. (And obviously I didn't find a p14 gun a decade ago.)
Why Does The Search Space Get So Big So Fast?
For the p10 vs. p9 case, there are most likely at least 10 unknown, unconstrained cell states in the new tenth phase of the oscillator. So the lifesrc algorithm has to try all of those possible states, and that's 2^10 = 1024 possibilities to try... multiplied by the already huge search space that lifesrc already has to look through for a p9 search (i.e., all the unknown, unconstrained cells in the other nine phases.)
So to get to p14, we might have a search space that's 1000x1000x1000x1000x1000 = a quadrillion times bigger than a similar search for a p9 object. Even ten years' worth of Moore's Law, and a distributed-search approach with thousands of computers involved, might not be enough to get through a search like that -- especially since a glider is a fairly big "spark", so a lot of unknown cells are necessarily involved.
Let's Try Pipsquirters Instead
To put this another way: look at the problem by analogy with pipsquirters. Noam Elkies found a p6 pipsquirter in 1997, and a p7 pipsquirter in 1999. Nobody really needs a p8 pipsquirter because we already have figure eights -- but a p9 pipsquirter would be nice. It might well be possible to find one of those with a multi-day search on modern computer hardware.
Pipsquirters have fairly minimal-size sparks, as these things go. It's a much smaller problem to find an oscillator with a domino spark, than an oscillator with a glider spark.
Now, lifesrc certainly isn't the last word in search technology! Probably there's some awesomely clever hashtable-based algorithm out there somewhere, that can work its way through a search space billions of times faster -- and then a true-period p14 gun might well be suddenly within reach. However...
If We Haven't Seen [X] Yet, We Probably Won't See A P14 Gun
Any algorithm that can find a true p14 gun, will probably be able to find lots of other interesting things very very easily. I'd say you can expect to see pipsquirters of periods 9, 10, 11, 12, 13, and 14, before a true p14 gun shows up.
Also, while we're on the subject, since "period < 20" was mentioned -- a true p19 gun (or oscillator) will still be a quintillion times more difficult to find than a p14 one... and the factor that I'm using (multiplication of search space size by 2^10 for each period increment) might be a serious underestimate for many searches.
Re: Thread for basic questions
Posted: April 18th, 2016, 7:29 am
Where is there a writeup of the symmetry codes (e.g. C1, D8_1, etc.) used in Catagolue?
Re: Thread for basic questions
Posted: April 18th, 2016, 7:57 am
Here are pictures and descriptions, and here's a list that I think is right but haven't double-checked. The list can also be dug out of apgsearch (Python) code -- I seem to recall the comments are reasonably detailed (though with occasional nerdy jokes).Rich Holmes wrote:Where is there a writeup of the symmetry codes (e.g. C1, D8_1, etc.) used in Catagolue?
Re: Thread for basic questions
Posted: April 21st, 2016, 9:13 am
For sawtooths, why can't you extend the idea of having a gun releasing fast ships interacting with slower ships (like copperheads) to those slower ships being arbitrarily slow manufactured ships, like gemini? As the target ships being slower brings the EF closer to 1, you could have a manufactured spaceship which can travel at any arbitrary speed desired, meaning an EF arbitrarily close to 1. Is there something wrong with that?
Re: Thread for basic questions
Posted: April 21st, 2016, 10:13 am
Nothing wrong with that at all. Even an unmodified Demonoid can reflect a glider --blah wrote:For sawtooths, why can't you extend the idea of having a gun releasing fast ships interacting with slower ships (like copperheads) to those slower ships being arbitrarily slow manufactured ships, like gemini? As the target ships being slower brings the EF closer to 1, you could have a manufactured spaceship which can travel at any arbitrary speed desired, meaning an EF arbitrarily close to 1. Is there something wrong with that?
Code: Select all
x = 338, y = 361, rule = B3/S23
270bo$270b2o$269bobo16$282bo$281bobo$281b2o5$262b2o$262b2o$266b2o$266b
o$264bobo$264b2o7b2o4b2o$273b2o4b2o8bo$279b2o7bobo$280b2o7b2o$243b2o
35b2o3b2o$243b2o34bo2bo2b2o7b2o$278bob2o11bobo3bo$267b2o3b2o4bob2o12bo
3bobo$266bobo3b4o3bo18b2o$266bo3bo2bo2bo$266b2o3bo4bo6b4o$271bo3bo7bo
3bo$270bo16bo$283b2obo$283bo$279bo2bo$279bo2bo$279bo2bo$279bo2bo$253b
2o25b2o$253b2o3$258b2o$258b2o3$266b2o$265bobo$265bo$264b2o2$282bo$281b
obo$281b2o3$274b2o19bo17b2o$274b2o7b2o11bo16b2o$283bo10b3o$281bobo$
281b2o$264b2o$264b2o20b2o24b2o$254b2o30b2o24b2o$255bo$255bobo$245bo10b
2o$245b3o20b3o$248bo18bo3bo$247b2o3b2o12bo5bob3o41b2o$252b2o12bo5bobo
2b2o39b2o$266bo5bo5bo$267bo3bo3bo2bo$268b3o5b2o$274bo$260b2o11b3o$251b
o7bobo11bo2bo48b2o$250bobo6bo15b2o48bobo$250bobo5b2o32b2o32bo$251bo19b
3o17bobo$271b3o18bo4$275b2o$256b2o17b2o39b2o$256b2o9b2o46bobo$268bo45b
obo$265b3o47bo$265bo2$266bo$265bobo47b2o$265bobo47bobo$263b3ob2o47bo$
262bo$263b3ob2o$265bob2o$313b2o22bo$275b2o16b2o18bobo19bobo$275b2o7b2o
7bobo18bo21b2o$261bo22bo9bo$260bobo19bobo$260bobo12b3o4b2o$261bo13bo$
276bo2$262b2o$262b2o37b2o$300bobo$301bo3$278bo$277bobo$268b2o7bobo$
268b2o8bo$279b3o$281bo8$281b2o$281b2o30$332b2o$332bobo$332bo188$3o$2bo
$bo!That's probably a little too huge and silly to be very interesting, though. Something similar could be set up with a Caterloopillar and *WSS salvos; it would still be huge, but at least the guns wouldn't have to start so far away from the spaceship.
Re: Thread for basic questions
Posted: April 21st, 2016, 10:53 pm
No.muzik wrote:Could a gun similar to this one exist in normal life?
Code: Select all
x = 22, y = 21, rule = B38/S23 4$4b3o$4bo3bo$3b2o3bo$2b2o5bo$2b2o2b2o2bo$8bobo$9bo!
Re: Thread for basic questions
Posted: April 22nd, 2016, 7:47 am
You don't know that.PHPBB12345 wrote: No.
Re: Thread for basic questions
Posted: May 3rd, 2016, 5:24 pm
So... In normal Life an agar cannot have an average density (over space and time) above 1/2, if I read correctly.
What about patterns that are aperiodic, be it in space, time, or both? Does this still hold?
Also: is there an equivalent to Penrose tilings for Life?
What about patterns that are aperiodic, be it in space, time, or both? Does this still hold?
Also: is there an equivalent to Penrose tilings for Life?
Re: Thread for basic questions
Posted: May 3rd, 2016, 7:22 pm
If that has been proven, I haven't heard about it or don't remember it (which is certainly possible). It's been proven for stable patterns, but only conjectured for agars. From the Life Lexicon:NotLiving wrote:So... In normal Life an agar cannot have an average density (over space and time) above 1/2, if I read correctly.
Life Lexicon wrote::density The density of a pattern is the limit of the proportion of live cells in a (2n+1)x(2n+1) square centred on a particular cell as n tends to infinity, when this limit exists. (Note that it does not make any difference what cell is chosen as the centre cell. Also note that if the pattern is finite then the density is zero.) There are other definitions of density, but this one will do here.
In 1994 Noam Elkies proved that the maximum density of a stable pattern is 1/2, which had been the conjectured value. See the paper listed in the bibliography. Marcus Moore provided a simpler proof in 1995, and in fact proves that a still life with an m x n bounding box has at most (mn+m+n)/2 cells.
But what is the maximum average density of an oscillating pattern? The answer is conjectured to be 1/2 again, but this remains unproved. The best upper bound so far obtained is 8/13 (Hartmut Holzwart, September 1992).
The maximum possible density for a phase of an oscillating pattern is also unknown. An example with a density of 3/4 is known (see agar), but densities arbitrarily close to 1 may perhaps be possible.
... I think that infinite aperiodic patterns are among the difficult cases that make it hard to prove the 1/2 agar density limit definitively.NotLiving wrote:What about patterns that are aperiodic, be it in space, time, or both? Does this still hold?
Hmm. Probably. Seems like you could take Karel Culik's thirteen aperiodic Wang tiles, for example, and choose some appropriate square tile size in Conway's Life. Create inductor edges for each Wang-tile color that will be stable if the opposing tile matches, but will otherwise collapse. An infinite stable pattern made out of tiles like that would necessarily be aperiodic -- any periodic pattern would eventually become chaotic, and then random ash.NotLiving wrote:Also: is there an equivalent to Penrose tilings for Life?
That's kind of an artificial aperiodicity, I suppose, but I can't think of anything more "natural" for B3/S23.
Re: Thread for basic questions
Posted: May 3rd, 2016, 9:33 pm
Do we know that bounded-periodic oscillatory patterns have an upper-bound 1/2 density limit on average, at least? Seems easier to prove than the aperiodic case. Although still way above my pay grade.
Also I'm interested by the aperiodic tiling suggestion. If I'm reading correctly, basically set up each tile such that it self-destructs (or at least doesn't return to its original state after a bounded number of steps) unless the corresponding edges match?
Oh.
Hmm.
Seems simple in retrospect, actually.
Each tile edge is composed of the presence or absence of 2 tables or absence thereof - use a binary encoding for the colors. So each tile is 14 x 14 - 15x15 once you include the gap between adjacent tiles. Use this set of Wang tiles.
It'll end up turning to ash unless every table is matched with a table (and every lack-of-table is matched with a lack-of-table).
Should be an aperiodic tiling, assuming you restrict oneself to only those 11 tiles.
Also I'm interested by the aperiodic tiling suggestion. If I'm reading correctly, basically set up each tile such that it self-destructs (or at least doesn't return to its original state after a bounded number of steps) unless the corresponding edges match?
Oh.
Hmm.
Seems simple in retrospect, actually.
Each tile edge is composed of the presence or absence of 2 tables or absence thereof - use a binary encoding for the colors. So each tile is 14 x 14 - 15x15 once you include the gap between adjacent tiles. Use this set of Wang tiles.
It'll end up turning to ash unless every table is matched with a table (and every lack-of-table is matched with a lack-of-table).
Should be an aperiodic tiling, assuming you restrict oneself to only those 11 tiles.
Re: Thread for basic questions
Posted: May 3rd, 2016, 11:32 pm
Hasn't been proven yet, as far as I can recall. I think everyone suspects that 1/2 is in fact the highest possible average density, but that doesn't mean it's easy to come up with a bulletproof proof.NotLiving wrote:Do we know that bounded-periodic oscillatory patterns have an upper-bound 1/2 density limit on average, at least? Seems easier to prove than the aperiodic case. Although still way above my pay grade.
Ah, there's an 11-tile four-color aperiodic set, and they've proved that 10-tile sets and three-color sets aren't enough! My information was out of date, and for some reason that 2015 tile set didn't show up in my searches. Somebody should update the Wikipedia article.NotLiving wrote:Each tile edge is composed of the presence or absence of 2 tables or absence thereof - use a binary encoding for the colors. So each tile is 14 x 14 - 15x15 once you include the gap between adjacent tiles. Use this set of Wang tiles.
The tiles you're describing would be 14x14, though of course they could be made bigger -- the boundary gap only needs to be included on two sides:
Code: Select all
x = 47, y = 47, rule = LifeHistory
5.C2.C.C2.C5.C2.C.C2.C5.C2.C.C2.C$5.4C.4C5.4C.4C5.4C.4C2$5.4A.4A5.4A.
4A5.4A.4A$5.A2.A.A2.A5.A2.A.A2.A5.A2.A.A2.A$2C.2A9.2A.2A9.2A.2A9.2A.
2C$.C.A11.A.A11.A.A11.A.C$.C.A11.A.A11.A.A11.A.C$2C.2A9.2A.2A9.2A.2A
9.2A.2C2$2C.2A9.2A.2A9.2A.2A9.2A.2C$.C.A11.A.A11.A.A11.A.C$.C.A11.A.A
11.A.A11.A.C$2C.2A9.2A.2A9.2A.2A9.2A.2C$5.A2.A.A2.A5.A2.A.A2.A5.A2.A.
A2.A$5.4A.4A5.4A.4A5.4A.4A2$5.4A.4A3.2B4AB4A3B2.4A.4A$5.A2.A.A2.A3.2B
A2BABA2BA3B2.A2.A.A2.A$2C.2A9.2A.2A9B2AB2A9.2A.2C$.C.A11.A.A11BABA11.
A.C$.C.A11.A.A11BABA11.A.C$2C.2A9.2A.2A9B2AB2A9.2A.2C$17.14B$2C.2A9.
2A.2A9B2AB2A9.2A.2C$.C.A11.A.A11BABA11.A.C$.C.A11.A.A11BABA11.A.C$2C.
2A9.2A.2A9B2AB2A9.2A.2C$5.A2.A.A2.A3.2BA2BABA2BA3B2.A2.A.A2.A$5.4A.4A
3.2B4AB4A3B2.4A.4A$17.14B$5.4A.4A5.4A.4A5.4A.4A$5.A2.A.A2.A5.A2.A.A2.
A5.A2.A.A2.A$2C.2A9.2A.2A9.2A.2A9.2A.2C$.C.A11.A.A11.A.A11.A.C$.C.A
11.A.A11.A.A11.A.C$2C.2A9.2A.2A9.2A.2A9.2A.2C2$2C.2A9.2A.2A9.2A.2A9.
2A.2C$.C.A11.A.A11.A.A11.A.C$.C.A11.A.A11.A.A11.A.C$2C.2A9.2A.2A9.2A.
2A9.2A.2C$5.A2.A.A2.A5.A2.A.A2.A5.A2.A.A2.A$5.4A.4A5.4A.4A5.4A.4A2$5.
4C.4C5.4C.4C5.4C.4C$5.C2.C.C2.C5.C2.C.C2.C5.C2.C.C2.C!Code: Select all
x = 13, y = 13, rule = LifeHistory
2.4D.4D$2.D2.D.D2.D$2D9.2D$D11.D$D3.2E.2E3.D$2D2.2E.2E2.2D2$2D2.2E.2E
2.2A$D3.2E.2E3.A$D11.A$2D9.2A$2.D2.D.D2.D$2.4D.4D!EDIT: Ah, no, I should have thought more carefully about the fact that you're not allowed to rotate or reflect Wang tiles. So a "color" doesn't have to consist of the same structure on both sides -- it just has to be any induction coil that doesn't successfully stabilize against any of the others.
In fact, they don't even have to be induction coils -- a structure that bridges two tiles would be fine, as long as it didn't stabilize against any of the other three "colors". Seems like that should allow a ridiculously small set of tiles to be designed -- less than 8x8, certainly. I wouldn't be surprised if 6x6 or even 5x5 turned out to be possible.
- 11_4color_Wang_tiles.png (28.06 KiB) Viewed 25221 times
Re: Thread for basic questions
Posted: May 4th, 2016, 1:01 pm
Ah ok. As I said, it's certainly above my pay grade.dvgrn wrote:Hasn't been proven yet, as far as I can recall. I think everyone suspects that 1/2 is in fact the highest possible average density, but that doesn't mean it's easy to come up with a bulletproof proof.NotLiving wrote:Do we know that bounded-periodic oscillatory patterns have an upper-bound 1/2 density limit on average, at least? Seems easier to prove than the aperiodic case. Although still way above my pay grade.
Yep. I'm not sure why it doesn't appear much of anywhere.dvgrn wrote:Ah, there's an 11-tile four-color aperiodic set, and they've proved that 10-tile sets and three-color sets aren't enough! My information was out of date, and for some reason that 2015 tile set didn't show up in my searches. Somebody should update the Wikipedia article.NotLiving wrote:Each tile edge is composed of the presence or absence of 2 tables or absence thereof - use a binary encoding for the colors. So each tile is 14 x 14 - 15x15 once you include the gap between adjacent tiles. Use this set of Wang tiles.
Smaller, you mean?dvgrn wrote: The tiles you're describing would be 14x14, though of course they could be made bigger
Ah, so there is some room for it to be made smaller. (Also: what are you using to create said images?)dvgrn wrote: <interesting 14x14 tiling cell>
I was thinking of this, actually, (or rather, I missed that you could have only 1 gap between tables) which has the downside that every second tile has to be mirrored (and as such you need to be careful to ensure that the tile encoding does not allow spurious connections - specifically a 01 will match with an unmirrored 10)
Code: Select all
#CXRLE Pos=-14,-14 Gen=11
x = 27, y = 27, rule = B3/S23:T28,28
4ob4o2b2ob2o2b4ob4o$o2bobo2bo3bobo3bo2bobo2bo$12bobo$11b2ob2o$2o23b2o$
o10b2ob2o10bo$o11bobo11bo$2o10bobo10b2o$11b2ob2o$2o23b2o$o25bo$o3bo2bo
bo2bobo2bobo2bo3bo$2o2b4ob4ob4ob4o2b2o2$2o2b4ob4ob4ob4o2b2o$o3bo2bobo
2bobo2bobo2bo3bo$o25bo$2o23b2o$11b2ob2o$2o10bobo10b2o$o11bobo11bo$o10b
2ob2o10bo$2o23b2o$11b2ob2o$12bobo$o2bobo2bo3bobo3bo2bobo2bo$4ob4o2b2ob
2o2b4ob4o!Interesting, although not strictly necessary, I don't think - generally "stable" is taken as "returning to original state after a bounded number of generations", yes?dvgrn wrote: It might be a good idea to add some extra decoration, like four blocks, in the middle of the tile. That way even if there's a tile that is made up of mostly the no-tables color, and there's just one unpaired table, the tile will still reliably cause some interesting chaos. A table by itself with enough empty space around it just collapses into vacuum, so you'd end up with a stable pattern again immediately
I've tossed a PBSAT solver at it. I shall see what happens.dvgrn wrote: However, it might be possible to come up with tiles smaller than 14x14, by mixing tables with other lengths of induction coil (?) I suppose the ON cells would have to be either mirror-symmetric or would have to be stable even without an exact match between induction coils. Would have to be careful that none of the combinations with other "colors" is also stable -- a length-2 offset wouldn't be good, unless it was two copies of the same color.
(Actually two encodings: one that enforces a 2x2 blank at each corner that's substantially faster, and one that does not but is substantially slower. The corner tiles as far as I can tell require 11^4 clauses to cover - "yay?". Any suggestions for how to deal with them in a sane manner?)
Re: Thread for basic questions
Posted: May 4th, 2016, 2:31 pm
Was trying to say that you _could_ have the 15x15 tiles that you suggested, perfectly well, by putting two spaces in the center of each edge instead of one. But 14x14 was all that was needed.NotLiving wrote:Smaller, you mean?dvgrn wrote: The tiles you're describing would be 14x14, though of course they could be made bigger
If I understand the question correctly -- just drawing and copy/pasting in Golly, using the LifeHistory rule.NotLiving wrote:Ah, so there is some room for it to be made smaller. (Also: what are you using to create said images?)
It seems better to stay away from this idea, then, since if there are rules about when to use mirror images (or rotations) then the tiles are no longer really Wang tiles.NotLiving wrote:I was thinking of this, actually... which has the downside that every second tile has to be mirrored...
What size tiles are you asking the PBSAT solver about? Seems as if a little experimentation could probably put a reasonable upper bound on the problem. We just need four different "colors", so four stable patterns that cross the boundary of an NxN tile, not necessarily symmetric but that might be simpler to deal with. The only criterion is that if each color-A half pattern is matched with a color-B other-half-pattern, for A!=B, then the combination must _not_ be stable.NotLiving wrote:I've tossed a PBSAT solver at it. I shall see what happens.
(Actually two encodings: one that enforces a 2x2 blank at each corner that's substantially faster, and one that does not but is substantially slower. The corner tiles as far as I can tell require 11^4 clauses to cover - "yay?". Any suggestions for how to deal with them in a sane manner?)
I think that's technically doable with 8x8 tiles, as long as we can count blinkers as "P2 stable" -- i.e., your test is to run the pattern for two ticks, not just one, and then if anything is different then you must have mismatched a tile:
Code: Select all
x = 15, y = 37, rule = LifeHistory
7B.7B$7B.7B$7BAC6B$7BAC6B$7B.7B$7B.7B$7B.7B4$7B.7B$7B.7B$7B.7B$7BAC6B
$7BAC6B$7B.7B$7B.7B4$7B.7B$7B.7B$7B.7B$6B2AC6B$7B.7B$7B.7B$7B.7B4$7B.
7B$7B.7B$7BA7B$7BA7B$7BA7B$7B.7B$7B.7B!It's quite possible that there's some delicately balanced set of 8x8 or smaller P1 stable tiles, with a lot more ON cells: the center would have to be customized for each of the 11 tiles so that it's internally stable. It's not necessary to solve for all possible combinations of colors, just for the particular eleven combinations in the T' set.
EDIT: To be more specific, I think the following is a set of 8x8 aperiodic Wang tiles for Conway's Life. That is, there are no periodic ways of tiling the infinite plane with these things, in such a way that the T=2 configuration is everywhere identical to the T=0 configuration:
Code: Select all
x = 108, y = 28, rule = LifeHistory
3B2A3B12.3BA4B12.3B2A3B12.2B2A4B12.3BA4B$8B12.3BA4B12.8B12.8B12.3BA4B
$8B12.8B12.7BA12.8B12.8B$7BA12.7BA12.7BA12.A5B2A12.A5B2A$7BA12.7BA12.
7BA12.8B12.8B$8B12.8B12.8B12.8B12.8B$8B12.8B12.8B12.8B12.8B$3B2A3B12.
3BA4B12.8B12.3B2A3B12.2B2A4B13$2B2A4B12.3B2A3B12.3BA4B12.3BA4B12.3B3A
2B12.3B3A2B$8B12.8B12.3BA4B12.3BA4B12.8B12.8B$A6BA12.A6BA12.7BA12.8B
12.7BA12.7BA$A6BA12.A6BA12.A6BA12.A6BA12.A6BA12.7BA$8B12.7BA12.A7B12.
A6BA12.A6BA12.7BA$8B12.8B12.8B12.8B12.8B12.8B$8B12.8B12.8B12.8B12.8B
12.8B$3B2A3B12.3BA4B12.3BA4B12.2B2A4B12.3BA4B12.8B!Code: Select all
x = 191, y = 41, rule = LifeHistory
35.2C$7B.7B18.2B2A4B45.2C18.C19.2C17.2C19.C$7B.7B5.2E11.8B42.3B2A3B
12.3BA4B12.3B2A3B12.2B2A4B12.3BA4B$7BAC6B4.E2.E9.AC6BAC41.8B12.3BA4B
12.8B12.8B12.3BA4B$7BAC6B4.E2.E9.AC6BAC40.A8B11.A8B11.A7BA12.8B12.8B$
7B.7B4.E2.E10.8B41.A7BAC10.A7BAC10.A7BA10.2AC5B2AC9.2AC5B2AC$7B.7B4.E
2.E10.8B41.A7BAC10.A7BAC10.A7BA12.8B12.8B$7B.7B5.2E11.8B42.8B12.8B12.
8B12.8B12.8B$33.2B2C4B42.8B12.8B12.8B12.8B12.8B$35.2A9.2C35.3B2C3B12.
3BC4B12.8B12.3B2C3B12.2B2C4B$43.3B2A3B35.2A18.A19.3A17.2A17.2A$7B.7B
5.E22.8B55.A$7B.7B5.E22.8B$7B.7B5.E21.AC6BAC$7BAC6B5.E21.AC6BAC$7BAC
6B5.E22.8B$7B.7B5.E22.8B$7B.7B5.E22.3B2C3B$46.2A2$36.C$7B.7B3.3E12.3B
A4B44.2C19.2C18.C19.C$7B.7B6.E11.3BA4B42.2B2A4B12.3B2A3B12.3BA4B12.3B
A4B12.3B3A2B12.3B3A2B$7B.7B6.E11.8B42.8B12.8B12.3BA4B12.3BA4B12.8B12.
8B$6B2AC6B5.E10.2AC5B2AC40.AC6BAC10.AC6BA12.7BAC11.8B12.7BA11.A7BA$7B
.7B4.E13.8B41.AC6BAC10.AC6BA11.AC6BAC10.AC6BAC10.AC6BA11.A7BA$7B.7B3.
E14.8B42.8B12.7BA11.AC7B11.AC6BAC10.AC6BA11.A7BA$7B.7B3.4E11.8B42.8B
12.8B12.8B12.8B12.8B12.8B$33.3BC4B42.8B12.8B12.8B12.8B12.8B12.8B$36.A
46.3B2C3B12.3BC4B12.3BC4B12.2B2C4B12.3BC4B12.8B$36.A49.2A18.A19.A18.
2A19.A19.3A$7B.7B3.3E85.A19.A39.A$7B.7B6.E21.3B3A2B$7BA7B6.E21.8B$7BA
7B3.3E21.A7BA$7BA7B6.E20.A7BA$7B.7B6.E20.A7BA$7B.7B3.3E22.8B$43.8B$
43.8B$46.3A!Re: Thread for basic questions
Posted: May 4th, 2016, 5:37 pm
First, thank you again. This is rather interesting.
With the restriction that the 16 corner cells are blank and everything is still life, I have an 8x8 set of tiles, and 7x7 or smaller is not allowed (assuming my code was correct):
This is really hard to visually see as 8x8 cells.
This is a 4x4 grid of 8x8 tiles containing all 11 tiles, with one mismatch (the tiles being aperiodic, you'll always end up with a mismatch on any bounded period, by definition).
The tile indexes are as follows:
Here is how the tiles fit together in this grid:
You can see the lone mismatch at the wrap on the bottom edge, on the right.
I like how zero up/down ended up being blank. Not forced, just how it came out.
Zero-indexed, obviously, but otherwise corresponding to the set in the paper.
I haven't exhaustively tested all possible combinations, but it looks good at first glance at least.
If tiles do not match with wrong colors of the mirrored copy, you can effectively treat the set of {tiles + mirrored tiles} as an aperiodic set of Wang tiles, and you don't need the rules about the mirror images (as it's already covered by the standard "must be stable" rule).
8x8 is 58872 clauses.
The still-life one with corner cells? Runs out of RAM and crashes even with 4x4 tiles :/
Clarification: if a color-A half-pattern is matched with any color B other-half-pattern, it should be stable if and only if A == B. As-stated, you could fulfill that criteria by building a bunch of tiles that were never stable.
Two edge cases:
One is that not all color-A half-patterns must be identical - and indeed in my example above it is not the case (look at the bottoms of patterns 9 and 1,for instance.). All that is required is that they match when the "colors" match and not otherwise. Which means that I cannot simply loop over all possible adjacent colors; it needs to be all tiles :/
Two, there's the problem of the corner cells of each tile. The corner cells are potentially affected by 3 other tiles, not just 1. Which means that the problem turns from the simple "for all other tiles, for all cardinal directions, none of the cells of the edge strip (read: border cells of this tile in the direction of the other tile and vice versa) should change if and only if the tiles should match" to something much harder. Something along the lines of "for all sets of 8 tiles surrounding this tile, none of the edges of this tile or the next cell out should change if and only if the tiles should match this one" would work - but then you're talking about 11^9 constraints!
Right now I'm just punting the problem by enforcing that the corner and adjacent-to-corner cells remain blank. This means that the corner cell will always remain dead at the start regardless, and hence will never change unless some other cell has already changed somewhere else.
Edit: just saw that edit. Now attempting to minimize the number of live cells - it'll serve as a sanity check at the very least (if it gets a worse solution than yours, I have a problem).
Also going to run a run maximizing the number of live cells - should get something closer to that weird still life and interesting cascades I am hoping for.
With the restriction that the 16 corner cells are blank and everything is still life, I have an 8x8 set of tiles, and 7x7 or smaller is not allowed (assuming my code was correct):
Code: Select all
x = 32, y = 32, rule = B3/S23:T32,32
3.2A6.2A5.2A.A5.2A3.$32.$.A7.A8.2A.A10.$A.A5.A.A6.A.A.3A4.2A2.$.A3.2A2.A3.2A.A2.A4.A2.A2.A.$A3.A2.2A3.A2.2A.A2.3A3.2A2.A$4.2A6.2A4.2A.A10.$18.A2.A5.2A3.$19.2A6.2A3.$4.2A6.2A18.$A3.A2.2A3.A2.2A6.2A6.A$A4.2A.A4.2A2.A5.A.A5.A$16.2A6.2A6.$18.2A.A4.2A.A2.$2.A7.A7.A.2A4.A.2A2.$2.3A5.3A19.$5.A7.A18.$2.4A6.A5.2A6.2A4.$.A10.4A.A.A2.2A.A.A2.2A$.2A2.3A7.A.A.A.A.A.A.A.A.A$2.A2.A2.A3.2A.A.A.2A2.A.A.2A2.A$A5.2A3.A.A.2A.A4.2A.A4.A$10.A7.A7.A5.$3.2A5.3A5.3A5.3A3.$3.2A8.A7.A7.A2.$10.4A6.2A6.2A2.$6.2A.A22.$.A3.A.A.2A2.3A4.4A4.2A2.$A.A.A2.A2.A2.A2.A2.A4.A3.A.A.$A.A.2A.2A5.2A3.5A7.A$2.A2.A20.A5.$2.A2.A5.2A5.A.2A4.3A3.!This is a 4x4 grid of 8x8 tiles containing all 11 tiles, with one mismatch (the tiles being aperiodic, you'll always end up with a mismatch on any bounded period, by definition).
The tile indexes are as follows:
Code: Select all
8 8 9 1
3 3 4 4
6 10 5 5
7 6 2 0
Code: Select all
+---+---+---+---+
| 2 | 2 | 3 | 2 |
|181|181|193|311|
| 0 | 0 | 2 | 2 |
+---+---+---+---+
| 0 | 0 | 2 | 2 |
|232|232|242|242|
| 1 | 1 | 0 | 0 |
+---+---+---+---+
| 1 | 1 | 0 | 0 |
|063|3a0|050|050|
| 2 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 1 | 1 | 1 |
|170|063|323|301|
| 2 | 2 | 3 | 1 |
+---+---+---+---+
I like how zero up/down ended up being blank. Not forced, just how it came out.
Zero-indexed, obviously, but otherwise corresponding to the set in the paper.
I haven't exhaustively tested all possible combinations, but it looks good at first glance at least.
It depends.dvgrn wrote: It seems better to stay away from this idea, then, since if there are rules about when to use mirror images (or rotations) then the tiles are no longer really Wang tiles.
If tiles do not match with wrong colors of the mirrored copy, you can effectively treat the set of {tiles + mirrored tiles} as an aperiodic set of Wang tiles, and you don't need the rules about the mirror images (as it's already covered by the standard "must be stable" rule).
The still-life no-corner-cells one? 5x5+ - I know it works (well, I know it runs and seems to give sane results. Not quite the same thing) up to at least 10x10 tiles, and probably works above that assuming you have the memory / time. Biggest problem is the n^2 number of constraints - but finding a solution gets easier as the problem size increases. 8x8 takes around 30 minutes to run using minisat+.dvgrn wrote: What size tiles are you asking the PBSAT solver about?
8x8 is 58872 clauses.
The still-life one with corner cells? Runs out of RAM and crashes even with 4x4 tiles :/
A clarification and the edge cases that I'm having trouble with.dvgrn wrote:The only criterion is that if each color-A half pattern is matched with a color-B other-half-pattern, for A!=B, then the combination must _not_ be stable.
Clarification: if a color-A half-pattern is matched with any color B other-half-pattern, it should be stable if and only if A == B. As-stated, you could fulfill that criteria by building a bunch of tiles that were never stable.
Two edge cases:
One is that not all color-A half-patterns must be identical - and indeed in my example above it is not the case (look at the bottoms of patterns 9 and 1,for instance.). All that is required is that they match when the "colors" match and not otherwise. Which means that I cannot simply loop over all possible adjacent colors; it needs to be all tiles :/
Two, there's the problem of the corner cells of each tile. The corner cells are potentially affected by 3 other tiles, not just 1. Which means that the problem turns from the simple "for all other tiles, for all cardinal directions, none of the cells of the edge strip (read: border cells of this tile in the direction of the other tile and vice versa) should change if and only if the tiles should match" to something much harder. Something along the lines of "for all sets of 8 tiles surrounding this tile, none of the edges of this tile or the next cell out should change if and only if the tiles should match this one" would work - but then you're talking about 11^9 constraints!
Right now I'm just punting the problem by enforcing that the corner and adjacent-to-corner cells remain blank. This means that the corner cell will always remain dead at the start regardless, and hence will never change unless some other cell has already changed somewhere else.
Simple problem first, then oscillatory ones... Though as you say, it's relatively easy to extend to do. Though potentially harder to actually solve.dvgrn wrote: I think that's technically doable with 8x8 tiles, as long as we can count blinkers as "P2 stable" -- i.e., your test is to run the pattern for two ticks, not just one, and then if anything is different then you must have mismatched a tile
Hence why I'm punting it to a SAT solver. I am no good at this sort of thing myself.dvgrn wrote: If P1 stable tiles are a requirement, then the initial upper bound seems to be 9x9, to be able to fit independent copies of four stable "color" objects at each of the four edges, without them interfering with each other.
It's quite possible that there's some delicately balanced set of 8x8 or smaller P1 stable tiles, with a lot more ON cells: the center would have to be customized for each of the 11 tiles so that it's internally stable.
Edit: just saw that edit. Now attempting to minimize the number of live cells - it'll serve as a sanity check at the very least (if it gets a worse solution than yours, I have a problem).
Also going to run a run maximizing the number of live cells - should get something closer to that weird still life and interesting cascades I am hoping for.
Re: Thread for basic questions
Posted: May 4th, 2016, 7:13 pm
Here's a LifeHistory way to make the boundaries a little clearer. Makes it easier to recognize the repeating tiles, at least:NotLiving wrote:With the restriction that the 16 corner cells are blank and everything is still life, I have an 8x8 set of tiles, and 7x7 or smaller is not allowed (assuming my code was correct...
This is really hard to visually see as 8x8 cells.
Code: Select all
x = 64, y = 64, rule = LifeHistory
3D2C3D3.2A3.2D2CDC2D3.2A3.3D2C3D3.2A3.2D2CDC2D3.2A$8D8.8D8.8D8.8D$DC
6D.A6.2D2CDC2D8.DC6D.A6.2D2CDC2D$CDC5DA.A5.DCDCD3C4.2A2.CDC5DA.A5.DCD
CD3C4.2A$DC3D2CD.A3.2A.C2DC4DA2.A2.A.DC3D2CD.A3.2A.C2DC4DA2.A2.A$C3DC
2DCA3.A2.ACDC2D3C3.2A2.AC3DC2DCA3.A2.ACDC2D3C3.2A2.A$4D2C2D4.2A2.2D2C
DC2D8.4D2C2D4.2A2.2D2CDC2D$8D8.2DC2DC2D3.2A3.8D8.2DC2DC2D3.2A$8.8D3.
2A3.3D2C3D8.8D3.2A3.3D2C3D$4.2A2.4D2C2D8.8D4.2A2.4D2C2D8.8D$A3.A2.AC
3DC2DCA6.AC6DCA3.A2.AC3DC2DCA6.AC6DC$A4.2A.C4D2CD.A5.ADC5DCA4.2A.C4D
2CD.A5.ADC5DC$8.8D2A6.2C6D8.8D2A6.2C6D$8.8D2.2A.A2.2D2CDC2D8.8D2.2A.A
2.2D2CDC2D$2.A5.2DC5D2.A.2A2.2DCD2C2D2.A5.2DC5D2.A.2A2.2DCD2C2D$2.3A
3.2D3C3D8.8D2.3A3.2D3C3D8.8D$5DC2D5.A2.8D8.5DC2D5.A2.8D$2D4C2D4.A3.2D
2C4D2.2A4.2D4C2D4.A3.2D2C4D2.2A$DC6D4.4ADCDC2D2C.A.A2.2ADC6D4.4ADCDC
2D2C.A.A2.2A$D2C2D3C7.ADCDCDCDC.A.A.A.AD2C2D3C7.ADCDCDCDC.A.A.A.A$2DC
2DC2DA3.2A.ADCD2C2DC.A.2A2.A2DC2DC2DA3.2A.ADCD2C2DC.A.2A2.A$C5D2C3.A.
A.ACDC4DCA.A4.AC5D2C3.A.A.ACDC4DCA.A4.A$8D2.A5.2DC5D2.A5.8D2.A5.2DC5D
2.A$3D2C3D2.3A3.2D3C3D2.3A3.3D2C3D2.3A3.2D3C3D2.3A$3.2A3.5DC2D5.A2.5D
C2D3.2A3.5DC2D5.A2.5DC2D$8.2D4C2D4.2A2.4D2C2D8.2D4C2D4.2A2.4D2C2D$6.
2ADC6D8.8D6.2ADC6D8.8D$.A3.A.AD2C2D3C4.4A4D2C2D.A3.A.AD2C2D3C4.4A4D2C
2D$A.A.A2.A2DC2DC2DA2.A4.A3DCDCDA.A.A2.A2DC2DC2DA2.A4.A3DCDCD$A.A.2A.
2A5D2C3.5A7DCA.A.2A.2A5D2C3.5A7DC$2.A2.A2.8D8.2DE5D2.A2.A2.8D8.2DE5D$
2.A2.A2.3D2C3D2.A.2A2.2D3E3D2.A2.A2.3D2C3D2.A.2A2.2D3E3D$3D2C3D3.2A3.
2D2CDC2D3.2E3.3D2C3D3.2A3.2D2CDC2D3.2E$8D8.8D8.8D8.8D$DC6D.A6.2D2CDC
2D8.DC6D.A6.2D2CDC2D$CDC5DA.A5.DCDCD3C4.2A2.CDC5DA.A5.DCDCD3C4.2A$DC
3D2CD.A3.2A.C2DC4DA2.A2.A.DC3D2CD.A3.2A.C2DC4DA2.A2.A$C3DC2DCA3.A2.AC
DC2D3C3.2A2.AC3DC2DCA3.A2.ACDC2D3C3.2A2.A$4D2C2D4.2A2.2D2CDC2D8.4D2C
2D4.2A2.2D2CDC2D$8D8.2DC2DC2D3.2A3.8D8.2DC2DC2D3.2A$8.8D3.2A3.3D2C3D
8.8D3.2A3.3D2C3D$4.2A2.4D2C2D8.8D4.2A2.4D2C2D8.8D$A3.A2.AC3DC2DCA6.AC
6DCA3.A2.AC3DC2DCA6.AC6DC$A4.2A.C4D2CD.A5.ADC5DCA4.2A.C4D2CD.A5.ADC5D
C$8.8D2A6.2C6D8.8D2A6.2C6D$8.8D2.2A.A2.2D2CDC2D8.8D2.2A.A2.2D2CDC2D$
2.A5.2DC5D2.A.2A2.2DCD2C2D2.A5.2DC5D2.A.2A2.2DCD2C2D$2.3A3.2D3C3D8.8D
2.3A3.2D3C3D8.8D$5DC2D5.A2.8D8.5DC2D5.A2.8D$2D4C2D4.A3.2D2C4D2.2A4.2D
4C2D4.A3.2D2C4D2.2A$DC6D4.4ADCDC2D2C.A.A2.2ADC6D4.4ADCDC2D2C.A.A2.2A$
D2C2D3C7.ADCDCDCDC.A.A.A.AD2C2D3C7.ADCDCDCDC.A.A.A.A$2DC2DC2DA3.2A.AD
CD2C2DC.A.2A2.A2DC2DC2DA3.2A.ADCD2C2DC.A.2A2.A$C5D2C3.A.A.ACDC4DCA.A
4.AC5D2C3.A.A.ACDC4DCA.A4.A$8D2.A5.2DC5D2.A5.8D2.A5.2DC5D2.A$3D2C3D2.
3A3.2D3C3D2.3A3.3D2C3D2.3A3.2D3C3D2.3A$3.2A3.5DC2D5.A2.5DC2D3.2A3.5DC
2D5.A2.5DC2D$8.2D4C2D4.2A2.4D2C2D8.2D4C2D4.2A2.4D2C2D$6.2ADC6D8.8D6.
2ADC6D8.8D$.A3.A.AD2C2D3C4.4A4D2C2D.A3.A.AD2C2D3C4.4A4D2C2D$A.A.A2.A
2DC2DC2DA2.A4.A3DCDCDA.A.A2.A2DC2DC2DA2.A4.A3DCDCD$A.A.2A.2A5D2C3.5A
7DCA.A.2A.2A5D2C3.5A7DC$2.A2.A2.8D8.2DC5D2.A2.A2.8D8.2DC5D$2.A2.A2.3D
2C3D2.A.2A2.2D3C3D2.A2.A2.3D2C3D2.A.2A2.2D3C3D!Your solution looks much more interesting than mine, already! I'm really happy to see someone with expertise with SAT solvers applying them successfully to Life problems. Am curious to see if you can really handle the P2 case so easily -- seems like there might be a smaller tile that's all blinkers, or all P2 anyway, but I ran into ugly conflicts when I tried to lay it out manually.NotLiving wrote:Hence why I'm punting it to a SAT solver. I am no good at this sort of thing myself.dvgrn wrote:It's quite possible that there's some delicately balanced set of 8x8 or smaller P1 stable tiles, with a lot more ON cells: the center would have to be customized for each of the 11 tiles so that it's internally stable.
Edit: just saw that edit. Now attempting to minimize the number of live cells - it'll serve as a sanity check at the very least (if it gets a worse solution than yours, I have a problem).
Also going to run a run maximizing the number of live cells - should get something closer to that weird still life and interesting cascades I am hoping for.
I strongly suspect that SAT solvers could break a lot of new ground in these kinds of CA puzzles, as they have already for small Gardens of Eden.
For example, one really simple way to solve the Conway's Life omniperiodicity problem would be to find a 2c/3 signal elbow, or alternatively a 2c/3 double-signal to single-signal converter (since we already have an elbow).
It seems as if it should be possible to set up a SAT solver to hunt for one of these 2c/3 converter patterns, as long as the area of the reaction is small enough and the reaction settles quickly enough.
Maybe Dean Hickerson's 'drifter' program has already covered the ground efficiently enough, and there's no solution out there in the reachable search space -- but SAT solvers look like an interesting new angle to try, anyway.
I'd try it myself... but I'm in need of a very basic tutorial on SAT solvers first -- e.g., where can I download one that will work well, and how do I set up constraints efficiently for a large CA grid?
Re: Thread for basic questions
Posted: May 4th, 2016, 8:40 pm
Let's move that aspect to a new thread about SAT solvers, then?
I'll make one.
I'll make one.
Re: Thread for basic questions
Posted: May 6th, 2016, 12:36 pm
Is there an upper bound to the size of the bounding-box of the minimum-sized-bounding-box-period-N-oscillator?
Re: Thread for basic questions
Posted: May 6th, 2016, 2:35 pm
There are 2^x states possible in a bounding box of size x, so an absolute limit is log_2(N), taking N = x. Considering symmetry, this becomes log_2(N)+1, due to the fact that a pattern cannot become all 8 of its orientations in a square box or all 4 in a rectangular box. Beyond this, I don't know of any other limit, but there may be proofs that I haven't heard of.NotLiving wrote:Is there an upper bound to the size of the bounding-box of the minimum-sized-bounding-box-period-N-oscillator?
Another interesting question related to this might be what the highest finite period attainable by a pattern with a predecessor fitting in a certain-size bounding box.
Re: Thread for basic questions
Posted: May 6th, 2016, 2:38 pm
If you want "bounding box" to denote the minimum bounding box among all phases, then I think this argument by dvgrn claims there is no scaling with N once the bounding box can contain a universal constructor.
If "bounding box" instead enforces the oscillator to stay within a bounding box of area A, then the maximum period is 2^A, because there are only 2^A distinct patterns within that box and they each have a unique offspring.
If "bounding box" instead enforces the oscillator to stay within a bounding box of area A, then the maximum period is 2^A, because there are only 2^A distinct patterns within that box and they each have a unique offspring.
Re: Thread for basic questions
Posted: May 6th, 2016, 3:15 pm
That looks more like a lower bound on bounding-box size, though. If you're looking for a practical upper bound, here's a start:A for awesome wrote:There are 2^x states possible in a bounding box of size x, so an absolute limit is log_2(N), taking N = x. Considering symmetry, this becomes log_2(N)+1, due to the fact that a pattern cannot become all 8 of its orientations in a square box or all 4 in a rectangular box. Beyond this, I don't know of any other limit, but there may be proofs that I haven't heard of.NotLiving wrote:Is there an upper bound to the size of the bounding-box of the minimum-sized-bounding-box-period-N-oscillator?
Code: Select all
x = 129, y = 106, rule = LifeHistory
97.A11.2A$64.A4.B26.A.A9.B2AB$62.3A3.2B2A24.A.A9.3B$61.A5.2BABAB21.3A
.2A9.B.B$55.2B4.2A4.3BA2B.4B15.A4.B8.5B$54.9B4.12B2.4B9.3AB2A6.6B$54.
7B7.11B.5B11.A.2A4.8B$54.9B5.18B12.13B$54.10B.3B.17B14.13B$54.2B2A28B
13.15B$53.2BA2BA27B2.B10.15B$53.2BA2BA32B5.B.17B$54.2B2A10BA46B$53.
14BABA16B2A13B2A13B$54.13BABA16B2A13B2A14B$54.4B.3B.5BA43B3.B2A$55.2B
5.49B4.A2.A$61.34B2.2B2.B3.6B5.2A.A$60.4B.12B3.7B2.4B13.6B7.A$59.4B2.
12B4.6B17.9B6.2A$58.4B7.7B6.3B19.2A4.4B10.2A$57.4B9.7B6.B21.A5.4B9.A$
56.4B10.6B26.3A7.4B10.A$55.4B12.6B25.A2.3A5.4B5.5A$54.4B12.7B27.A2.A
5.4B4.A$53.4B14.7B25.2A2.A.AB.7B2.B3A$52.4B14.9B29.2AB.7B3.2B.A$51.4B
16.9B30.12B4A$42.2A6.4B5.2A9.6B.4B29.7B2A3BAB2.2A$43.A6.4B5.A3.A7.6B.
4B28.7B2A2B.B3A2.A$43.A.AB.7B.BA.A2.A.A5.6B3.4B27.10B3.B.A.2A$44.2AB.
7B.B2A3.A.A6.6B3.4B25.8B8.A$46.5BA5B4.2A.3A3.6B5.4B23.9B7.2A$46.4BABA
4B5.B4.A3.6B5.4B21.4B2.3B$46.4BABA6B.B2AB3A3.6B7.4B19.4B3.5B$48.3BA7B
.B2A.A6.6B7.4B10.A6.4B7.2A$49.12B9.6B9.4B7.3A5.4B8.A$49.13B9.6B9.4B5.
A7.4B10.3A$49.13B2A2.2A2.6B11.4B4.2A5.4B13.A$50.12BA.A2.A3.6B11.9B4.
4B$48.10B.2B.B.A.A3.6B13.6B5.4B$48.2A3.6B4.2A.2A3.6B12.8B2.4B$49.A2.
6B6.A5.6B11.15B$46.3A4.6B3.A.A6.6B10.14B$46.A5.6B4.2A6.6B11.13B$53.6B
12.6B8.2AB.10B$52.6B12.6B8.A.AB3.B2A3B$53.6B12.6B7.A6.B2A3B$36.2A14.
6B12.6B7.2A6.4B$35.A.A15.6B12.6B15.3B$29.2A4.A16.6B12.6B17.2B.BA$27.A
2.A2.2A.4A13.6B12.6B15.B2ABA.A$27.2A.A.A.A.A2.A12.6B12.6B15.BABABA.A$
30.A.ABABAB15.6B12.6B12.A2.A.A.A.A.2A$30.A.AB2AB15.6B12.6B13.4A.2A2.A
2.A$31.AB.2B17.6B12.6B16.A4.2A$34.3B15.6B12.6B15.A.A$34.4B6.2A7.6B12.
6B14.2A$32.3B2AB6.A7.6B12.6B$32.3B2AB3.BA.A8.6B12.6B$30.10B.B2A8.6B
12.6B$29.13B11.6B6.2A4.6B5.A$28.14B10.6B6.A.A3.6B4.3A$27.15B11.6B5.A
6.6B2.A$26.4B2.8B12.6B3.2A.2A4.6B3.2A$25.4B5.6B13.6B3.A.A.B.2B.10B$
24.4B4.9B11.6B3.A2.A.A12B$9.A13.4B5.2A4.4B11.6B2.2A2.2A13B$9.3A10.4B
7.A5.4B9.6B9.13B$12.A8.4B5.3A7.4B9.6B9.12B$11.2A7.4B6.A10.4B7.6B6.A.
2AB.7BA3B$11.5B3.4B19.4B7.6B3.3AB2AB.6BABA4B$13.3B2.4B21.4B5.6B3.A4.B
5.4BABA4B$3.2A7.9B23.4B5.6B3.3A.2A4.5BA5B$3.A8.8B25.4B3.6B6.A.A3.2AB.
7B.B2A$2A.A.B3.10B27.4B3.6B5.A.A2.A.AB.7B.BA.A$A2.3AB.2B2A7B28.4B.6B
7.A3.A5.4B6.A$.2A2.BA3B2A7B29.4B.6B9.2A5.4B6.2A$3.4A12B30.9B16.4B$3.A
.2B3.7B.B2A29.9B14.4B$4.3AB2.7B.BA.A2.2A25.7B14.4B$7.A4.4B5.A2.A27.7B
12.4B$2.5A5.4B5.3A2.A25.6B12.4B$2.A10.4B7.3A26.6B10.4B$4.A9.4B5.A21.B
6.7B9.4B$3.2A10.4B4.2A19.3B6.7B7.4B$8.2A6.9B17.6B4.12B2.4B$9.A7.6B13.
4B2.7B3.12B.4B$9.A.2A5.6B3.B2.2B2.31BC2B$10.A2.A4.45B2C2B5.2B$11.2AB
3.43BA3B2C.3B.4B$12.14B2A13B2A16BABA13B$13.13B2A13B2A16BABA14B$14.46B
A10B2A2B$14.17B.B5.32BA2BA2B$15.15B10.B2.27BA2BA2B$15.15B13.28B2A2B$
16.13B14.17B.3B.10B$18.13B12.18B5.9B$17.8B4.2A.A11.5B.11B7.7B$17.6B6.
2AB3A9.4B2.12B4.9B$17.5B8.B4.A15.4B.2BA3B4.2A4.2B$17.B.B9.2A.3A21.BAB
A2B5.A$18.3B9.A.A24.2A2B3.3A$17.B2AB9.A.A26.B4.A$18.2A11.A!But it's easy to rebuild the Snark chains to make a stable loop structure with a period that's a multiple of eight, and then for large periods we can just put eight signals in the loop. The loop adjusts in only one dimension, so that keeps the bounding box from growing unnecessarily.
Now, we don't _really_ want eight signals in the loop if we're looking for an upper bound, because that's going to require a loop that's about eight times too long. So instead we should find replacements for the Snark chains that have all possible different timings mod 8. We can replace the Snark chain on one side and not the other, to get [odd number]+8N periods.
There will be even smaller lower bounds, if you work at it, using slower signal conduits -- we have some really slow Herschel circuits, for example. But they won't be as simple as a nice clean orthogonal loop (I think).
That's an interesting question indeed, but very hard to make any headway on, at least once the bounding box gets bigger than what we can exhaustively search.A for awesome wrote:Another interesting question related to this might be what the highest finite period attainable by a pattern with a predecessor fitting in a certain-size bounding box.
Once we get to relatively-huge bounding boxes, we don't know -- and aren't likely to know for the foreseeable future -- how small a box a universal constructor-computer predecessor might be squeezed into, with an associated looped program calculating Ackerman's function or some such... Once we cross that size threshold, wherever it is, the highest finite period suddenly goes sky-high (or much higher).
But it seems impossible to figure out very much in practice, for even for far smaller sizes than that. It's going to be very tough to answer that question even about an 8x8 square. I would think an exhaustive search is really the only way to get a definitive answer.
Re: Thread for basic questions
Posted: May 7th, 2016, 9:14 am
I'm looking for an upper bound on the lower bound.
In other words, a minimum size such that "assuming there is a pN oscillator, there is guaranteed to be one that fits in an NxM box, where N and M are defined as follows...".
The concrete example works, but I'm specifically looking at the remaining no-known-pattern oscillator periods here.
In other words, a minimum size such that "assuming there is a pN oscillator, there is guaranteed to be one that fits in an NxM box, where N and M are defined as follows...".
The concrete example works, but I'm specifically looking at the remaining no-known-pattern oscillator periods here.
Re: Thread for basic questions
Posted: May 7th, 2016, 10:51 am
NotLiving wrote:I'm looking for an upper bound on the lower bound.
In other words, a minimum size such that "assuming there is a pN oscillator, there is guaranteed to be one that fits in an NxM box, where N and M are defined as follows...".
The concrete example works, but I'm specifically looking at the remaining no-known-pattern oscillator periods here.
I don't think there will be any provable limits here that are small enough to be of any use. If there's a cell at (0,0) that's part of p41 oscillator, then the state of a cell 41 cells away in any direction (including diagonally) could conceivably affect it.
Therefore the, um, lower bound on the upper bound on the lower bound that you're looking for would be 83x83, for a p41 oscillator... and I can't think of any reason why arbitrarily large support structures could be ruled out absolutely.
For lower periods, in practice, once you get to the first line of stator cells, there's generally a way to add stable support to complete a permanent structure within a few more rows. But nobody has much experience with engineering p41 oscillators.
My intuition on the possibility of "arbitrarily large support structures" is based on past experience with searches for specific oscillators such as a [[superfountain]]. It's only p4, but you need a lot of rows of supporting p4 cells to get the reaction supported successfully. It was hard work to cut the original monstrosities down to this (Nicolay Beluchenko, 2006):
Code: Select all
x = 23, y = 18, rule = B3/S23
11bo3$5bo2bo5bo2bo$3b2o2bob5obo2b2o$5bo11bo$3bob2o9b2obo$bobo3b3o3b3o
3bobo$3obo13bob3o$10bobo$4b3o3bobo3b3o$4bo2bo3bo3bo2bo$3b4o2bobobo2b4o
$3b2o2b3obob3o2b2o$2bo3bo3bobo3bo3bo$3bo2bobobobobobo2bo$4bobob2o3b2ob
obo$5bo11bo!
#C [[ THUMBNAIL AUTOSTART GPS 5 ]]-- That seems really unlikely, based on other experience, but it seems very hard to mathematically rule it out... except with a counterexample!
Re: Thread for basic questions
Posted: May 7th, 2016, 2:31 pm
Good answer, thanks.
On a related note: is there an upper bound on the depth required to support an arbitrary row of still-life with only dead cells on the other side, assuming there is a way to support said row?
On a related note: is there an upper bound on the depth required to support an arbitrary row of still-life with only dead cells on the other side, assuming there is a way to support said row?