RWG> ... My 3x3 memory, also vague, was that someone at the AILab (Beeler? Speciner?) Greatly reduced the GOE bound by exhaustively searching for the 3x3 with fewest predecessors (= the hollow box, despite its frequency of appearance). Banks then used this to focus his GOE search.) I was searching for a GOE, and Roger Banks beat me to it. I or Mike Speciner may have tabulated the predecessors of all 3x3s, but that turned out to be a bad goal. I tried to fit in lots of hollow boxes, but found it is necessary to throw in considerable "garbage" to force the predecessor count to keep going down as the candidate strip is extended. Roger's sense of what to append was, I felt and still believe, inspired. On a related note, could another answer to Marc LeBrun's question be the "grandfatherless problem"? -- Must there exist a Life pattern that is not a GOE, but all of whose predecessors are GOEs? I remember this was discussed years ago, but I cannot recall what was decided! -- Mike Beeler
--rwg
ACW>*Winning Ways* came out in 1982, more than a decade after the original flurry of Life columns in Martin Gardner's column. I have a memory, that may of course be a confabulation, of seeing a sketch of the 3-by-3 block proof in one of those columns. I certainly knew the 3-by-3 proof by 1973 or 1974 at the latest.
On Mon, Dec 5, 2011 at 12:55 PM, Richard Guy <rkg@cpsc.ucalgary.ca <http://gosper.org/webmail/src/compose.php?send_to=rkg%40cpsc.ucalgary.ca>> wrote:
Allan & others,> Winning Ways was written some time ago, especially> some parts of it. I would be interested to learn the reference> to any ``earlier proof''. R.>>> On Mon, 5 Dec 2011, Allan Wechsler wrote:>> Why did Winning Ways use the very profligate Garden of Eden proof,>> featuring 5-by-5 subsquares, instead of the earlier proof (I think it was>> featured in a Mathematical Games column), which has much smaller numbers>> and uses 3-by-3 subsquares?>>>> The older proof demonstrates very handily that a Garden of Eden exists in>> a>> 42-by-42 square. (The key inequality is that 140^196 < 2^1404.) Why the>> elaborate construction with 5-by-5 subsquares, which doesn't achieve>> crossover until the square measures in the billions of cells on a side?>>>> When I was in high school sometime around 1972, I went to see John Conway>> talk either at Wayne State University or the University of Michigan. I>> have a very clear memory of him sketching the proof with the 3-by-3>> subsquares.>>>> On Mon, Dec 5, 2011 at 3:29 AM, Bill Gosper <billgosper@gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> wrote:>>>> rcs>>>>>>> I think the original counting argument was Moore's, and it easily>>> applied directly to Life. However, there's an easy example of a GOE>>> from the counting argument: The argument shows that there's some>>> GOE pattern, of size < a computable number N. To make the argument>>> constructive, just make up a supersize pattern, with all possible>>> patterns of size N.>>>>>> Wrt showing Louiville numbers are transcendental:>>> Use the example L = sum 10 ^ (- N!).>>> In this special case, it's not too hard to check that>>> L defeats any prospective polynomial.>>>>>> Rich>>>>>> --->>> Quoting Allan Wechsler <acwacw@gmail.com <http://gosper.org/webmail/src/compose.php?send_to=acwacw%40gmail.com>>>> <http://gosper.org/webmail/**src/compose.php?send_to=**>>> acwacw%40gmail.com<http://gosper.org/webmail/src/compose.php?send_to=acwacw%40gmail.com>>>>
:>>>>>>> This is the one I've been trying to remember. Thank you, Alon.>> This>>>>>>> also reminds me of the proof that the Game of Life has a finite Garden>>>> of>>> Eden pattern. (Since the original proof, many explicit predecessorless>>>> patterns have been found.) It depends on counting possible predecessors>>>> and shows that for a certain class of patterns, the number of candidate>>>> predecessors is smaller than the number of patterns, so one of that>>> class>>>> must lack a predecessor. The class is astronomically large, though, and>>>> the counting argument gives no hints about how to find an example.>>> <...>>>>>>><http://www.tweedledum.com/rwg/goe.htm>>>> --rwg
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun