Page 1 of 1
Find the smallest pattern provably not glider constructible
Posted: March 13th, 2015, 6:05 pm
by HartmutHolzwart
As recent ptogress in glider constructions has shown, glider construction are pretty versatile.
However, a GoE does not have a predecessor, so in particular it cannot be glider constructible. As relatively small GoEs are known, there also must be a pretty small non glider constructible pattern.
Maybe one can somehow exploit the fact that glider constructible patterns must have predecesssors of every generation.
Otherwise I have no idea how one could prove, that a particular pattern is not glider constructible.
So that is the challenge: Find it and then prove it.
Re: Find the smallest pattern provably not glider constructible
Posted: March 13th, 2015, 7:44 pm
by dvgrn
HartmutHolzwart wrote:However, a GoE does not have a predecessor, so in particular it cannot be glider constructible. As relatively small GoEs are known, there also must be a pretty small non glider constructible pattern...
That's going to be a tough one. If the pattern is a GoE, you're done. Otherwise it has a predecessor -- probably thousands or millions of them, if it's the size of the smallest-known GoE or a little smaller.
A proof of non-glider-constructibility would have to show that all of those predecessors are also non-glider-constructible, and all of
their predecessors as well, as far back as forever. Those ancestors might be space-dust, or near still lifes, or anything in between, and we have to somehow be sure that not one of them can be constructed with gliders.
So... let's just say I won't be tackling that version of the problem any time soon! I'd conjecture that the smallest provably non-glider-constructible pattern will always be the smallest known GoE -- unless someone comes up with a small example of a pattern with a parent but no grandparent, of course, or a small period-N pattern whose only Nth-removed ancestor is itself, or a variation on that theme.
The constructibility question has all kinds of interesting corollaries, though. What's the smallest still life that's not glider constructible (if any)? What's the smallest or lowest-period oscillator that's not glider constructible (probably a lot smaller)? These seem a lot easier to tackle than the original question, though they're probably still not within range of an automated search for the foreseeable future.
Re: Find the smallest pattern provably not glider constructible
Posted: March 15th, 2015, 3:45 pm
by simsim314
I don't think there is any such pattern. And here is why:
GOE are very rare, and probably there is no any pattern that has parent but no grandparent. This is because even one iteration on random pattern will "normalize" the GOL pattern. GOE are bizarre creature that can exist only in "uniform random space".
On the other hand I come to believe everything that has a parent sequence, can be "directed" into glider synthesizable "drection". This is because "parent sequence" can be "normalized" in similar way to "evolving forward" patterns.
So I would say that GOE are some sort of "black holes" of GOL, and are not a part of general "from->to" paths of GOL which cover anything else except GOE. For example everything that can be synthesized by gliders, can be also trivially synthesized by any moving GOL object (say LWSSs etc).
I was thinking of the option to prove any SL can be synthesized, using induction. Due to the fact that SL is "local phenomenon", that means each cell is influenced only by it's neighbors. So in theory it's possible to use some sort of construction mechanism to build SL layer by layer, similar to the way UC build SLs today. You will only need to specify a way how to turn on or off the "next" cell, in space of SLs. This seems to me hard problem - but solvable. You only need to think "locally", in a sense that SL need "stabilizers" of limited width and height around it, and a way to use glider to move from one stabilizer to another.
Re: Find the smallest pattern provably not glider constructible
Posted: March 15th, 2015, 9:06 pm
by dvgrn
simsim314 wrote:So I would say that GOE are some sort of "black holes" of GOL, and are not a part of general "from->to" paths of GOL which cover anything else except GOE. For example everything that can be synthesized by gliders, can be also trivially synthesized by any moving GOL object (say LWSSs etc).
On the other hand... fairly simple calculations will show that above a certain size, most patterns actually have to be GOEs. Very roughly: in the limit case, every time two predecessors have the same descendant, some other descendant must have no predecessor.
Obviously most or all of these parentless patterns will be active space dust, not still lifes. I agree that it seems not too likely that there are any still-life GoEs.
However, I don't think the case has been made very well yet that it's impossible to adjust known GoEs to produce almost-GoEs with just one or a few predecessors -- and then pile several such almost-GoEs around a particular point in such a way that a single predecessor is possible, but that predecessor is provably a GoE.
It's allowable to take as much space as we need to set this up, after all, and the bigger the bounding box, the higher proportion of randomly-chosen patterns are GoEs. (Right?)
Re: Find the smallest pattern provably not glider constructible
Posted: March 16th, 2015, 10:27 am
by simsim314
dvgrn wrote:fairly simple calculations will show that above a certain size, most patterns actually have to be GOEs.
Didn't thought of that, you probably right. We can also give some upper limit to this: we can check what percentile of 5x5 patterns will be different in next generation. This percentile should get down with N for NxN patterns.
We could get patterns that have parent but not grandparents - and yet those patterns are very "artificial" (i.e. rare).
So the claim should be: in the space of "infinite parents" patterns, one can get the parents to get "normalized" (i.e. reduced to gliders).
I can believe some loop can occur in the "non normal space" so some oscillator can be "GoE oscillator" (that means each pattern is the only parent of the next pattern). But if some pattern has infinite list of "different" parents, it should be gliders synthesizable.
Re: Find the smallest pattern provably not glider constructible
Posted: March 16th, 2015, 3:16 pm
by biggiemac
Well, is there a way to show that one-sided constructions (only gliders from NE and NW, for example) are/are not capable of producing certain features?
If it turns out they aren't completely capable, and there's a subset of patterns that absolutely need multidirectional collisions to produce, then if we put complicated patterns in a configuration that no matter the order, the tricky areas will be inaccessible at some point through a construction process, that could be a start. I know there's a difference here between practically impossible and provably impossible, but I'm interested if looking for unidirectional limitations would be fruitful.
There is the problem that we can't exactly rule out any arbitrary pattern that isn't a GoE from showing up in 1G + tons of stills..
Re: Find the smallest pattern provably not glider constructible
Posted: March 16th, 2015, 3:47 pm
by simsim314
biggiemac wrote:but I'm interested if looking for unidirectional limitations would be fruitful.
It wouldn't. You can build everything with slow salvo, and use blockic and other seeds to convert any unidirectional into multi-directional. chris_s already showed how any glider salvo can be "dried" (i.e. can be triggered with single gliders and multiple SLs). So this problem solved (everything that can be constructed with gliders from 4 directions can be constructed with block and gliders from single direction using slow and dried salvo).
The only (obvious) limitation on unidirectional gliders salvo is existence of SL in the first place (otherwise the gliders will continue to infinity).
biggiemac wrote:There is the problem that we can't exactly rule out any arbitrary pattern that isn't a GoE from showing up in 1G + tons of stills..
Well this in principle can be solvable. For example if one shows that all gliders + SL interaction have to satisfy some "combinatorial property". This could show that patterns that don't exhibit this property are not constructable with gliders. But no such property known - and I don't believe that such exists, but it could in principle.
Re: Find the smallest pattern provably not glider constructible
Posted: March 16th, 2015, 5:53 pm
by biggiemac
simsim314 wrote:biggiemac wrote:but I'm interested if looking for unidirectional limitations would be fruitful.
It wouldn't. You can build everything with slow salvo, and use blockic and other seeds to convert any unidirectional into multi-directional. chris_s already showed how any glider salvo can be "dried" (i.e. can be triggered with single gliders and multiple SLs). So this problem solved (everything that can be constructed with gliders from 4 directions can be constructed with block and gliders from single direction using slow and dried salvo).
If I'm not mistaken though this only is true given enough space. What I had in mind was a set of neighboring objects that, once enough were in place, truly limited gliders from entering except from one or two directions, no matter what order you tried to construct them. The technology to turn slow gliders into multidirectional ones doesn't buy anything in that case, there simply wouldn't be room.
Re: Find the smallest pattern provably not glider constructible
Posted: March 16th, 2015, 9:44 pm
by dvgrn
biggiemac wrote:If I'm not mistaken though this only is true given enough space. What I had in mind was a set of neighboring objects that, once enough were in place, truly limited gliders from entering except from one or two directions, no matter what order you tried to construct them. The technology to turn slow gliders into multidirectional ones doesn't buy anything in that case, there simply wouldn't be room.
This is along the lines of what I was thinking a while back about an inductive proof on the constructibility of still lifes. If you have enough tools to add or modify just one cell near a corner of a still life (while also adjusting nearby cells so that the result is still stable) then you could just barely conceivably end up with a complete proof of universal still life constructibility.
However, as the still life gets bigger, it will restrict the number of directions that gliders can come from -- we'll need very different toolkits from what we have so far, to adjust still lifes at corners with gliders from three directions (plus two *WSS directions, I suppose) -- or make changes along an edge with gliders from two diagonals plus one *WSS direction.
I can't see that there's any likely way to prove anything with this approach, though -- or rather, the only workable way looks like a constructive proof, where a complete set of tools is actually found that can incrementally build any arbitrarily large still life.
Re: Find the smallest pattern provably not glider constructible
Posted: March 17th, 2015, 4:46 am
by simsim314
biggiemac wrote: What I had in mind was a set of neighboring objects that, once enough were in place, truly limited gliders from entering except from one or two directions
Well in this case this won't be constructible at all with gliders no matter from which directions. As I said I have a good deal of doubt such thing exists, and a sketch of a general proof for any SL to be constructed. But as long as we guessing everything is possible.
Re: Find the smallest pattern provably not glider constructible
Posted: March 20th, 2015, 11:10 am
by Freywa
Suppose we take an example: how would we synthesise Nivasch's "random" still life from the Golly collection?
Code: Select all
x = 98, y = 98, rule = B3/S23
2obob2o3b2ob2o2bob2o3b2o3b2o2bo5bo8b2o2b2obob2ob2o3b2ob2o3b2o5b2ob2obo
3b2ob2obo$ob2obo5bobo2bob2o3bo2bobobo2b3o3b3o5bo2bo2bob2obobo4b2obobo
3bo2b2o2bobob2o2bobobob2o$6bo4bo2bobo4bo2bobobo7bo5bobo2bo2bobo5bobobo
6bo3bo3bob2o2bo3b3obobo$b6o5b2obobob2ob2obo2bo4b2obo2b4ob3ob3obob2ob2o
bob6obobo2b3o4b2ob2o4bobob3o$o12bo3b2obobo2bobob2o2bob2obo8bo3b2o2bobo
2bo6bobob2obo2b3o4bob2o2bobo3bo$b2ob2obobobobo2bo3bobo2bobo2bo7bob2ob
4o2bo3bobobobo2b3obo2bo4bo2bo2b4o4bobo2b2o$2bobob2ob2obo3bo3bobob2o2bo
2b6ob2obobo3b3ob2o2bobob3o2bob2obob3o4b2o3bob2obob2obo$2bobo7bobobob2o
3bo2b2o8bo7b3o3bo2b3obo4bobo4b2o3b4o2bo3bobobo4bo$b2obob6ob2o2bo6b2o2b
6o2bob6o4bo2bo5b4obobob2o4bo6bo2bobobobob3ob2obo$o3bobo4bo3bobo8bobo5b
obobo5b4ob2ob4o4bobobobob5ob4obob2o2bobobo4bob2o$b4o2b2o3bobo2bobo4b2o
2bobobobobo3bo2bo3bo2bo5b3o3bo2bo7bo3bobo3bobobo3b3o$5bobo3b2obobob2o
5bobob3obobob3obo2bo3bobob4o2b2o2b2obob4o2bob2o2bo3bobo2b3o3b4o$b5o2bo
5bobo7bo2bo5bobo2bo2bob2o2b2obobo3bo8bobo3bobo2bobob2obo2b2o2bobo4bo$o
5bobo2b4ob6o2bobo2b3obob2o3b2o2bobo2bobo2bobob6obobo2b2ob2obobo2bob3o
2bo3b3o$4o2bobobo11bobo2b2obo2bo3b3o2bobo2bo3bob2ob2o5bobob2o5bo2bob2o
5bob4o3bo$4bobobobo2b8obob3o5bob3o2bob2ob3o3bobo6b3obobo3b4obo3bo2b6o
5bob2o$2o2bobobobobo3bo3bobo4b2obob2o3bobo3bo3b4o3b5o2bobo2b3o3bo2b3o
2bo7b5obo$obobo2bobobob2o3bobo2b2obo2b2o4bobob4o2bo5b4o3bobo2bo5b2o2b
2o3b2ob7o6bo$2bo2bobobobobob4o2bobo3bo3b4obobo4b3ob2obo5bobobobo3b2obo
b2o2b2o2bobo7bob2ob2o$bobobobobobobobo3bobobob2ob3o5bo3b2o4bobob2o2b3o
bobobobo2bobo3bobob2o3b2ob6obo2bo$2bo2bo2bo2bobobo2b2obob2obo4b4ob4o2b
3o3bo4bo4bobobob2obobo3bo2bo6bobo8bo$3b3o5bobobobo3bo4bob2o4bo6bo3b4ob
3ob5obo2bo3bob3obo3bobo3bo4b6o$6b5obo2bobo3bob2obobob3o2bob3obobo6bo2b
o6bo3b2obo4bo3b2ob3ob6o$b4o5bobob2obob3obo2bo6b2o3bobobob5o2bobo2b2obo
b3o2bo2b2o4bo6bo7bob2o$bo2bob2o4bobo3bo5bobo2b4o2b2o4bo2bo3bob2obobobo
bobo2bo2b2ob2o3bob4obob5ob2obo2b2o$2bobobo5bo2b2obo2b2obobobo3bobo2b3o
bobo2bobo2bobobobobobobo9bobobo3bobobo2bo7b2o$3b2o2bo5bobob2obo2b2obob
o2bo2bobo2bobobob2obobo2bobob2obo2b11obobobo3bo4bob2obo$o4b3o4b2obo4b
2o4bobobo3bo2bobobobo2bo2b2ob2obo4bobo4bo7bobob5o2bobobob6o$5o10bob2o
3b4obobob3ob2obobobobobo4bo3bob2o2bo2bo4b2ob4o2bo5b3obobo6bo$4bob2o4b
4obob3o3bobobo5bo2bobobobob2o3bo3bobo4b7ob2o4bobo2b3o3bobob4o$3obo2bo
3bo5bo4b3o2bobob3obob2obobobobo2bob2ob2o2b4o11b3o2bobo3b3o2bo5bo$o2bob
2o4bob5ob2o3bobo2bobo2b2obo2bobobo2b3obo4b2o4bob2o2b5o3b2o2b3o4b2ob5o$
bobo5b2obo6bob3o2bobo3bo5b2o2bobo6bob2o3b2o2bobo2bo2bo2bobo2b2o3b4o3bo
$2obob2o2bo2bo2b3o8bob3ob6o2b3o2b4ob2obob3o2bobo2b3o5bob3o2b3o3bob2o2b
o$3bobobobob2obo3b9o4bo5bobo3bobo2bobo8b2ob3o9bo3bobo2b2obo2bob2o2bo$
3bobobobo4b4o9b3obobobobo2bo2bo2bobo2b8o6b5o6b3o2bobobobobo3b3o$b2obo
2bobob2o5bo2b2o2bo3bobob2obobobo3b2obobobo7bob4o5bob4o3bobo3bobo2bobo$
bo2bob2ob2ob2ob2obo2bo2bob3o2bo4bobob2o3bobobo2b8obo3b2o2b2obo3bobo2bo
3bob2obobob2o$2bobobo9bob2obob2o4b2ob4obobo2bo2bobobo12b2o3bo4bo2b2ob
2ob2ob2o4bobobo$b2obo2b5ob2obo2bobo4b2o2bobo4bobobo2b2obob4ob4ob2obob
2ob5o3bo2bo2bo5b3o2bobo$2bobo7b2o2b3o2b4obo3bobo2b3obob3o3bo4bobo2bobo
2bo2bo10b2o2bo2b5o2b3ob2o$2bobobobobo4bo3b2o3bobo2b2obobo3bobo3b2o2b4o
3bobo2bobobo2b7o7b3o5bo4bo$b2o2bob2ob4obo2bo2b2obobobo2bobob2obo3bobo
7b4ob4o2bob2obo4b8o5b2obo2b2o2bo$o2bobo8b2obobobo2bobobobo2bobo2b5o2b
6obo8bobo2bo3bo9bob2o2bo2bobo2b2obo$b2obobob5o4bobobo2bobobo2b3obobo5b
obo4bo3b2ob2o2bob2obo2b10obobobobo2bob2obo2bo$4bobobo4b4o2bob2obobob3o
5bobob2obo2b2o3b3obobobobo2bobobo10b2obobob2obo2bobobo$b2obobo2b3o5b2o
5bobo4bob2obob2obobo4bo6bo3bobobo2bobo2b3ob3o4bobo4bobo2bob2o$o2bo2b3o
3b4obo6bobob4obo2bo5bob4o2bob2obobo2bo2bobo2bobo2bobo2b3obo2b4obo3bo$b
o2b2o3b3o3bobobob2obobobo5b3ob3obobo3b4obobob3o3bobobo2b2o3bobo2bob2ob
o3bo3b2ob2o$2b2o3b2o4bobobob2obobobo2b5o3bo2bobo2b3o5bobo4b4obobobo5bo
b2obo2bobobo6bob2o$5b2o2b6obobo3bobob2obo4b2obobo2b3o3b6obob2obo4bobob
5obo2bob2obobob2o5bo$2b3o2bobo6bo2bob2obo4bob2o3b2obobo3b2o9bobo2b4o2b
2o4bob3o5bobo3bo3b2o$bo3bobobob4ob3o3bobob2obobob2o3b2obob2o2b5ob3o3b
2o3bobo3b2obo4b5obob3obo3bob2o$bobo2bo2bobo2b2o3b2o3bob2ob2o2bob2o4b2o
bobo4bobo2b3o2bobo2bob2obobob2obo3bobo3bo2bo2bob2o$2ob2obobo3bo4bo3b4o
8bobob4o3bo2b2o2bobobo3bobobobobo4bo2bo2bobo4b2obo3bobo$6bob5ob2ob4o4b
9obobo2bob2obobobobobo2bobo2bobobobob2obobo2b2ob4obobob3o2bo$2ob2o2bo
6bobo5b3o4bo4bo3bobobo2bo3bobob4obobobo2b2obobo2bob2o6bobobo4b2ob2o$bo
bo4b6o2bob4o4bo4b2obob3obo2b3obobobo5bo2bobobo3bo2bobo2bob4obobob5o2bo
2bo$o2bobo7bobobo5bob2o5bo2bo4b3o3bobo3b5o3bobo2bobob3o2bobobo2bobobo
5bo2bobo$2obob7o3bo3b5obo6bo3b4o3b2obobob2o5b3o2b4obo4b2o2bo2bobobobob
2o2bob2ob2o$bob2o7b3ob3obo5bo3bob4o3bobo2bobobobo2b3o4b2o6b4o4b2obobob
obobobobobo$o5bob2o2bo3bo5b4obobobo4b2obob3o2bobo3b2o2b3obo2bob3o4b4o
2bobob2obo3bobobo$4ob2obo7bob4obo3bobo3b2obobo5b2obobo6bo2bo2b2obo2b3o
bo3bobobo4b4o3bob2o$3bobo2bo2bo3b2obo8bob4obobobob4o3bob4obobobo4bobob
o2bobo2b2obo2b4o4b2obobo$2obo2bobobobobo6b2o2b2obo3bobobobobo3bob2o5b
2obob2o3bo2bob2o2bobo2bobobo4bo2bob2obo$obobobobobobob2ob5o4bobob2o3bo
2bo2bob2obo2b3o3bobo3b2obobobo3bobo2bobobob3obobo4b2o$2bobobobobobo2bo
bo5bo2bo2bo2b3o3b3o3bo3b2o2b2obobob2obobobobo2b2o2b3obo2bo2bobob4obo2b
o$2bobobobobob2obo2b6o3bobobo9b2obo6bo2bobobobobobobobobo2b2o4b2obobo
2bo4bobob2o$b2ob2obo2bobo2b3o2bo7bo2b4o2bobo2bobob4obobo2bobobobobob2o
bobo4bobo3bobobo2b2o3bobo$bo5bobo2bobo3bo3b2o2bobobo3b4ob3o2bobo2bobob
3o2bo2bo2bo4bob6obob2obobob2o2b4o2bo$2b6ob2obo2bobo3b2o2bobobob2o5bo5b
obobo2b2o3b2obobobo2b3obo7bobo2bobo3b2o4b3o$11bob3ob2o5b2obo2bo2b4obob
obobo2bob2o3bo4bobo2b2o2bobob5obo2bobo2bobo3bobo$4ob5obo13bob2obobo4bo
b2ob2obobo2bob2ob4obob2o2b2o2bobo3bo2bobobob2ob4ob2ob2o$o2bobo3bo2b4ob
2o6bo2bobob4obo7bob2obo2bo6bo2bobo2b2o2bobo2bobobobo7bo3bobo$5bobo2b2o
3bobo2bo2bob2obo2bo4bo2b2ob4obo2bobo2b3obobobo2bo5bob4obobobob5o3b2o$
4bobob2o2bo2bo2bob4o2bo2bobob2o5bobo4bobobob2o2bobobob2obob5o5bo2bobob
o4b3o2b2o$3bo2bobo2bobob2obo5bo3b2ob2o2b5o2bob2obobobo3bobobob2o3bobo
5b3obobo2bo3b2obo2bo2bo$3b4obob2obo4b5o2b3o6bo4bobobo2bobobo2b3obo2bo
3b3obo2b3o3b2obobob4o2bobob2o$o7bo2bobob3o5b2o4b6ob2obobobobo2bo2b2o3b
ob2o2b2o4bobo4bo3b2obo6bo2bo$4ob4o2bobobo2b5o3b3obo5b2obo2b2obobobobo
2bo2bo2b2o2b4o2b5ob2o3bobob3ob2obo$3bobo3b2o2bo2bo6b3o6b3o4bo4bobo2bo
2bob2obobo2bo5b2o6bob3o2bobo2bo3b2o$2obo3bo2bobob2ob4obo2bob5o2bob2ob
5o2bobobobo2bobobobob5o3bob2obo3bob2o2bobob2o2bo$obo2bob2o3bo3bo3bobo
3bo5bo2bobo5bobobobobobo4bob2obo4b4obo2bo3bo3b3o2bobobobo$3b3o3b3ob2ob
o2bo3b3o2b3o2b2o2bob3obobobobo2bob3obo5b4o5bo2b2o3b3o3bobobobo2bo$6bob
o4bo2bobob3o3b2o3b2o2b2obo2bobobobo2bobo4bobob2obo3bob3ob2o3bobo3b2o2b
obob2obo$b4obob4obob2obobo2bobo2b2o4bo3bobo2bobob2obob4o3b2obo4b2obo2b
o2b4o3b2obob2obobo2b2o$o4bo5bobobo2bobo2bobobo2b5ob2obob3obo3bo6b3o3bo
bo3bobobo2bo4b3obobo2bobobobo$4obob4o2bobob2o2b3ob2o2bo5bobo2bo4b3o2b
4obo3bobo2b4o2bob2obob2o3bobob2obobobo2b2o$3bobobo2bob2o2bo2b2o9b4obob
o4b3o3b2o3bob5obobo6bo4bobob2obobo3bo2bo2bobo$2obobo2bo2bo2bobobo2bob
7o3bob2ob4o2bobo3bo2bo7bo2bob5ob4obo3bobobobo3bob2o2bo$o2bo2bob2obo2bo
bob2obobo6b2obo4bo3bo3b3o2bob6obo2b2obo4bo5b3obo3bobobobo2bob2o$bob4o
4b4obo4bobob4obobob3obob2ob3o3b3o6bob2obo2bob2obob4o3bob4obob2obo3bo$
2o5b4o5bob3obo2bo2bo3bo4bobo3bo2b3o3b5obo4bob2obo2bobo4bobo5b2o4b2o2bo
$2b4obo2bob2obo2bo3bobo3bobo2b3obo2b2obobo3b2o6b2ob2obo4bobo3b4obobob
2o4b3o2bob2o$2bo2bo2bobobo3b2o4bo2b4ob3o3bob2o2bo2b2o2bob5o4bo2b6ob4o
3bobobobob4o3bobo$6bobobobob2o4b2obobo7bo2bo3bobobo2bobobo2bo5bobo6bo
4bo4bobobobo3bobo2bob2o$5b2obobo2bo2bobo2bobobob2ob3o2b2o3bobob2o2bobo
5bobobobobob2obob3o5bobobo2bo2bobobo2b2o$9b2o4b2ob2o4b2ob2obo10bo7bo5b
2ob2o3b2obob2obo6b2ob2o2b2o3b2ob2o!
The procedure I have in mind is similar to how integrated circuits are built up: we first synthesise the bottom of this still life and then work our way upwards. So the proof that all still-lifes are constructible would have two phases: (1) show that any finite rectangular region containing some still-lifes can be built from two directions on a long, thin still-life base and (2) show that all such thin bases can be synthesised from four directions from a seed of 18 or fewer cells (which we know
has to be constructible).
To do this, though, we'll need a compendium of all possible motifs that may appear in still lifes and transformatory procedures between them. This is Appel and Haken's 1976 proof of the four-colour theorem all over again.
Re: Find the smallest pattern provably not glider constructible
Posted: March 20th, 2015, 5:34 pm
by mniemiec
Freywa wrote:The procedure I have in mind is similar to how integrated circuits are built up: we first synthesise the bottom of this still life and then work our way upwards. So the proof that all still-lifes are constructible would have two phases: (1) show that any finite rectangular region containing some still-lifes can be built from two directions on a long, thin still-life base and (2) show that all such thin bases can be synthesised from four directions from a seed of 18 or fewer cells (which we know has to be constructible).
Back in 1998, at the CA98 conference, I did a talk about object synthesis from gliders. At the very end, I mentioned some subjects for future research, which included a hypothetical method to synthesize all still-lifes. The method was somewhat similar to how 3D printers work today. Basically, you are always working on a "still-life in progress", which can be divided into three regions. Let us consider the still-life as an oscillator of period 1. Pick a cell that we will call the "active cell". Everything anywhere above that cell, or directly left of it is part of the rotor (i.e. active part of the still-life). The active cell, everything below it, or directly right of it is part of the stator (i.e. temporary scaffolding that is used to support the rotor until it is self-sufficient). The top row of the stator (active cell, everything right of it, the cell below it, and everything left of that) is the bushing (whose composition matters) and the rest is the casing (whose composition doesn't).
If the active cell is the opposite state than that desired in the still-life, one needs a method to surgically alter it and the stator around it; if it already has the desired state, one need do nothing. In either case, once the active cell is the right state, one can name the cell to its right the new active cell. By induction, by starting with an empty active cell two squares to the left of the still-life and progressing to an empty active cell two cells to the right of the still life, one can thus "print" an entire row of the still-life. Similarly, by then switching the active cell to an empty cell on the left end of the next row, starting with empty space and ending with two empty rows, one can print any still-life.
The main difficulty with this method is to identify all the different kinds of temporary stator necessary to support any rotor (which is fairly easy), and to find ways of surgically altering every possible stator configuration to flip the internal active bit (which is not).
One could use a similar method to print higher-period oscillators, but the number of stator pieces (which would not necessarily be still-lifes) would increase dramatically, as would the number of synthesis mechanisms needed to flip the active bit (which would now have multiple states). I suspect that this might not be too difficult for period 2 oscillators, but I shudder at the complexities involved for anything higher.
Freywa wrote:To do this, though, we'll need a compendium of all possible motifs that may appear in still lifes and transformatory procedures between them.
Yes, exactly!