Une suite pour la Vie
(doublée d’une correspondance passionnante avec
Dean Hickerson)
Une suite de nombres
en rapport avec le Jeu de la
Vie : celle de ceux qui disparaissent
quand on leur soumet la loi d’airain des naissances et des morts. Pour trouver
ces nombres, il faut d’abord en fixer l’aspect. Voici l’alphabet retenu, il se
compose des dix chiffres obtenus en noircissant les cases ad hoc d’un rectangle 3 x 5 :
xxx
x xxx xxx
x x xxx xxx
xxx xxx xxx
x x
x x x
x x x x
x x x x x
x x
x xxx xxx
xxx xxx xxx
x xxx xxx
x x
x x x
x x x x
x x x x
xxx
x xxx
xxx x xxx
xxx x xxx
xxx
0 1
2 3 4
5 6 7
8 9
On séparera d’une
case les chiffres à l’intérieur des nombres, puis on les injectera dans une applet du type de celle qui figure en
bas de page. Le résultat, après quelques générations, est toujours l’un des
trois suivants :
- disparition de la
population de départ ;
- croissance infinie
(par dissémination de vaisseaux, par exemple) ;
- stabilisation.
Pour le cas qui nous
occupe – le devenir des nombres –,
tout dépend de la typographie utilisée, bien sûr. Nous avons dessiné les
chiffres du haut de la manière la plus courante possible (cf. les divers affichages digitaux,
pendulettes, réveils-matin, lecteurs de DVD, etc.) – mais d’autres
façons de faire sont envisageables, lesquelles produiront d’autres résultats.
Voici plusieurs dessins du 1, du 4 ou du 7 (nous
avons retenu le 1b, le 4c, le 7b) :
xx x x
x x x xxx
xxx
x x
x x x x
x x x
x x
xxx x x xxx
xx x
x x
x xxx x
x x
xxx x x x
x x x
1a 1b
4a 4b 4c
7a 7b
Les nombres qui
disparaissent selon la graphie fixée tout en haut, sont :
8,10,11,14,18,20,31,48,50,81,83,87,88,101,118,122,127,144,148,155,157,161,174,181,188,191,199,202,205,206,208,218,221,228,245,
...
Cette suite est-elle
finie ? Il est en effet concevable qu’elle s’arrête à partir d’un certain
nombre, très grand, lequel ferait « exploser » la population initiale
de points, envoyant des vaisseaux dans tous les sens, produisant des kyrielles
de clignotants ou de blocs fixes – mais ne s’effondrant plus jamais sur
elle-même...
Dean Hickerson, de la liste SeqFan,
a montré qu’il n’en est rien et qu’il y aura toujours moyen de prolonger la
suite et de trouver des nombres qui disparaissent.
Eric Angelini asked:
> If we represent the ten digits like
this (in a 5x3 box):
...
> ... the integers which disappear in
the "Game of Life" are listed hereafter
> (two digits,
inside an integer, are always separated by one space):
>
>
8,10,14,18,20,31,48,50,81,83,87,88,101,118,122,127,144,148,155,157,161,174,
> 181,188,191,199...
>
> Is the sequence finite?
No. For example, numbers of the form 1811...1181
all die in 5 generations.
Just to clarify, we're using a variable
width font, with "1" being narrower
than the other digits; e.g. 1811181 is:
o ooo o o o ooo o
o o o o o o o o o
o ooo o o o ooo o
o o o o o o o o o
o ooo o o o ooo o
But even if we use a fixed-width font, the
same numbers (starting with
181181) still die, in 15 gens:
o ooo o
o o ooo o
o o o o
o o o o o
o ooo
o o o
ooo o
o o o o
o o o o o
o ooo o
o o ooo o
(Of course, I don't think this sequence
should be added to OEIS, since
it depends not only on base-10 representations, but also
on a specific
way of representing digits as Life patterns.)
Dean Hickerson
De même que les
nombres découverts par Dean (placer autant de « 1 » qu’on veut entre les bornes 1811 et
1181), il y a ceux qui commencent par « 1 » et qu’on fait suivre
d’autant de « 4 » que l’on veut (14, 144,
1444, 14444...) – ils s’évanouissent aussi, mais en 9 générations à
chaque fois.
L’applet utilisée pour produire image et
suite est ici :
http://www.math.com/students/wonders/life/life.html
[Dernière minute :
Jonathan Post vient
de m’écrire ceci en privé (7 février 2007)
(...)
By the way, Eric, I first did the lower
end of your sequence 39 years
ago in 1968 at Caltech in a language called CITRAN
(derived from JOSS)
running on dumb terminals connected to an IBM 7090/7094 which
did ALL
the
computing for all departments of Caltech plus NASA JPL!
(...)
... les beaux esprits
se rencontrent !]
[Dernière seconde :
Dean Hickerson revient
sur la question de la durée de vie des nombres-qui-meurent :
Eric, I've thought some more about about
numbers whose corresponding Life
patterns die. The numbers listed on your web page all die
within
65 generations. I wondered if there were
numbers which take longer than
that. After quite a bit of experimentation, I found that
there's no limit
on the length of time before such a pattern dies. In
particular, the
pattern for 1666225099901176 produces 2 gliders, which
annihilate each
other in generation 77:
o ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo o o ooo ooo
o o o o
o o o o o o o o o o o o o o o o o
o ooo ooo ooo ooo ooo ooo o o ooo ooo ooo o o o o o ooo
o o o o o o o o o o o o
o o o o o o o
o o o
o ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo o o o ooo
If you change the '999' to a longer string of '9's, the lifetime increases;
each additional '9' increases it by 8 generations.
I've tried to find a more interesting
example, based on a decaying fuse
formed by a string of '2's.
But the best I've found doesn't quite die;
it ends up with a population of 44. This happens for
numbers of the
form 19900222...22200661, where the number of '2's a
multiple of 3 and
>= 9.
(If you add one more '2', you end up with two blocks and two
period-3 pulsars.)
o ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo
ooo ooo ooo o
o o o o o o o o o o o
o o o
o o o o
o o o o o o o
o ooo ooo o o o o ooo ooo ooo ooo ooo ooo ooo ooo ooo o o o
o ooo ooo o
o o o o o o o o
o o o
o o o
o o o o o o o o o o o
o ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo ooo
ooo ooo ooo o
There's probably some way to modify the
ends to make this die, but I
haven't found it.
You mentioned:
> (try 137, in
the applet, it's fun !)
It's strange that a heavyweight spaceship
shows up so soon. Lightweight
and middleweight spaceships are much more common. Most of
the ones I've
seen come from large messy patterns (e.g. 1044, 2310,
2848), but 3207
produces a LWSS by itself, and 12739 makes a MWSS plus a boat,
a beehive,
and a glider.
6854 produces a
bunch of stuff, including a pentadecathlon (period 15).
I wonder what the smallest number is whose
pattern's population goes to
infinity...
Dean Hickerson
À suivre ?]
----------------
[Oui, à suivre, effectivement ; Dean vient de m’envoyer encore
ceci :
I wrote:
> I've tried to find a more interesting
example, based on a decaying fuse
> formed by a
string of '2's. But the best I've found
doesn't quite die;
> it ends up
with a population of 44. This happens
for numbers of the
> form
19900222...22200661, where the number of '2's a multiple of 3 and
> >= 9.
It took a few days of searching, but I
finally found a way to modify the
ends so the pattern dies.
Try any number of the form
1125344743766189077900222...2220066748424
where the number of 2's in the middle is divisible by 3 and
>= 9. With
9 2's, this dies in 191 gens. Each additional group of 3 2's adds 18 to
the lifetime.
The MWSS that's formed at the left end of
that pattern can be used in
other patterns that take a long time to die. For example, try
1125344743766111...11162
where the number of 1's in the middle is at least 2. This forms a MWSS
at the left end, which destroys a block at the right
end.
Or
1125344743766111...111947742
where the number of 1's in the middle is odd. This forms a MWSS at the
left and a LWSS at the right, which annihilate each other.
Or
4147297575111...11153
with at least 4 1's.
This forms a MWSS at the left (on a different path
from the one above) which destroys a boat at the right
end.
By the way, in your original message about
this subject, you listed some
numbers whose patterns die:
8,10,14,18,20,31,48,50,81,83,87,88,101,118,122,127,144,148,155,161,
174,181,188,191,199
You missed 11 and 157. Of the 505 numbers up to 10000 which die, the
one that takes the longest is 1048, which dies in 201
gens.
Dean Hickerson
L’illu ci-dessus est désormais bonne, j’ai
corrigé la suite des nombres-qui-meurent
selon l’indication de Dean.]
Je vous encourage à entrer dans l’applet ce nombre-ci, qu’il a
trouvé :
1125344743766111111111111111111111111111947742
(il y a 27 « 1 » qui forment
bloc -- il pourrait y en avoir 29, ou 31, ou 33...)
La façon qu’à ce nombre de s’autodétruire est magnifique !
[À suivre encore ?]
----------------
[Oui ! Je reçois ceci de Dean ce matin, 20 février 2007 – c’est
toujours passionnant (notamment les
questions irrésolues du Jeu de la Vie
qu’il mentionne et que j’ai balisées d’une flèche « -->
») ; je commence par lui dire que les nombres sont
simples à expédier par courriel] :
>> The good thing with this is that
*numbers* are easy
>> to post
and to reproduce in an applet.
True, but for any really serious Life
experiments you need a faster
program, which can read and write patterns. Then you can run
some of the
larger patterns that people have built, like the ones on my
Life page:
http://www.math.ucdavis.edu/~dean/life.html
>> Doesn't the Game of Life
"sleep" a bit nowadays?
There are still several people who are
active in Life. Most of us have
other things that keep us busy, so activity is sporadic.
(...)
You can see some of the recent results on H. Koenig's blog:
http://pentadecathlon.com/lifeNews/index.php
>> This would wake a few people up,
I guess!
Maybe. But, although your number patterns
provide some fun puzzles, and
I've enjoyed playing around with them for
a while, they're not really
relevant to the big questions in Life, like:
--> What oscillator periods are possible? (Currently we
have examples of
all periods except 19, 23, 31, 34, 37, 38, 41, 43, 51, and
53.) See
Jason Summers's Game of Life Status
page:
http://entropymine.com/jason/life/status.html
--> What spaceship velocities are possible? (Currently
known:
orthogonal c/2, c/3, c/4, c/5, 2c/5, c/6, 2c/7, 17c/45;
diagonal c/4, c/5, c/6, c/12) See Jason's page for this
also.
--> What growth rates can we construct? (Currently known
includes
population in gen t asymptotic to a constant times t^r for
any
rational number r with 1 <= r <= 2. Also for r = 1/(2^k) with k>=0,
r = (k-1)/k with k>=1, and r = 1/3. Also log(t), t log(t),
log(t)^2, t log(t)^2. (I'm sure I've forgotten some.)
--> Is there a pattern which has
a parent but no grandparent? (I.e.
it can occur in gen 1 of something, but not in gen 2.) Conway
offered $50 for this back around 1970, but it's still
unanswered.
--> Can all still-lifes and oscillators be constructed by
crashing
gliders together? See Mark
Niemiec's Life Page:
http://home.interserv.com/~mniemiec/lifepage.htm
--> What is the ultimate fate of an infinite random
pattern? Does it
fill up with an ecosystem of competing self-replicators?
What is
its limiting density (if it has one)?
(...)
Here are the numbers up to 1000:
8 10 11 14 18 20 31 48 50 81 83 87 88 101 118 122 127 144 148 155 157
161 174 181 188 191 199 202 205 206 208 218 221 222 228 245 247 248 274
278 284 285 295 302 304 305 308 309 312 313 315 323 327 331 342 349 353
397 414 418 428 472 481 488 502 505 508 518 527 551 555 558 562 582 629
639 660 661 706 714 726 727 746 751 753 758 759 772 777 796 802 805 811
812 814 815 818 822 823 853 855 872 881 902 906 916 917 923 947 956 971
>> Thanks again, Dean, my right thumb is almost dead
(entering
>> the
applet lots of numbers via the mouse!)
If you switch to a Life program that can
read and write pattern files
in RLE
notation (the most common one used for exchanging patterns),
then you won't have to use the mouse so much.
>> wouldn't
it be interesting to find the smallest integer producing:
>>
>> - a pure glider
...
Here, I think, are the smallest numbers
which produce some of the small,
named objects. In some cases there are smaller numbers that
produce these
along with other things, but these are probably the
smallest that produce
just a single object. (I only checked patterns that finish
within 2000 gens.
It's possible that there are smaller
numbers which produce single objects
after more than 2000 gens, but it's unlikely; patterns that
last that long
are usually large and messy.)
aircraft carrier 186176
bakery
1672
barge
243
beacon (p2)
3671
beehive
163
blinker (p2)
29
block
70
boat
24
clock (p2)
unknown
eater 1415073803975114
fleet
7108
glider
90
honey farm
78
HWSS unknown
LWSS 3207
MWSS 94174
infinite grow
154299
loaf
60
long barge
unknown
long boat
587
long ship
unknown
long snake
unknown
mango
857
oscillator (p15)
1445481003304129144171771
pond
36
pulsar (p3)
0
ship
516
snake
unknown
still
life 180010010081
toad (p2)
8696
traffic light (p2)
1
tub
3906
In case you switch to a program that can
read RLE files, here's a pattern
containing the numbers listed above:
#C Smallest numbers which produce some
small named objects
x = 19, y = 1225, rule = B3/S23
3ob3o$2bobobo$3ob3o$o5bo$3ob3o57$3ob3o$2bobobo$2bobobo$2bobobo$2bob3o
57$3ob3ob3ob3o$2bobobobobobo$3ob3obobob3o$2bo3bobobobobo$3ob3ob3ob3o
57$3obobo$2bobobo$3ob3o$o5bo$3o3bo57$ob3ob3o$obo5bo$ob3ob3o$obobo3bo$o
b3ob3o57$3obob3o$o3bobo$3obob3o$2bobobobo$3obob3o57$3obobob3o$2bobobo
3bo$3ob3ob3o$o5bo3bo$3o3bob3o57$3ob3ob3ob3o$obobo3bobobo$3ob3ob3ob3o$o
bobobo3bobobo$3ob3ob3ob3o57$3ob3ob3obo$2bobo5bobo$3ob3o3bobo$2bobobo3b
obo$3ob3o3bobo57$ob3ob3obob3ob3o$obobobo3bo3bobo$ob3ob3obo3bob3o$obobo
bobobo3bobobo$ob3ob3obo3bob3o57$3ob3o$o3bobo$3obobo$obobobo$3ob3o57$3o
b3ob3o$o3bobo3bo$3ob3o3bo$2bobobo3bo$3ob3o3bo57$3ob3o$2bobo$3ob3o$2bob
obo$3ob3o57$3ob3ob3o$obobo5bo$3ob3o3bo$obo3bo3bo$3ob3o3bo57$obob3o$obo
bobo$obobobo$obobobo$obob3o57$o$o$o$o$o57$3ob3o$2bobobo$2bob3o$2bobobo
$2bob3o57$3obob3ob3o$2bobobobobobo$2bobobobob3o$2bobobobobobo$2bobob3o
b3o57$3ob3o$obobobo$3obobo$2bobobo$3ob3o57$3ob3ob3ob3o$2bo3bobobo3bo$
3ob3obobo3bo$2bobo3bobo3bo$3ob3ob3o3bo57$3obobobob3obobo$obobobobo3bob
obo$3ob3obo3bob3o$2bo3bobo3bo3bo$3o3bobo3bo3bo!
Dean Hickerson
Le tableau des
« small objects » évoqués par Dean
sera mis à jour régulièrement, au fil des améliorations trouvées. La maison se
permet de recommander l’injection du nombre 154299 dans le Jeu de la Vie, produisant une expansion infinie de toute beauté (illustrée ci-dessous) :
[Dean] :
I've found a number that produces infinite
growth: 154299. I believe
it's the smallest such number. In gen 539 it produces a Corderman switch
engine (along with a lot of other junk) which travels
southeast, leaving
behind 4 blocks every 48 gens.
Quelle merveille,
bravo Dean !
Voici un dictionnaire
(en langue anglaise) qui permet de
comprendre en quoi consistent « small objects » et autres
configurations :
http://www.bitstorm.org/gameoflife/lexicon/
L’applet que nous utilisons le plus est
toujours là :
http://www.math.com/students/wonders/life/life.html
Retour à la page d’accueil du site, là