*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> 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> 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>
:
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<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<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
______________________________**_________________
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>