Re: Garden of Eden positions in Life: Was: Re: game of life question

On Jul 31, 10:56 pm, David Bernier <david...@xxxxxxxxxxxx> wrote:
|What strikes me as unusual is that the population is infinite. I
don't
|remember
|seeing discussions of infinite populations in, for instance, Martin
|Gardner's _Mathematical Games_ columns.

I thought there was a discussion of the kind of debris
generated by configurations that differed from infinite
diagonals such as {(x,y) : x=y} in finitely many cells.
I think it was pointed out that the diagonal by itself
is stable, but if you perturb it by adding a live cell
adjacent to it, it unravels. Of course I think it also
mentioned that the configuration could be kept stable
while cutting it down to finite, by replacing it with
{(-n,-n-1),(-n+1,-n-1),(n+1,n),(n+1,n-1)} u
{(x,y) : -n<=x=y<=n}.

I thought the discussion of what happens to long lines
{(x,y) : x=0 and 0<=y<n} included a mention of what
happens to the infinite line {(x,y) : x=0}, but it's
been a really long time since I read that column.

Infinite configurations can be thought of as limits
of finite configurations. The finite configurations
are a countable set, and in a suitable metric, the
full set of configurations is the metric completion
of the set of finite configurations. The evolution
takes finite configurations to finite configurations,
and it extends by continuity to the full set of
configurations.

|I find finite populations more natural...

Do rational numbers strike you as more natural than
real numbers? It seems to me that the analogy
rational numbers : real numbers ::
finite configurations : infinite configurations
has some validity to it.

Being infinite doesn't necessarily mean that they're
complicated. It's easy to see that the infinite
diagonal is stable. Finding a way to tie off the
ends of a long but finite diagonal to make it
stable requires a little tinkering. It's a bit
like proving that a certain mapping with an
obvious real fixed-point also has rational
fixed-points arbitrarily close to it.

The glider gun is an example of a state that
approaches a periodic limit, where the limiting
cycle consists of infinite configurations.

All the infinite configurations I remember being
mentioned are definable in Presburger arithmetic,
i.e., first-order arithmetic with just <, +. I
guess generalized to include negative numbers.
To put it in a less esoteric way, they're all
definable using linear equations and inequalities
in x and y and congruences mod fixed numbers,
combined with the boolean operations "and", "or"
and "not". In a sense, then, they're all
relatively elementary.

If there is an infinite garden-of-Eden, then
by a compactness argument, its restriction to
[-n,n]x[-n,n] for large enough n is also a
garden-of-Eden.

If a state can be regressed m generations for
each m>0, does that guarantee that it is
timeless? If it can't be regressed by m, then
its restriction to [-n,n]x[-n,n] for large
enough n also can't be. Probably more
difficult: if a configuration is timeless,
are sufficiently large finite restrictions
also?

Keith Ramsay

.

Relevant Pages

  • Re: Garden of Eden positions in Life: Was: Re: game of life question
    ... |What strikes me as unusual is that the population is infinite. ... of finite configurations. ... |I find finite populations more natural... ...
    (sci.math)
  • Re: game of life question
    ... L. Conway's game of life determines a mapping T from P to ... These are usually called "stable configurations". ... configuration is automatically ageless. ... But if we allow an infinite grid, then it's clear there are other ...
    (sci.math)
  • Elaborate Cooling Schedule - Simulated Annealing
    ... cooling schedules in simulated annealing. ... for terminating temperature in the cooling schedule proposed by Lundy ... If my rule for obtaining new configurations from the older ones at any ... [0, 1), isn't the cardinal value of R, infinite in such case? ...
    (sci.math)
  • Re: game of life question
    ... These are usually called "stable configurations". ... ancestry of infinite length. ... In that case, of course stable configurations have such an ancestry, ... A "timeless" configuration is never a Garden of Eden configuration; ...
    (sci.math)
Quantcast