Re: [math-fun] Request for example elementary non-constructive proofs with "witnesses"
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>>:
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. <...>
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>>:
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
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>>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
*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>
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."
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>
participants (4)
-
Allan Wechsler -
Bill Gosper -
Hans Havermann -
Richard Guy