I read this, and it is, unfortunately, not the discussion of the proof that I remembered. Could it have been that Conway presented the proof at the talk I went to? I know it was discussed. His "parlor trick" around then was to challenge people to draw Life patterns, and he would construct a predecessor. He was uncannily good at it. On Mon, Dec 5, 2011 at 2:40 PM, Hans Havermann <gladhobo@teksavvy.com>wrote:
Allan Wechsler:
*Winning Ways* came out in 1982, more than a decade after the original
flurry of Life columns in Martin Gardner's column.
The Game of Life, Part II was in the February 1972 issue of Scientific American. Copying from the "Wheels, Life and other Mathematical Amusements" 1983 reproduction thereof:
"Among the notable contributions of Edward F. Moore to cellular automata theory the best-known is a technique for proving the existence of what John W. Tukey named 'Garden of Eden' patterns. These are configurations that cannot arise in a game because no preceding generation can form them. They appear only if given in the initial (zero) generation. Because such a configuration has no predecessor, it cannot be self-reproducing. I shall not describe Moore's ingenious technique because he explained it informally in an article in Scientific American (see 'Mathematics in the Biological Sciences', by Edward F. Moore; September, 1964) and more formally in a paper that is included in Burks's anthology."
"Alvy Ray Smith III, a cellular automata expert at New York University's School of Engineering and Science, found a simple application of Moore's technique to Conway's game. Consider two five-by-five squares, one with all cells empty, the other with one counter in the center. Because, in one tick, the central nine cells of both squares are certain to become identical (in this case all cells empty) they are said to be 'mutually erasable'. It follows from Moore's theorem that a Garden of Eden configuration must exist in Conway's game. Unfortunately the proof does not tell how to find such a pattern and so far none is known. It may be simple or it may be enormously complex. Using one of Moore's formulas, Smith has been able to calculate that such a pattern exists within a square of 10 billion cells on a side, which does not help much in finding one."
The book also has "The Game of Life, Part III" which serves as an addendum to the other parts and thus may contain material not previously published in Martin's column. In it, we have:
"The first Garden of Eden pattern... was found by Roger Banks in 1971. It required an enormous computer search of all possible predecessor patterns. The confining rectangle (9 x 33) holds 226 bits. The only other Garden of Eden pattern known was found by a French group in 1974, led by J. Hardouin-Duparc, at the University of Bordeaux. It is inside a rectangle of 6 x 122."
______________________________**_________________ 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>