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 -----