Difference between revisions of "Lifeline Volume 6"
(vol 6 page 1 (better than vol 10 page 1 here)) |
(pp 4- 5) |
||
Line 158: | Line 158: | ||
EN: the_* are empty cells. | EN: the_* are empty cells. | ||
====Page 4==== | |||
Lifecomic by Richard Holmes of | |||
Fayetteville, N.Y. | |||
I'm a real son of a Gun! | |||
Lifecomic by Traw | |||
pant, pant. | |||
Excursions Into the Universe of '3-4' Life . . . | |||
Into the foreseeable future, this variation to Conway's basic rules | |||
will probably hold and sustain more interest than any other variation | |||
yet reported. Several developments in 3-4 Life since its first introduction | |||
in issue Number Four (Page 8) make it as interesting as regular | |||
Life during its earlier stages. Here are a few: | |||
James B. Shearer of Livermore, Ca. has discovered | |||
several still life forms other than the block | |||
(see No.4,p.8)! The object on the right is one | |||
of these new surprising discoveries. | |||
Paul Dietz or Ellicott City, Md. reports the | |||
two oscillators shown below in this interesting | |||
variation on Life. | |||
Raynham has determined there are 44 different collisions involving | |||
pairs of the period three orthogonal spaceship (see No.5,p.5). One | |||
of the more interesting results is shown below. | |||
"diamond ring" | |||
period 4 oscillator | |||
in 4 generations | |||
generation 7 | |||
Lifequotes | |||
'If it were possible to spend one hour with Albert Einstein, I would | |||
use my share of that hour to introduce and explain Life.' | |||
. . . an anonomous <!--original spellin--> Lifenthusiast. | |||
Editor's Errors_and Embarrassment . . . | |||
On page six of LIFELINE Number Five Answers to Reader Exercises 5.1, | |||
c. should read: The dented row of bits forms two beehives and a blinker | |||
after fourteen moves. | |||
====Page 5==== | |||
Reader Article . . . | |||
ON THE GARDEN-OF-EDEN THEOREM<br> | |||
by<br> | |||
Frank Bernhart, Kansas State University | |||
It is remarkable that several years before Conway invented the | |||
"Life" game, Edward F. Moore proved a theorem showing that certain types | |||
of cellular automata must have Garden-of-Eden configurations, and although | |||
this proof applied to "Life", no example was known for some time. | |||
The theorem has been strengthened by John Myhill, and now provides a | |||
complete criterion for the existence of GOE's. Both results are collected | |||
in ESSAYS ON CELLULAR AUTOMATA, edited by Arthur W. Burks (U. of Ill. | |||
Press, 1970). The argument underlying the Moore-Myhill criterion is not | |||
basically hard to follow, and this article presents a brief exposition | |||
for readers of Life-Line. | |||
To avoid tangling with a number of discrepancies that exist between | |||
the two results, the terminology here is redefined and the argument reworded. | |||
Readers interested in the original definitions should refer to | |||
the papers. | |||
For definiteness, four properties of cellular automata are stated. | |||
(a) The space of the automaton is an infinite cellular square array. | |||
(b) Changes occur in discrete time steps, and each step is called a | |||
generation. | |||
(c) The change in each cell occurs simultaneously, and depends on a | |||
universal rule that only takes into account the contents of that cell | |||
and its neighbors. | |||
(d) The rule is deterministic, hence each pattern has precisely one | |||
successor, although a pattern may have none, one or more than one | |||
predecessor ('father'). | |||
In physics space is said to be homogeneous if the natural laws | |||
treat all the points alike, and anisotropic if all directions at a point | |||
are treated alike. The universality of the rule means that our automata | |||
are homogeneous in the discrete sense, or that a sequence of generations | |||
is unchanged if the entire pattern is shifted to the right, the left, | |||
up, or down. We do not care about anisotropy, but Conway's game is | |||
anistropic in the sense that rotation of the pattern 90° or reflection | |||
does not alter the rule. In short, the rule retains all the symetry | |||
originally possessed by the infinite square array. | |||
Define a Garden-of-Eden or GOE pattern to be any pattern which is | |||
not the successor of any other pattern, or in other words cannot be | |||
any generation of a sequence other than the first or 0-generation. In | |||
"Life" a finite pattern may be called a GOE, but with the understanding | |||
that the rest of space is in a blank state. A blank state is defined | |||
as a state which remains the same when it is surrounded by identical | |||
states --- we will assume there is at most one blank state. Because | |||
the existence theorem is not limited to automata possessing a blank | |||
state, we need a way to refer to finite patterns that doesn't depend | |||
on blank states. Let us employ the word orphan ( a term due to Conway) | |||
to mean any finite pattern with the property that any total pattern | |||
including it must be a GOE. | |||
...to be continued... | ...to be continued... |
Revision as of 18:04, 4 March 2010
Lifeline Volume 6 | ||
Published in | October 1972 | |
---|---|---|
Preceded by | Volume 5 | |
Succeeded by | Volume 7 |
This page is a transcript of Volume 6 of the Lifeline newsletter |
---|
This article may contain spelling mistakes and/or errors that will not be corrected -- it is preserved in this way for history's sake |
A QUARTERLY NEWSLETTER FOR ENTHUSIASTS OF JOHN CONWAY'S GAME OF LIFE O OOOOO OOOOO OOOOO O OOOOO O O OOOOO O O O O O O OO O O O O OOO OOO O O O O O OOO O O O O O O O OO O OOOOO OOOOO O OOOOO OOOOO OOOOO O O OOOOO• Editor and Publisher: Robert T. Wainwright •NUMBER 6OCTOBER 1972
A QUARTERLY NEWSLETTER FOR ENTHUSIASTS OF JOHN CONWAY'S GAME OF LIFE O OOOOO OOOOO OOOOO O OOOOO O O OOOOO O O O O O O OO O O O O OOO OOO O O O O O OOO O O O O O O O OO O OOOOO OOOOO O OOOOO OOOOO OOOOO O O OOOOO Number 6 OCTOBER 1972• Editor and Publisher: Robert T. Wainwright •
Page 1
Only one day before picking up the freshly printed copies of LIFELINE Number Five I received a letter from JHC himself describing several new conjectures which he put forth regarding Life. I immediately prepared a short note describing one of the conjectures, 'The Grandfather Problem' for insertion into each of the newsletters which were about to be sealed for mailing.
I would now like to further elaborate upon that small note inserted into LIFELINE Number Five and also present another of Conway's amazing conjectures.
The Grandfather Problem: here is a problem that as Conway says seems
compIeteIy untouchabIe - even the Moore type argument fails completely.*
Is there a configuration which has a father but no grandfather? Your
obvious ideas are most likely wrong. For instance although the pattern
below left has at least one father which is an orphan there are very
likely other fathers which are not orphans. What we are looking for
is a pattern with only orphans for fathers. Of course, we can ask
similar questions about great-grandfathers etc. Conway is offering
$50 to the first person to settle the grandfather problem either way.
tick tock
Editor's Note (EN): this is a highly artificial object.
The Unique Father Problem: Conway has posed another related problem which is the following: is there a stable configuration whose only father is itself (with some fading junk some distance away not being counted)? For example, is there any father to the 'tock' other than the 'tick' (these are the two phases of the clock shown above right)? There is and I will present all submitted in LIFELINE Number Seven next month but for some other configuration there may be no other predecessors other than itself.
Conway offers a $50 prize for this as well. All decisions for validity of proofs to be his alone, I shall forward all proofs to Conway who will act as the final arbiter of the contest.
- The reader may enjoy reading 'Mathematics in the Biological Sciences'
by Edward F. Moore in the September 1964 issue of Scientific American. Additionally, page five of this LIFELINE contains an article regarding the Moore-Myhill criterion for existance of Garden of Eden configurations.
Page 2
Class E, Evolutionaries, Exercises, Et cetera . . .
'LIFEXPLANATIONS' by Peter Raynham of Waterloo, Ontario, Canada
There are various lifeforms such as the beehive, which are small and stable. However bigger life is unstable, and tends to break down. For instance, a superbeehive, with edges of three instead of two, is unstable, and in twelve generations, it splits apart into four normal beehives. A superblinker also is unstable, and in six generations, becomes four normal size blinkers. Life can also be cross bred, to create new life with traits of both original objects. For example, the super-beehive produces beehives but it stabilizes. A blinker, however,oscillates, but leaves no debris. Now by combining these two objects into one, a pattern is produced which both oscillates and leaves beehives. All these are shown here:
super- beehive splits into ...
super blinker becomes ...
hybrid: super- beehive blinker
EN: interesting, any others?
Reader Briefs ...
Mark Horton of Cardiff by Sea, Ca.
notes that: the figure two forms a
beehive and block in sixteen generations
which then conservatively
interacts as described on page 15
of LIFELINE Number Three.
GENERATlON 0000 / NUMBER TWO
Christopher Scussel of Birmingham Mi.
notes that the collision of a glider
and a lightweight spaceship will in
130 generations result in a pure census
of twenty blinkers. (EN: a blinding
finish!)
SPACESHIP-GLIDER CRASH
RESULTING IN MANY BLINKERS
Class l, Still Lifes and Stable Forms . . .
Lee H. Skinner of Albuquerque,N.M. has now verified that of the still lifes there are 24 ten-bit objects, at least 40 eleven-bit objects, about 65 twelve-bit objects, about 75 thirteen-bit objects and about 100 fourteen-bit objects. Based upon this and other empirical information, several interesting generalizations have now been made regarding Life structures. These will be introduced in a later issue of LIFELINE. EN: try identifying all two dozen of the tens.
Page 3
Class II, Oscillators . . .
The cover page of LIFELINE Number Five illustrated a set of oscillators With periods of 8, 4, 3, 5, 6 2, 7, and 9.(a thru h respectively)! Excluding (a) all these were discovered and sent in by Buckingham's Combine, the prolific group who have now reported over thirtyfive new oscillators with a period greater than two! For variety the writer included (a). To insure appropriate credit and authorship I will now indicate the specific discoverer and exact name as coined by same.
Object Name Period Discoverer.
(a) 'roteightor' 8 Wainwright
(b) 'boss' 4 Buckingham
(c) 'biting off more
than they can chew' 3 Raynham
(d) 'mathematician' 5 Buckingham
(e) '$rats' 6 Buckingham
(f) 'snake pit' 2 Niemiec
(g) 'burloaferimeter' 7 Buckingham
(h) 'worker bee' 9 Buckingham
(1) 'dinner table' 12 Wainwright
EN: I have included (i)
here for completeness.
Lifeobservation by Glenn Puro of Geneva N Y
While reading The UFO Experiences A Scientific Inquiry by J. Allen Hynek, I noticed a feature of interest in Figure 7, one of the photographs following page 52. In the photograph, six images of apparently opaque objects are grouped in a formation strongly resembling the beehive of John H. Conway's game "life," instead of a line or hexagon as would seem more likely in a natural phenomenon. The only obvious way one would be led to such a pattern is by using rules to fabricate a space, as has been done in designing cellular automata. Of course, there is also the possibility that the pattern resulted from a wide, if not broad, circulation of Scientific American.
Reader Reply . . .
Regarding the 'Line-Block' Oscillator by Harry J. Riley of Trenton,N.J.
Three more oscillators residing on a 4x12 torus have been reported by Riley. The first is simply a period two flip-flop consisting of two adjacent lines (see diagram a). The second is a period four oscillator consisting of a block between two lines (see diagram b). The third is a period twelve oscillator which emulates a spaceship-wick moving west at the speed of light as was first reported in LIFELINE Number Three on page 18 (see diagram c).
EN: the_* are empty cells.
Page 4
Lifecomic by Richard Holmes of Fayetteville, N.Y. I'm a real son of a Gun!
Lifecomic by Traw pant, pant.
Excursions Into the Universe of '3-4' Life . . . Into the foreseeable future, this variation to Conway's basic rules will probably hold and sustain more interest than any other variation yet reported. Several developments in 3-4 Life since its first introduction in issue Number Four (Page 8) make it as interesting as regular Life during its earlier stages. Here are a few:
James B. Shearer of Livermore, Ca. has discovered several still life forms other than the block (see No.4,p.8)! The object on the right is one of these new surprising discoveries.
Paul Dietz or Ellicott City, Md. reports the two oscillators shown below in this interesting variation on Life.
Raynham has determined there are 44 different collisions involving pairs of the period three orthogonal spaceship (see No.5,p.5). One of the more interesting results is shown below.
"diamond ring" period 4 oscillator in 4 generations
generation 7
Lifequotes 'If it were possible to spend one hour with Albert Einstein, I would use my share of that hour to introduce and explain Life.' . . . an anonomous Lifenthusiast.
Editor's Errors_and Embarrassment . . .
On page six of LIFELINE Number Five Answers to Reader Exercises 5.1, c. should read: The dented row of bits forms two beehives and a blinker after fourteen moves.
Page 5
Reader Article . . .
ON THE GARDEN-OF-EDEN THEOREM
by
Frank Bernhart, Kansas State University
It is remarkable that several years before Conway invented the "Life" game, Edward F. Moore proved a theorem showing that certain types of cellular automata must have Garden-of-Eden configurations, and although this proof applied to "Life", no example was known for some time. The theorem has been strengthened by John Myhill, and now provides a complete criterion for the existence of GOE's. Both results are collected in ESSAYS ON CELLULAR AUTOMATA, edited by Arthur W. Burks (U. of Ill. Press, 1970). The argument underlying the Moore-Myhill criterion is not basically hard to follow, and this article presents a brief exposition for readers of Life-Line.
To avoid tangling with a number of discrepancies that exist between the two results, the terminology here is redefined and the argument reworded. Readers interested in the original definitions should refer to the papers.
For definiteness, four properties of cellular automata are stated.
(a) The space of the automaton is an infinite cellular square array.
(b) Changes occur in discrete time steps, and each step is called a generation.
(c) The change in each cell occurs simultaneously, and depends on a universal rule that only takes into account the contents of that cell and its neighbors.
(d) The rule is deterministic, hence each pattern has precisely one successor, although a pattern may have none, one or more than one predecessor ('father').
In physics space is said to be homogeneous if the natural laws treat all the points alike, and anisotropic if all directions at a point are treated alike. The universality of the rule means that our automata are homogeneous in the discrete sense, or that a sequence of generations is unchanged if the entire pattern is shifted to the right, the left, up, or down. We do not care about anisotropy, but Conway's game is anistropic in the sense that rotation of the pattern 90° or reflection does not alter the rule. In short, the rule retains all the symetry originally possessed by the infinite square array.
Define a Garden-of-Eden or GOE pattern to be any pattern which is not the successor of any other pattern, or in other words cannot be any generation of a sequence other than the first or 0-generation. In "Life" a finite pattern may be called a GOE, but with the understanding that the rest of space is in a blank state. A blank state is defined as a state which remains the same when it is surrounded by identical states --- we will assume there is at most one blank state. Because the existence theorem is not limited to automata possessing a blank state, we need a way to refer to finite patterns that doesn't depend on blank states. Let us employ the word orphan ( a term due to Conway) to mean any finite pattern with the property that any total pattern including it must be a GOE.
...to be continued...