Re: [math-fun] Request for example elementary non-constructive proofs with "witnesses"
Allan, can you sketch the 3x3 proof? 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.) --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
I'll describe two sets of configurations, A and B. Each pattern in B, if it has a predecessor at all, has one in A. But B will have more members than A, so some members of B must lack predecessors. A square of cells, 42 cells on a side, is broken up into 14^2 = 196 square blocks, each block being 3 cells on a side. Each block has a single center cell, surrounded by eight more cells. A configuration belongs to A if it fits inside the 42^2 field, and if after one generation, leaves all those center cells live. A configuration belongs to B if it fits inside the 40^2 field obtained from the first field by insetting all the edges by one, and has all the center cells live. A 3-by-3 block leaves its center cell live if the center cell was dead, and 3 peripheral cells were live, OR if the center cell was live and either 2 or 3 peripheral cells were live. Combinatorics gives us the total number of possible 3-by-3 blocks that leave their center cells live: the number is 140. (This is the only step of the proof that actually uses the rules of Life.) Therefore, set A has 140^196 configurations in it. The 40^2 field has 1600 cells in it; for a configuration to belong to set B, 196 of those cells are the original 3-by-3 centers and must be live, leaving 1404 cells that may be either alive or dead. Therefore, set B has 2^1404 configurations in it. That 140^196 < 2^1404 is left as an exercise for the reader. On Mon, Dec 5, 2011 at 4:41 PM, Bill Gosper <billgosper@gmail.com> wrote:
Allan, can you sketch the 3x3 proof? 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.) --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
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
participants (3)
-
Allan Wechsler -
Bill Gosper -
Michael Beeler