orphan pattern / garden of eden

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

orphan pattern / garden of eden

Post by keeskwekkeboom » December 15th, 2011, 5:02 am

Does anybody know software to verify Garden's of Eden / orphan patterns?

Since with a new approach (in contrast to backtracking) I might have found some new 10x10 orphan patterns.

Please let me know.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: orphan pattern / garden of eden

Post by HartmutHolzwart » December 15th, 2011, 5:04 pm

you can use wls in parent mode to verify that you have found an orphan.

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: orphan pattern / garden of eden

Post by 137ben » December 15th, 2011, 5:39 pm

HartmutHolzwart wrote:you can use wls in parent mode to verify that you have found an orphan.
Although it only actually checks for a GoE.

keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

Re: orphan pattern / garden of eden

Post by keeskwekkeboom » December 16th, 2011, 6:57 am

It's not very clear to me which search settings I have to use to find a previous generation (if it exists).
I tried to fill in the possible orphan pattern, keep default search settings (find parent only = off) and start a search. I got loads of warnings about inconsistent cells at row x column y.

So I tried a simpler example, the following configuration (x = don't care; - = dead; o = life). I did not find a previous generation, so probably my settings are wrong?
xxxx
x--x
x-ox
xxxx

keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

Re: orphan pattern / garden of eden

Post by keeskwekkeboom » December 16th, 2011, 12:26 pm

Actually, here you can find our orphan. http://homepage.tudelft.nl/37b0y/

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: orphan pattern / garden of eden

Post by HartmutHolzwart » December 16th, 2011, 2:17 pm

Maybe you should read the instruction for wls first.

Use the parent options and set number of generations to 2.

In order to find a potential predecessor, you need to lay at least three cells of X around the pattern. Note that you have to enter your pattern in gen 1 in oder to have the predecessor in gen 0.

Hope this helps!

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: orphan pattern / garden of eden

Post by 137ben » December 16th, 2011, 4:46 pm

Actually, here you can find our orphan. http://homepage.tudelft.nl/37b0y/
Wow, this may be the first known GoE which fits in a 10 by 10 box, congratulations!

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: orphan pattern / garden of eden

Post by HartmutHolzwart » December 16th, 2011, 7:07 pm

Actually, you need to leave another ring of empty cells around the pattern to prove it's an orphan.

keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

Re: orphan pattern / garden of eden

Post by keeskwekkeboom » December 18th, 2011, 11:21 am

Yes, of course we used another ring of cells around the 10 x 10 box in order to find the orphan. Currently WLS is running with one ring of don't care (x) cells.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: orphan pattern / garden of eden

Post by HartmutHolzwart » December 18th, 2011, 12:34 pm

you'll need one ring of empty cells and three rings of X-cells!

keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

Re: orphan pattern / garden of eden

Post by keeskwekkeboom » December 19th, 2011, 10:24 am

Why one ring of empty cells? These are not part of the orphan pattern and would therefore be a Garden of Eden containing the orphan pattern. If the orphan pattern already has no precursor an extra ring won't alter that. In my opinion one ring of don't cares is enough.

And why three rings of X-cells?

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: orphan pattern / garden of eden

Post by HartmutHolzwart » December 20th, 2011, 4:50 pm

This is due to the way x-cells work in WLS. Actually the cells set can influence x-cells to be set as well, if this is necessary for consistency.

One ring of x-cells means that there is no predecessor that consists of empty cells outside the wls field. Only with a ring of three rows of x-cells, side effects can be eliminated.

keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

Re: orphan pattern / garden of eden

Post by keeskwekkeboom » December 22nd, 2011, 4:36 am

Achim Flammenkamp verified that this pattern has no predecessor. Also, the pattern got a sound name: orphan 7 :D .
http://wwwhomes.uni-bielefeld.de/achim/orphan_7th.html

User avatar
Wojowu
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: orphan pattern / garden of eden

Post by Wojowu » December 22nd, 2011, 9:17 am

Congratulations! This is smallest Garden of Eden known! And it has rotational symmetry! I think there are smaller ones (maybe even 6x6), but most of them won't have any symmetry :cry: .
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: orphan pattern / garden of eden

Post by HartmutHolzwart » December 22nd, 2011, 2:17 pm

Could you elaborate on your approach? Did I overlook a link?

I think quite a lot of people here would be interested!

Thanks in advance,
Hartmut

keeskwekkeboom
Posts: 7
Joined: December 15th, 2011, 4:57 am

Re: orphan pattern / garden of eden

Post by keeskwekkeboom » January 8th, 2012, 4:43 pm

Currently, we are working on a paper for AAAI that will elaborate our approach and we are running some more experiments to see if we can find an even smaller GoE. Once we have news we will post more info here.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: orphan pattern / garden of eden

Post by Macbi » September 25th, 2017, 7:34 pm

Could somebody clarify for me the remarks made by HartmutHolzwart in this thread?
HartmutHolzwart wrote:you'll need one ring of empty cells and three rings of X-cells!
In particular I'd like to know the minimal value of n for which we can say that if a pattern has a predecessor then it has a predecessor all of whose live cells are within a distance of n from the positions of the live cells in the original pattern. I think HartmutHolzwart is suggesting that n is 3 or 4, but that seems like a huge number.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: orphan pattern / garden of eden

Post by dvgrn » September 25th, 2017, 10:42 pm

Macbi wrote:Could somebody clarify for me the remarks made by HartmutHolzwart in this thread?
HartmutHolzwart wrote:you'll need one ring of empty cells and three rings of X-cells!
In particular I'd like to know the minimal value of n for which we can say that if a pattern has a predecessor then it has a predecessor all of whose live cells are within a distance of n from the positions of the live cells in the original pattern. I think HartmutHolzwart is suggesting that n is 3 or 4, but that seems like a huge number.
Hartmut has a lot more experience with WLS than I do, so all I can do is try to re-explain this part a little bit:
HartmutHolzwart wrote:This is due to the way x-cells work in WLS. Actually the cells set can influence x-cells to be set as well, if this is necessary for consistency.

One ring of x-cells means that there is no predecessor that consists of empty cells outside the wls field. Only with a ring of three rows of x-cells, side effects can be eliminated.
When you set up a target pattern in WLS with just one row of X-cells around the outside, everything beyond that is "outside the WLS field" and is assumed to be all OFF cells (not unknown don't-care cells).

That's actually an additional restriction that you don't want when you're hunting GoEs. There might well be no possible way to fill that single ring of X-cells in the predecessor pattern, without including three ON cells in a row along one edge. If that happens, then it forces a cell to be ON outside the ring in WLS's internal model of the descendant pattern.

If there's a cell ON out there, then that doesn't match WLS's assumption that all those cells out there are OFF -- so WLS cheerfully throws away that candidate, even though it might actually be a perfectly good predecessor pattern.

Apparently effects like these can propagate one more row out somehow. At least, the implication is that two rows of X cells aren't enough, because WLS might still deduce that an ON cell must be set beyond those two cells, and thereby throw out a valid solution.

I don't see how that would happen exactly, when you're only looking for a one-tick predecessor. Once you have two rings of X's there's really not much harm in adding a third, I suppose -- but it would be good to see a specific example of such a forced cell to prove that it's not an old superstition from a previous version of WLS, or something like that.

One experiment might be to see if WLS finds the same number of parents for something like mtve's grandparentless pattern, when there are two rings of X cells and when there are three.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: orphan pattern / garden of eden

Post by Naszvadi » September 26th, 2017, 2:32 am

For the OP, my 2cents are: ../forums/viewtopic.php?f=9&t=2563, which basically points to my contribution to GNU linear programming kit. That contains life_goe.mod that can be solved with older GLPK binaries like in WLS/*ubuntu repos, it is a general pattern GOE checker in B3/S23. Feel free to ask if you have further related questions!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: orphan pattern / garden of eden

Post by Macbi » September 26th, 2017, 4:34 am

dvgrn wrote:Apparently effects like these can propagate one more row out somehow. At least, the implication is that two rows of X cells aren't enough, because WLS might still deduce that an ON cell must be set beyond those two cells, and thereby throw out a valid solution.
So what I'm worried about is that three cells might not be enough. Unless we have some mathematical proof that "if a pattern has a predecessor then it has one with all its cells within a range of 3" then all of the patterns that we are claiming to be GOEs might actually not be. They might have some 1000000 by 1000000 predecessor.

(Actually I think all know GOEs have also been shown to be orphans (which really does only require looking in a 1 cell margin). So there's not actually a problem with any of them. But I hope you see what I'm worried about in principle.)

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: orphan pattern / garden of eden

Post by dvgrn » September 26th, 2017, 8:36 am

Macbi wrote:
dvgrn wrote:Apparently effects like these can propagate one more row out somehow. At least, the implication is that two rows of X cells aren't enough, because WLS might still deduce that an ON cell must be set beyond those two cells, and thereby throw out a valid solution.
So what I'm worried about is that three cells might not be enough. Unless we have some mathematical proof that "if a pattern has a predecessor then it has one with all its cells within a range of 3" then all of the patterns that we are claiming to be GOEs might actually not be. They might have some 1000000 by 1000000 predecessor.
It's definitely a worthwhile thing to worry about -- but I don't think there's actually a problem.

A WLS search needs three rings of X's only for a technical reason. It either finds, or doesn't find, parent patterns for the original MxN pattern. If a parent doesn't exist inside an (M+2) by (N+2) box, then the pattern is a GoE -- no question, because of the speed-of-light limit. Anything outside that is irrelevant to the GoE question.

The three rings of X's are just to make sure that WLS doesn't throw away valid parents that happen to force ON cells to exist several rings out. This "forcing" calculation is a side effect of WLS's optimization algorithm, which amounts to "don't try anything with OFF cells in positions where they're forced to be ON, because that's obviously a total waste of time".

If WLS didn't have those optimizations -- say, if it did a brute-force check of every combination of ON and OFF cells in the (M+2) by (N+2) region -- then the three rings of X's wouldn't be necessary... but also a search for predecessors of a 10x10 GoE would take until the Sun burns out.

Also, if WLS's default assumption was that cells outside the search field were X's -- don't-care cells -- rather than OFF cells, then no rings of X's would be needed at all in the setup. But since that's not the way it was designed... well, we have it on good authority that WLS's optimization tricks will never reach out and force an ON cell across three rows of X's. No need to worry about 500000-ish rows out.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: orphan pattern / garden of eden

Post by Macbi » September 26th, 2017, 2:10 pm

If a parent doesn't exist inside an (M+2) by (N+2) box, then the pattern is a GoE -- no question, because of the speed-of-light limit. Anything outside that is irrelevant to the GoE question.
I think I might be making a distinction between "Garden of Eden" and "Orphan" that you're not. According to LifeWiki:
A related concept to Gardens of Eden is that of orphans, which are finite patterns that can not occur as part of the evolution of another pattern. That is, they are Gardens of Eden that can be extended in any way to form other Gardens of Eden.
So being an orphan is a stronger property than being a Garden of Eden. A Garden of Eden is a pattern (an assignment to every cell in the grid of alive or dead) with no pattern that transforms to it. An orphan is an assignment of alive or dead to some of the cells in the grid, such that however we fill in the remaining cells we get a Garden of Eden.

Now, if I have an N by M pattern it's easy to verify if it's an orphan: I draw the N+2 by M+2 box around it and check (lets pretend by brute force) that every way of filling in that N+2 by M+2 box evolves into a pattern that disagrees with the alleged orphan on at least one cell within the N by M box. As you say: the speed of light prevents any cells outside the N+2 by M+2 box from mattering.

But now I claim that it's much harder to verify if a pattern is a Garden of Eden.

Suppose I have an N by M pattern. I can check if it's an orphan, as above. If it is then it's also a Garden of Eden. If not then there exists an N+2 by M+2 arrangement of cells whose evolution agrees with my pattern inside the N by M box. But this isn't necessarily a predecessor of my pattern: it could have some cells that remain alive outside the N by M box. So in this case it remains unknown whether the pattern is a GoE or not.

So checking if something is a GoE isn't simple and I don't know a good way to do it.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: orphan pattern / garden of eden

Post by dvgrn » September 26th, 2017, 3:16 pm

Macbi wrote:... So checking if something is a GoE isn't simple and I don't know a good way to do it.
Good point. Yeah, this GoE stuff is a big theoretical pain, which might become a real problem for an actual candidate GoE pattern at some point.

Pattern Types We've Seen So Far
For the moment, I think that every known infinite pattern with a finite number of ON cells is either

1) a Garden of Eden that includes an orphan, or
2) a non-Garden-of-Eden with a parent pattern that generates the pattern exactly with no far-away ON cells.

Those are both easy cases. But maybe there's a third type of pattern,

3) a non-Garden-of-Eden MxN pattern that does not include an orphan inside the MxN box, but nonetheless has no parent pattern that generates the exact MxN pattern with no ON cells anywhere else.

Now, if we have this situation, then evolving any parent of P by one tick must turn on at least one cell in some set of cells S. Clearly we can just add OFF cells at every location in S, and call that an orphan. The only problem is that that orphan doesn't fit inside MxN any more.

(It may be provable that set S must be finite, so the orphan is still finite, at least. Or might a finite MxN pattern force an infinite set of cells to be ON? Not sure. Don't want to think about it. Maybe it doesn't matter anyway.)

Well, They Probably Exist
Seems like a type-3 beast is going to be fairly hard to find, because very often you can overpopulate an area outside MxN and have everything die off in one tick. Somehow you have to play some clever games near the boundary so that that is not possible.

-- Then again, Steven Eker's Garden of Eden 10 is very close to being an example, isn't it? If we could find a Garden of Eden that includes a single OFF cell outside an Mx(N+1) rectangular boundary, then we could cut off that cell with a slightly smaller rectangle... and that would guarantee that the MxN pattern has parents, but that none of the parents create exactly the MxN pattern with no ON cells outside the rectangle.

Limiting the Damage
We know how to fill an arbitrarily large area with ON cells, such that everything inside that area definitely dies of overpopulation in one tick. We could actually do that everywhere outside the one-cell ring around the MxN pattern, couldn't we? So the only place where there's a potential problem is right there in that one-cell ring.

If I'm right about that (which I certainly wouldn't bet on) then really that's just a slightly larger brute-force search, and the theoretical problem pretty much goes away. Set S above turns out to be some subset of the cells in that one-cell ring around MxN, not a hypothetical scattering throughout the infinite Life grid.

(?)

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: orphan pattern / garden of eden

Post by Macbi » September 26th, 2017, 5:44 pm

(Big titles, dvgrn style.)

A mathematical result

The wikipedia page for Garden of Eden says that every GoE contains an orphan:
Wikipedia wrote:By definition, every orphan belongs to a Garden of Eden: extending an orphan to a configuration of the whole automaton, by choosing a state for each remaining cell arbitrarily, will always produce a Garden of Eden. But the reverse is also true: every Garden of Eden contains at least one orphan.
To be more precise I think this means that for every GoE (considered as an infinite pattern where all cells are either on or off) we can find a finite subset of the cells which is an orphan. But this doesn't mean that if the GoE has all its live cells in an N by M box then we can find an orphan in that same box. The orphan could be much larger.

It at least answers this question:
dvgrn wrote:(It may be provable that set S must be finite, so the orphan is still finite, at least. Or might a finite MxN pattern force an infinite set of cells to be ON? Not sure. Don't want to think about it. Maybe it doesn't matter anyway.)
The set S can always be chosen to be finite.

The proof of the result sounds hellish:
Wikipedia wrote:To prove this, Kari uses a topological argument, based on the Curtis–Hedlund–Lyndon theorem according to which the transition functions of cellular automata are exactly the translation-invariant continuous functions on the space of configurations. Here, continuity is defined by assigning a discrete topology to the finite set of states of the automaton, and then using a product topology with one term in the product for each cell in the automaton to construct a topological space whose points are the automaton's configurations. By Tychonoff's theorem it is a compact space.

For each finite pattern, the set of configurations that contain the pattern is an open set in this topology, called a cylinder. The cylinders form a basis for the topology. As Kari observes, the collection of configurations that are not Gardens of Eden is just the image of the transition function, so by the closed map lemma for compact spaces it is a closed set. The set of Gardens of Eden, correspondingly, is an open set. Because it is open and the cylinders form a basis, the set of Gardens of Eden can be represented as a union of cylinders. Each of the cylinders in this union consists only of Gardens of Eden, so the pattern that determines each cylinder must be an orphan. If the set of Gardens of Eden is non-empty, there must be at least one cylinder in this union, so there must be at least one orphan. And any particular Garden of Eden must belong to one of these cylinders, and therefore must contain the orphan for that cylinder.
But I've run into this sort of argument before. I bet it boils down to the following:
  • Suppose we had a pattern containing no orphans
  • Then we can look at a 1 by 1 box. It's not an orphan, so there must be some predecessor that works at least inside that box
  • Then expand it to a 3 by 3 box. It's not an orphan, so there must be some predecessor that works at least inside that box. This predecessor must be consistent with one of the predecessors for the 1 by 1 box, because we can just restrict it
  • Carry on in this way, continually expanding to larger boxes
  • Stitch together all these consistent partial predecessors to form an actual predecessor for the whole pattern
  • So if a pattern contains no orphans then it has a predecessor
  • So every GoE contains an orphan
The difficult bit it the precise details of the "stitching together" process. It's probably not too hard to work out the details by hand, but if you're a mathematician it seems more elegant to use a "compactness" argument like Kari does above.

So there is an algorithm

I had been a bit worried that there might not be any algorithm that determined whether or not a given pattern was a GoE. Maybe you could somehow encode a Turing machine into a pattern, so that determining whether or not it had a predecessor was the same as solving the Halting Problem. But because of the above result we can use the following algorithm:
  • Suppose we have a pattern with finitely many live cells that fit inside a N by M box
  • (a) Check if this N by M box is an orphan. If so then the pattern is a GoE
  • (b) Check if there is an N+2 by M+2 predecessor, if there is then the pattern isn't a GoE
  • If neither (a) or (b) worked then expand the box by one cell in every direction and repeat
Because of the above result there either is a predecessor, or there is an orphan, and the above algorithm will eventually find one or the other and then halt.


Except...

What if we had some pattern with only a finite number of live cells, but all of whose predecessors had an infinite number of live cells? If this can happen then the above algorithm might never halt, because there is a predecessor but the predecessor doesn't fit in any bounding box. I don't think that this can actually happen but at the moment I can't disprove it.

I like this idea
dvgrn wrote: Limiting the Damage
We know how to fill an arbitrarily large area with ON cells, such that everything inside that area definitely dies of overpopulation in one tick. We could actually do that everywhere outside the one-cell ring around the MxN pattern, couldn't we? So the only place where there's a potential problem is right there in that one-cell ring.

If I'm right about that (which I certainly wouldn't bet on) then really that's just a slightly larger brute-force search, and the theoretical problem pretty much goes away. Set S above turns out to be some subset of the cells in that one-cell ring around MxN, not a hypothetical scattering throughout the infinite Life grid.
So we have an N by M pattern, and an N+2 by M+2 pattern whose successor agrees with the N by M pattern inside the N by M box, but also leaves or creates some cells outside of that. And our plan is to just add loads more cells around the outside in order to kill off all these cells we don't want via overpopulation. These extra cells will form a solid block going all the way around our pattern, and we know that it's possible to create an edge for the outside of a solid block so that no cells stay alive or are born near that edge.

I agree that this is a good plan. Also, if we could make it work then we can rule out the nightmare I described above: a finite pattern with only infinite predecessors. But it's not immediately trivial.

The naive thing to try is just to completely fill in every cell outside of the N+2 by M+2 box. But this won't work: if there are three empty cells at the edge of the N+2 by M+2 pattern, then we will have inadvertently caused a new cell to be born there. So we need a cleverer approach: some way of adding extra cells without accidentally causing any new survivals or births. I don't immediately see how to do this.
Last edited by Macbi on September 26th, 2017, 6:49 pm, edited 1 time in total.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: orphan pattern / garden of eden

Post by dvgrn » September 26th, 2017, 6:13 pm

Macbi wrote:The naive thing to try is just to completely fill in every cell outside of the N+2 by M+2 box. But this won't work: if there are three empty cells at the edge of the N+2 by M+2 pattern, then we will have inadvertently caused a new cell to be born there. So we need a cleverer approach: some way of adding extra cells without accidentally causing any new survivals or births. I don't immediately see how to do this.
Darn. I figured there was probably some invidious exception to my hopeful suggestion, and you've unfortunately found it.

Some cases we can certainly handle -- like if an edge is all OFF cells, two rows deep, then we have some limited ability to do things like this:

Code: Select all

x = 18, y = 18, rule = LifeHistory
2.A2.A2.A2.A.A.A$2.A2.A2.A2.A.A.A$18A$2.14A$18A$2.4A.2A.6A$2.4A7.3A$
6A6.6A$2.3A7.4A$2.4A7.3A$6A6.6A$2.3A7.4A$2.6A.2A.4A$18A$2.14A$18A$2.A
2.A2.A2.A.A.A$2.A2.A2.A2.A.A.A!
But that doesn't work for all widths. Somehow it seems likely that there's a counterexample cell arrangement at an edge or corner, that means that all added cells can't be instant-killed without causing new births, by any possible surrounding Ring of Death By Overcrowding.

That's just a guess. But it seems kind of analogous to the Coolout Conjecture -- it just seems like there are very limited options for fixing problems. If you have two problems right next to each other along an edge, and you need control over three cells to fix each problem, then you're going to be out of luck.

Maybe like the Coolout Conjecture, the smallest counterexample will turn out to be manageably small.

Post Reply