Re: [math-fun] Life's Adam & Eve
Scott wrote: << Isn't the existence of Garden of Eden configurations an easy proof of non-existence of Adam & Eve configurations?
Yes. Duhhhhhh. << FWIW, it feels like a direct Adam/Eve nonexistence proof might be simpler than a direct Garden of Eden existence proof.
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question. Consider those patterns each having an infinite sequence of ancestors. Is there a starting pattern for which every one of these eventually appears somewhere among its descendants? (Alternatively, consider each pattern that, for every N in Z+, has a sequence of N ancestors. Same question.) --Dan ________________________________________________________________________________________ It goes without saying that .
I'm not sure if I understand the question fully... I think rather than all "patterns that have an infinite sequence of ancestors", we would need to at least restrict it to patterns that do not end as a still-life [1] or oscillator[2]... Let S be the set of patterns that have an infinite sequence of ancestors. Many finite, unchanging patterns (still-lifes) are a member of S, because they can be formed by a collision of two or more gliders[3]. For example, a block[4] can be formed by colliding two gliders (see [5] for details). Each pattern containing two gliders that is an ancestor of the block pattern also belongs to S, and these are all distinct from one another. The boat [6] also belongs to S, and has a glider synthesis, therefore it also has an infinite sequence of distinct ancestors that also belong to S. If the Adam/Eve starting pattern's evolution includes any of the block predecessors, its subsequent evolution must lead to the block. But if it included any of the boat predecessors, its subsequent evolution would lead to the boat. The evolution of the pattern can only end one way, so it cannot contain both the block predecessors and the boat predecessors. The same argument works for oscillators and spaceships[7], so we have to exclude those too. And the same argument would extend to puffer trains [8] because for example a puffer train that leaves a trail of blocks will always be distinct from one that leaves a trail of boats. In fact, I think if you can find any two patterns that have a mutually exclusive forward history, they cannot both be in the forward history of the Adam/Eve pattern. [1] http://www.conwaylife.com/wiki/Still_life [2] http://www.conwaylife.com/wiki/Oscillator [3] http://www.conwaylife.com/wiki/Glider [4] http://www.conwaylife.com/wiki/Block [5] http://www.conwaylife.com/wiki/Glider_synthesis [6] http://www.conwaylife.com/wiki/Boat [7] http://www.conwaylife.com/wiki/Spaceship [8] http://www.conwaylife.com/wiki/Puffer_train On Mon, Dec 5, 2011 at 20:29, Dan Asimov <dasimov@earthlink.net> wrote:
<< FWIW, it feels like a direct Adam/Eve nonexistence proof might be simpler than a direct Garden of Eden existence proof.
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
(Alternatively, consider each pattern that, for every N in Z+, has a sequence of N ancestors. Same question.)
--Dan
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
Robert, I think that you are taking "pattern" to mean "configuration of the entire 2-d grid", while in what Dan was asking about, "pattern" means "finite rectangle with a given configuration". So if there's an "Adam and Eve" configuration, it can produce a "block" (for example, a 10x10 square that is empty except for a filled 2x2 rectangle in the center), and still produce other configurations, at other places, or at other times (the block doesn't have to exist forever for the original configuration to be considered Adam & Eve; it just has to exist at some time step; other configurations can later impinge on its space. You can build a turing-complete computer out of life, which can therefore enumerate all the configurations. The question is whether you can then produce them all, which is sort of like adding a printer to the computer. I suspect you could augment the computer by something that could generate gliders at arbitrary offsets and collide them, so if that's true, the question is whether any finite configuration that has ancestors infinitely far in the past can be produced by some combination of intersecting gliders. Andy On Tue, Dec 6, 2011 at 1:17 AM, Robert Munafo <mrob27@gmail.com> wrote:
I'm not sure if I understand the question fully... I think rather than all "patterns that have an infinite sequence of ancestors", we would need to at least restrict it to patterns that do not end as a still-life [1] or oscillator[2]...
Let S be the set of patterns that have an infinite sequence of ancestors.
Many finite, unchanging patterns (still-lifes) are a member of S, because they can be formed by a collision of two or more gliders[3]. For example, a block[4] can be formed by colliding two gliders (see [5] for details). Each pattern containing two gliders that is an ancestor of the block pattern also belongs to S, and these are all distinct from one another.
The boat [6] also belongs to S, and has a glider synthesis, therefore it also has an infinite sequence of distinct ancestors that also belong to S.
If the Adam/Eve starting pattern's evolution includes any of the block predecessors, its subsequent evolution must lead to the block. But if it included any of the boat predecessors, its subsequent evolution would lead to the boat. The evolution of the pattern can only end one way, so it cannot contain both the block predecessors and the boat predecessors.
The same argument works for oscillators and spaceships[7], so we have to exclude those too. And the same argument would extend to puffer trains [8] because for example a puffer train that leaves a trail of blocks will always be distinct from one that leaves a trail of boats.
In fact, I think if you can find any two patterns that have a mutually exclusive forward history, they cannot both be in the forward history of the Adam/Eve pattern.
[1] http://www.conwaylife.com/wiki/Still_life
[2] http://www.conwaylife.com/wiki/Oscillator
[3] http://www.conwaylife.com/wiki/Glider
[4] http://www.conwaylife.com/wiki/Block
[5] http://www.conwaylife.com/wiki/Glider_synthesis
[6] http://www.conwaylife.com/wiki/Boat
[7] http://www.conwaylife.com/wiki/Spaceship
[8] http://www.conwaylife.com/wiki/Puffer_train
On Mon, Dec 5, 2011 at 20:29, Dan Asimov <dasimov@earthlink.net> wrote:
<< FWIW, it feels like a direct Adam/Eve nonexistence proof might be simpler than a direct Garden of Eden existence proof.
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
(Alternatively, consider each pattern that, for every N in Z+, has a sequence of N ancestors. Same question.)
--Dan
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
I have seen the claim in several posts that because Life is Turing complete, you can program a "Life Computer" to enumerate all possible configurations. Is this true? If so, I have misunderstood the universality of Life for a long time. Can someone unwedge me? My understanding has always been that you must encode a computation in a specific way. The encoding may have a quite complicated (large number of life cells) representation for each symbol. I don't understand how the universality of a Life computer (constructed out of many life cells) tells us whether/how you can enumerate all life configurations. Am I just confused? Thanks. ----- Message from andy.latto@pobox.com --------- Date: Tue, 6 Dec 2011 12:51:36 -0500 From: Andy Latto <andy.latto@pobox.com> Reply-To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Life's Adam & Eve To: math-fun <math-fun@mailman.xmission.com>
Robert, I think that you are taking "pattern" to mean "configuration of the entire 2-d grid", while in what Dan was asking about, "pattern" means "finite rectangle with a given configuration". So if there's an "Adam and Eve" configuration, it can produce a "block" (for example, a 10x10 square that is empty except for a filled 2x2 rectangle in the center), and still produce other configurations, at other places, or at other times (the block doesn't have to exist forever for the original configuration to be considered Adam & Eve; it just has to exist at some time step; other configurations can later impinge on its space.
You can build a turing-complete computer out of life, which can therefore enumerate all the configurations. The question is whether you can then produce them all, which is sort of like adding a printer to the computer. I suspect you could augment the computer by something that could generate gliders at arbitrary offsets and collide them, so if that's true, the question is whether any finite configuration that has ancestors infinitely far in the past can be produced by some combination of intersecting gliders.
Andy
On Tue, Dec 6, 2011 at 1:17 AM, Robert Munafo <mrob27@gmail.com> wrote:
I'm not sure if I understand the question fully... I think rather than all "patterns that have an infinite sequence of ancestors", we would need to at least restrict it to patterns that do not end as a still-life [1] or oscillator[2]...
Let S be the set of patterns that have an infinite sequence of ancestors.
Many finite, unchanging patterns (still-lifes) are a member of S, because they can be formed by a collision of two or more gliders[3]. For example, a block[4] can be formed by colliding two gliders (see [5] for details). Each pattern containing two gliders that is an ancestor of the block pattern also belongs to S, and these are all distinct from one another.
The boat [6] also belongs to S, and has a glider synthesis, therefore it also has an infinite sequence of distinct ancestors that also belong to S.
If the Adam/Eve starting pattern's evolution includes any of the block predecessors, its subsequent evolution must lead to the block. But if it included any of the boat predecessors, its subsequent evolution would lead to the boat. The evolution of the pattern can only end one way, so it cannot contain both the block predecessors and the boat predecessors.
The same argument works for oscillators and spaceships[7], so we have to exclude those too. And the same argument would extend to puffer trains [8] because for example a puffer train that leaves a trail of blocks will always be distinct from one that leaves a trail of boats.
In fact, I think if you can find any two patterns that have a mutually exclusive forward history, they cannot both be in the forward history of the Adam/Eve pattern.
[1] http://www.conwaylife.com/wiki/Still_life
[2] http://www.conwaylife.com/wiki/Oscillator
[3] http://www.conwaylife.com/wiki/Glider
[4] http://www.conwaylife.com/wiki/Block
[5] http://www.conwaylife.com/wiki/Glider_synthesis
[6] http://www.conwaylife.com/wiki/Boat
[7] http://www.conwaylife.com/wiki/Spaceship
[8] http://www.conwaylife.com/wiki/Puffer_train
On Mon, Dec 5, 2011 at 20:29, Dan Asimov <dasimov@earthlink.net> wrote:
<< FWIW, it feels like a direct Adam/Eve nonexistence proof might be simpler than a direct Garden of Eden existence proof.
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
(Alternatively, consider each pattern that, for every N in Z+, has a sequence of N ancestors. Same question.)
--Dan
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- End message from andy.latto@pobox.com -----
As was pointed out earlier, this interpretation cannot be right because we know that there are many configurations without predecessors; in fact, *most * configurations lack predecessors. Life is universal in the computational sense. Indeed, the computation must be encoded; the researchers who proved Life's computational universality picked an encoding to make the proof as easy as possible. I think they emulated tag automata, which were previously known to be universal. On Tue, Dec 6, 2011 at 4:36 PM, <mbgreen@cis.upenn.edu> wrote:
I have seen the claim in several posts that because Life is Turing complete, you can program a "Life Computer" to enumerate all possible configurations. Is this true? If so, I have misunderstood the universality of Life for a long time. Can someone unwedge me? My understanding has always been that you must encode a computation in a specific way. The encoding may have a quite complicated (large number of life cells) representation for each symbol. I don't understand how the universality of a Life computer (constructed out of many life cells) tells us whether/how you can enumerate all life configurations. Am I just confused? Thanks. ----- Message from andy.latto@pobox.com --------- Date: Tue, 6 Dec 2011 12:51:36 -0500 From: Andy Latto <andy.latto@pobox.com> Reply-To: math-fun <math-fun@mailman.xmission.com**> Subject: Re: [math-fun] Life's Adam & Eve To: math-fun <math-fun@mailman.xmission.com**>
Robert, I think that you are taking "pattern" to mean "configuration
of the entire 2-d grid", while in what Dan was asking about, "pattern" means "finite rectangle with a given configuration". So if there's an "Adam and Eve" configuration, it can produce a "block" (for example, a 10x10 square that is empty except for a filled 2x2 rectangle in the center), and still produce other configurations, at other places, or at other times (the block doesn't have to exist forever for the original configuration to be considered Adam & Eve; it just has to exist at some time step; other configurations can later impinge on its space.
You can build a turing-complete computer out of life, which can therefore enumerate all the configurations. The question is whether you can then produce them all, which is sort of like adding a printer to the computer. I suspect you could augment the computer by something that could generate gliders at arbitrary offsets and collide them, so if that's true, the question is whether any finite configuration that has ancestors infinitely far in the past can be produced by some combination of intersecting gliders.
Andy
On Tue, Dec 6, 2011 at 1:17 AM, Robert Munafo <mrob27@gmail.com> wrote:
I'm not sure if I understand the question fully... I think rather than all "patterns that have an infinite sequence of ancestors", we would need to at least restrict it to patterns that do not end as a still-life [1] or oscillator[2]...
Let S be the set of patterns that have an infinite sequence of ancestors.
Many finite, unchanging patterns (still-lifes) are a member of S, because they can be formed by a collision of two or more gliders[3]. For example, a block[4] can be formed by colliding two gliders (see [5] for details). Each pattern containing two gliders that is an ancestor of the block pattern also belongs to S, and these are all distinct from one another.
The boat [6] also belongs to S, and has a glider synthesis, therefore it also has an infinite sequence of distinct ancestors that also belong to S.
If the Adam/Eve starting pattern's evolution includes any of the block predecessors, its subsequent evolution must lead to the block. But if it included any of the boat predecessors, its subsequent evolution would lead to the boat. The evolution of the pattern can only end one way, so it cannot contain both the block predecessors and the boat predecessors.
The same argument works for oscillators and spaceships[7], so we have to exclude those too. And the same argument would extend to puffer trains [8] because for example a puffer train that leaves a trail of blocks will always be distinct from one that leaves a trail of boats.
In fact, I think if you can find any two patterns that have a mutually exclusive forward history, they cannot both be in the forward history of the Adam/Eve pattern.
[1] http://www.conwaylife.com/**wiki/Still_life<http://www.conwaylife.com/wiki/Still_life>
[2] http://www.conwaylife.com/**wiki/Oscillator<http://www.conwaylife.com/wiki/Oscillator>
[3] http://www.conwaylife.com/**wiki/Glider<http://www.conwaylife.com/wiki/Glider>
[4] http://www.conwaylife.com/**wiki/Block<http://www.conwaylife.com/wiki/Block>
[5] http://www.conwaylife.com/**wiki/Glider_synthesis<http://www.conwaylife.com/wiki/Glider_synthesis>
[6] http://www.conwaylife.com/**wiki/Boat<http://www.conwaylife.com/wiki/Boat>
[7] http://www.conwaylife.com/**wiki/Spaceship<http://www.conwaylife.com/wiki/Spaceship>
[8] http://www.conwaylife.com/**wiki/Puffer_train<http://www.conwaylife.com/wiki/Puffer_train>
On Mon, Dec 5, 2011 at 20:29, Dan Asimov <dasimov@earthlink.net> wrote:
<<
FWIW, it feels like a direct Adam/Eve nonexistence proof might be simpler than a direct Garden of Eden existence proof.
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
(Alternatively, consider each pattern that, for every N in Z+, has a sequence of N ancestors. Same question.)
--Dan
--
Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com ______________________________**_________________ 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>
-- Andy.Latto@pobox.com
______________________________**_________________ 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>
----- End message from andy.latto@pobox.com -----
______________________________**_________________ 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>
On Tue, Dec 6, 2011 at 4:36 PM, <mbgreen@cis.upenn.edu> wrote:
I have seen the claim in several posts that because Life is Turing complete, you can program a "Life Computer" to enumerate all possible configurations. Is this true? If so, I have misunderstood the universality of Life for a long time. Can someone unwedge me? My understanding has always been that you must encode a computation in a specific way. The encoding may have a quite complicated (large number of life cells) representation for each symbol. I don't understand how the universality of a Life computer (constructed out of many life cells) tells us whether/how you can enumerate all life configurations. Am I just confused?
I think you are correct. When I say that a Life computer could "enumerate all finite life configurations", I mean that it could enumerate them in symbolic form, which would need to be decoded. Translating this symbolic form into an actual realization of the configuration is what I was referring to as producing a "printer" for the computer. Thinking about it a bit more, To produce all produceable configurations (those with ancestors arbitrarily far back in time), I don't think the right approach would be "for each configuration, try to find a configuration of gliders that will produce it"; this sounds like a uncomputable task. Instead, we could have the Life Turing machine enumerate all the configurations of gliders, and try them all. Except that it would have to exclude those configurations that would destroy the computer, and that may be an insoluble problem. If we only cared about keeping the computer alive for a finite amount if time, the Life-Turing-machine could simulate the glider configuration, and only actually execute it if simulation proved that it didn't destroy the computer in that amount of time. But since we want to produce all of the infinitely many configurations, we want to keep the computer alive forever, and I suspect that the question "Will this life configuration over here ever reach this spot over here?" is uncomputable. So I'm not sure an Adam & Eve configuration exists, or at any rate, this angle of attack will succeed in proving that it does. Andy
Thanks. ----- Message from andy.latto@pobox.com --------- Date: Tue, 6 Dec 2011 12:51:36 -0500 From: Andy Latto <andy.latto@pobox.com> Reply-To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Life's Adam & Eve To: math-fun <math-fun@mailman.xmission.com>
Robert, I think that you are taking "pattern" to mean "configuration of the entire 2-d grid", while in what Dan was asking about, "pattern" means "finite rectangle with a given configuration". So if there's an "Adam and Eve" configuration, it can produce a "block" (for example, a 10x10 square that is empty except for a filled 2x2 rectangle in the center), and still produce other configurations, at other places, or at other times (the block doesn't have to exist forever for the original configuration to be considered Adam & Eve; it just has to exist at some time step; other configurations can later impinge on its space.
You can build a turing-complete computer out of life, which can therefore enumerate all the configurations. The question is whether you can then produce them all, which is sort of like adding a printer to the computer. I suspect you could augment the computer by something that could generate gliders at arbitrary offsets and collide them, so if that's true, the question is whether any finite configuration that has ancestors infinitely far in the past can be produced by some combination of intersecting gliders.
Andy
On Tue, Dec 6, 2011 at 1:17 AM, Robert Munafo <mrob27@gmail.com> wrote:
I'm not sure if I understand the question fully... I think rather than all "patterns that have an infinite sequence of ancestors", we would need to at least restrict it to patterns that do not end as a still-life [1] or oscillator[2]...
Let S be the set of patterns that have an infinite sequence of ancestors.
Many finite, unchanging patterns (still-lifes) are a member of S, because they can be formed by a collision of two or more gliders[3]. For example, a block[4] can be formed by colliding two gliders (see [5] for details). Each pattern containing two gliders that is an ancestor of the block pattern also belongs to S, and these are all distinct from one another.
The boat [6] also belongs to S, and has a glider synthesis, therefore it also has an infinite sequence of distinct ancestors that also belong to S.
If the Adam/Eve starting pattern's evolution includes any of the block predecessors, its subsequent evolution must lead to the block. But if it included any of the boat predecessors, its subsequent evolution would lead to the boat. The evolution of the pattern can only end one way, so it cannot contain both the block predecessors and the boat predecessors.
The same argument works for oscillators and spaceships[7], so we have to exclude those too. And the same argument would extend to puffer trains [8] because for example a puffer train that leaves a trail of blocks will always be distinct from one that leaves a trail of boats.
In fact, I think if you can find any two patterns that have a mutually exclusive forward history, they cannot both be in the forward history of the Adam/Eve pattern.
[1] http://www.conwaylife.com/wiki/Still_life
[2] http://www.conwaylife.com/wiki/Oscillator
[3] http://www.conwaylife.com/wiki/Glider
[4] http://www.conwaylife.com/wiki/Block
[5] http://www.conwaylife.com/wiki/Glider_synthesis
[6] http://www.conwaylife.com/wiki/Boat
[7] http://www.conwaylife.com/wiki/Spaceship
[8] http://www.conwaylife.com/wiki/Puffer_train
On Mon, Dec 5, 2011 at 20:29, Dan Asimov <dasimov@earthlink.net> wrote:
<< FWIW, it feels like a direct Adam/Eve nonexistence proof might be simpler than a direct Garden of Eden existence proof.
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
(Alternatively, consider each pattern that, for every N in Z+, has a sequence of N ancestors. Same question.)
--Dan
--
Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- End message from andy.latto@pobox.com -----
-- Andy.Latto@pobox.com
Andy Latto: ... Except that it would have to exclude those configurations that woulddestroy the computer ... That's not right. The Turing machine part of the Life array must be isolated from the Life pattern array being represented. That is, the Turing machine tape is separate from the Turing machine CPU. If the Life implementation of the Turing machine does secure its CPU and firmware from corruption by the data being processed, than you don't have a proper Turing machine. I trust that the proof of the universality of Life that the Life hackers provided decades ago meets this requirement. -- Gene
Whoops .... I left out a "not". Here it is corrected.
________________________________ From: Eugene Salamin <gene_salamin@yahoo.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, December 6, 2011 4:07 PM Subject: Re: [math-fun] Life's Adam & Eve
Andy Latto:
... Except that it would have to exclude those configurations that would destroy the computer ...
That's not right. The Turing machine part of the Life array must be isolated from the Life pattern array being represented. That is, the Turing machine tape is separate from the Turing machine CPU. If the Life implementation of the Turing machine does not secure its CPU and firmware from corruption by the data being processed, then you don't have a proper Turing machine. I trust that the proof of the universality of Life that the Life hackers provided decades ago meets this requirement.
-- Gene
Yes, Andy, that makes more sense. Thank you. I've been thinking about this today and I eventually figured out that's what it must be. So the question is about a finite pattern which, if run long enough, will eventually contain every other "eligible" finite pattern. Each eligible finite pattern could be found somewhere within a portion of some future generation of the "Adam and Eve"'s evolution. Eligible patterns are, as described before, those which have ancestors going back arbitrarily (or "infinitely") many generations. (Of course, if you allowed the "Adam and Eve" configuration to be infinite, then it can contain all finite patterns, so clearly that wasn't the question.) My glider collision idea isn't too important, and I think it restricts the thought too much. I think the universal computer with a "printer" idea has a lot of promise. Perhaps someone can prove that the universal computer with a "printer" is necessary, then someone else can prove that a "universal printer" is impossible. It also invites a philosophical approach referencing the brain-in-a-vat argument [1]. If the Life pattern exists in a representation inside the Turing machine, who's to say it is any "less real" than the actual Life pattern that would be produced by the "printer"? Perhaps we don't need to print out the patterns to say we have generated them. In that case, a suitable binary counter[2] is our "Adam and Eve" configuration. [1] http://en.wikipedia.org/wiki/Simulation_hypothesis [2] http://www.conwaylife.com/forums/viewtopic.php?f=2&t=337#p1884 On Tue, Dec 6, 2011 at 12:51, Andy Latto <andy.latto@pobox.com> wrote:
Robert, I think that you are taking "pattern" to mean "configuration of the entire 2-d grid", while in what Dan was asking about, "pattern" means "finite rectangle with a given configuration". [...]
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
Good point. Now let me make a feeble attempt to rescue the Adam & Eve question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
That is a ludicrously difficult question to solve; it may even be undecidable. For the special case where 'pattern having an infinite sequence of ancestors' is replaced with 'pattern with a finite well-spaced glider synthesis', the answer is yes. Sincerely, Adam P. Goucher
Oh, I see where you're going Adam: because of the halting problem [1], we cannot know if a machine like the the Fermat Prime Calculator [2] ever terminates in a finite pattern. But I think Dan was asking something more like this: Is there a finite-sized pattern AE (for "Adam and Eve") whose evolution eventually includes all other finite-sized Life patterns, except those that have no ancestors ("orphans", "grandfatherless", etc. patterns). If so, then for every pattern P, there would be a number N such that the Nth generation of AE is (or contains) the pattern P. - Robert [1] http://en.wikipedia.org/wiki/Halting_problem [2] http://www.conwaylife.com/wiki/Fermat_prime_calculator On Tue, Dec 6, 2011 at 02:56, Adam P. Goucher <apgoucher@gmx.com> wrote:
Good point. Now let me make a feeble attempt to rescue the Adam & Eve
question.
Consider those patterns each having an infinite sequence of ancestors.
Is there a starting pattern for which every one of these eventually appears somewhere among its descendants?
That is a ludicrously difficult question to solve; it may even be undecidable.
For the special case where 'pattern having an infinite sequence of ancestors' is replaced with 'pattern with a finite well-spaced glider synthesis', the answer is yes.
Sincerely,
Adam P. Goucher
______________________________**_________________ 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>
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
participants (7)
-
Adam P. Goucher -
Allan Wechsler -
Andy Latto -
Dan Asimov -
Eugene Salamin -
mbgreen＠cis.upenn.edu -
Robert Munafo