From: Scott Fluhrer Subject: Conway's Life: Garden of Eden Pattern Date: Sun, 24 Jan 1999 19:50:27 GMT Newsgroups: sci.math In Conway's Game of Life, a Garden of Eden pattern is defined to be a pattern that cannot arise from a previous pattern. If it exists at all, it must be as part of the starting state. They have been proven to exist, but to the best of my knowledge, no explicit patterns have been demonstated to date. I have found several 16x16 patterns that are Garden-of-Eden patterns. Here is a rather symmetrical example: **************** ** * ****** * ** * ***** ***** * ** ** **** ** ** ****** ** ****** ** * ****** * ** **** **** **** * **** **** * **** * * **** ** ******** ** *** * **** * *** * ************ * ** ** **** ** ** ***** ** ***** *** * **** * *** **************** If anyone is interested, email me, and I'll sketch out a proof that the above is a Garden-of-Eden pattern -- poncho ============================================================================== From: domnei@aol.comxyzxyz (Domnei) Subject: Re: Conway's Life: Garden of Eden Pattern Date: 24 Jan 1999 20:15:24 GMT Newsgroups: sci.math >They have been proven to exist, but to the best >of my knowledge, no explicit patterns have been >demonstated to date. > >I have found several 16x16 patterns that are >Garden-of-Eden patterns. > (snip) Scott - Interesting! Just one correction, though - explicit patterns have been known since the early 1970's. The first one was, I think, found by the '70's group of Life explorers at M.I.T. - it's listed in Vol 2 of Conway/Berlekamp/Guy's "Winning Ways". It's 33x9, so certainly yours is smaller, in terms of area, but only slightly. I _ would_ be interested in a sketch of the proof, as I've never seen a proof that that 33x9 is a Garden of Eden, and always wondered how such a proof goes. Mike Keith Web site: http://users.aol.com/s6sj7gt/mikehome.htm (remove post-w letters from e-mail address) ============================================================================== From: Scott Fluhrer Subject: Re: Conway's Life: Garden of Eden Pattern (oops) Date: Wed, 27 Jan 1999 02:34:18 GMT Newsgroups: sci.math In article <78k9sk$e7f$3@cantuc.canterbury.ac.nz>, mathwft@math.canterbury.ac.nz (Bill Taylor) wrote: >|> Yes, it would be _very_ interesting to see a real proof. > >Yes, obviously there are MANY of us who would like to see it. > >Please post it here! > I see I have severely overstated my case. Here are my particular sins: 1. I stated I had a proof. Well, I do, but it's a computerized search, rather larger than can be verified by hand. I thought that was good enough (after all, theorems such as the four color theorem has relied on computerized searches before now), but as other people have also done computerized searches in this area, it's no big deal. Sorry. 2. As many of you have pointed out, explicit garden of eden patterns were already known. Shows you what I get for not bothering with a literature search. 3. By email, someone pointed out that Achim Flammenkamp has already found an explicit 14x14 pattern (actually, so have I since I announced a 16x16 pattern, but his pattern uses fewer live cells). In addition, he apparently has far more advanced techniques that I do; the emailer reported that Achim "said that [a] constructing 16x16 one took only seconds." For more details on his work, see http://www.uni-beilefeld.de/~achim/ Sorry to bother you guys... -- poncho ============================================================================== From: hwatheod@leland.Stanford.EDU (theodore hwa) Subject: Re: Conway's Life: Garden of Eden Pattern Date: 24 Jan 1999 20:18:54 GMT Newsgroups: sci.math Scott Fluhrer (sfluhrer@ix.netcom.com) wrote: : In Conway's Game of Life, a Garden of Eden : pattern is defined to be a pattern that cannot : arise from a previous pattern. If it exists : at all, it must be as part of the starting state. : They have been proven to exist, but to the best : of my knowledge, no explicit patterns have been : demonstated to date. Some explicit patterns are known; see e.g. the last chapter of Vol 2 of Winning Ways for your Mathematical Plays. Also included in at least one version of a Life simulation program for the Mac. I think it was much larger than 16x16 though. : I have found several 16x16 patterns that are : Garden-of-Eden patterns. ============================================================================== From: dik@cwi.nl (Dik T. Winter) Subject: Re: Conway's Life: Garden of Eden Pattern Date: Mon, 25 Jan 1999 12:55:47 GMT Newsgroups: sci.math In article <78ft4j$dup@dfw-ixnews6.ix.netcom.com> Scott Fluhrer writes: > In Conway's Game of Life, a Garden of Eden > pattern is defined to be a pattern that cannot > arise from a previous pattern. If it exists > at all, it must be as part of the starting state. > They have been proven to exist, but to the best > of my knowledge, no explicit patterns have been > demonstated to date. Once upon the time there existed a journal devoted to Conway's Game of Life. As far as I know only a limited number of issues (6?) have ever been issued. In one of these there is an explicit Garden of Eden. It might be that Martin Gardner also has shown it in one of his columns. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/