Lifeline Volume 6
| 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
Page 1
View scan of this page
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.
|
Editor's |
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
View scan of this page
| '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: | ||
| EN: interesting, any others? | ||
| 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.
GENERATION 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 |
|
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
View scan of this page
|
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. | |||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||
|
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. |
| 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). | ||
| a | b | c |
| EN: the * are empty cells. | ||
Page 4
View scan of this page
|
Lifecomic by Richard Holmes of Fayetteville, N.Y.
|
Lifecomic by Traw
|
|
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. | |
period 4 oscillator in 4 generations |
|
|
'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.
|
|
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
View scan of this page
|
ON THE GARDEN-OF-EDEN THEOREM |
|---|
|
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 symmetry 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. |
Page 6
View scan of this page
|
The possibility remains open that a GOE pattern might have no orphans at all, i.e. each finite part can occur as a successor if its environment is suitably changed. About such GOE's, if they exist, we have nothing to say --- the proof is concerned with the existence of orphans. Given an orphan the remaining cells may be filled with any states at all, and a GOE is obtained. The 9X33 rectangle published as an orphan (see "Math. Games", SCI.AM., 11-71) properly includes at least two layers of blanks to 'insulate' it from the environment --- in games without blanks other states may act as insulation. It is amazing that Moore's proof shows only that an orphan exists in "Life" not larger than about 25X109 by 25X109. The discovery of a small orphan was an important step, and probably one much smaller than the known one exists. Moore's proof is not a 'pure' existence proof, since a definite bound can be calculated, but obviously no one cared to comb through all configurations of that size! Let P be a finite pattern, square in shape, presumed to be part of a total pattern. When P is given, the next state may be computed for any cell not in the outermost layer. A boundary cell of course depends both on cells within P, and cells outside P. The new states of the inner cells from a square Q, smaller than P by two rows and two columns. If P is size nxn, then Q is (n-2)x(n-2). Let T, or T:P->Q denote the transformation taking P to Q. This notion is applicable to all the automata under consideration. Note that another equivalent definition of orphan is a configuration Q which is not the successor of any P under T. Merely taken an orphan of any shape and add enough cells for padding to make the shape square. Two states of the 'universe' will be called indistinguishable with respect to each other if two things are true: (a) They have the same sussessor, and (b) The states are the same, except for a finite number of cells. Two square arrays P,P1 of the same size will be called mutually erasable if (a') The size is at least 5x5 and the outer two layers are identical. (b') Both P,P1 yield the same square Q under T. It is now not hard to see that two universal states U, U1 are indistinguishable just in case there is a pair of ME squares P,P1 such that P occurs in U, and if P is replaced by P1, U1 is obtained. We assume of course that P,P1 and consequently U, U1 are distinct. Suppose U, U1 are indistinguishable, then a square array P in U may be singled out, large enough to include all the cells where U, U1 differ, and at least two layers besides. It is clear that this square pattern P and its correspondent P1 in U1 form an ME pair. On the other hand, if U contains P, and P,P1 are ME, form U1 by replacing P with P1. Suppose T: P,P1 ->Q. Each cell of the space either has identical contents for itself and its neighbors in both U and U1 , or else is in the area that becomes Q, hence U, U1 are followed by identical generations. Here is seen the reason for two identical layers of insulation instead of one. |
Page 7
View scan of this page
|
Notice that any finite pattern containing P of arbitrary shape is an orphan if P is, and is mutually erasable if P is. This is the reason it is no loss to consider square arrays only. We are now ready for the Moore-Myhill Theorem. It states that an automata of the sort described above possesses a finite Garden-of-Eden (orphan) if and only if there is a finite pair of mutually erasable square arrays. First consider the-case where P,P1 are squares, say of size nxn, which are mutually erasable. The idea of the proof is to range copies of these together to obtain patterns which have only one successor for a large number of predecessors. The occurence of such "greedy" children with so many fathers eventually predominates to such an extent that there are not enough fathers remaining for the rest, and some must be orphans. Compare the strain in Marxist thought that predicts the concentration of goods in the hands of a rich few with the passage of time, so that many are left without. For a bit of rationale, consider the border which is lost in applying the transformation T. This depends roughly on the size of the square array, whereas the number of copies of P or P1 that can be packed into the array depends more on the area. As the area has a faster growth rate, loss due to 'erasure' should eventually overtake and exceed the loss of states due to the border. In giving a numerical argument, we omit the calculation of an exact bound. For some k > 1, consider all possible square arrays R of size kn x kn. Each R can be partitioned into k2 subarrays of size nxn. Suppose P is one of these subarrays, and T: R -> S. Replace P by P1 and get R1. Since T: R1-> S, in looking at arrays R with distinct succesors, we can pass over those cases which contain P rather than P1 as a subarray. Let A be the number of states per cell. There are then An2 possibilities for an nxn array, but with P omitted, only An2-1. This happens in all k2 possibilities for an nxn array, but with P omitted, only An2-1) k2 arrays R with distinct successors can be found. But the number of possible successors S is the number of arrays of size (kn-2) x (kn-2), which is A(kn-2)2. All that is needed to argue the existence of an orphan is the inequality An2-1 k2 < A(kn-2)2 for large enough k, for then 'children' exceed 'fathers'. But consider the equivalent condition obtained by raising both sides to the 1/k2 power. (An2 - 1) < A(kn-2)2/k2 = A(n-2/k)2 By increasing k, n - 2/k can be made close to n, so that the right side can be made as close to An2 as desired. The left side is less than this amount by the fixed quantity 1, hence the inequality can be achieved. |
Page 8
View scan of this page
|
To make the argument in reverse, assume that some array P of size nxn is an orphan. Consider the A (kn-2)2 different arrays S of size (kn-2) x (kn-2). By adding two identical layers to all of these, obtain the same number of arrays Q of size (kn+2 x (kn+2). Consider the transformation T:Q -> R, where R is nxn. Now if R is the successor of some Q, none of the k2 different subarrays of size nxn can be the orphan P. Using an argument almost identical to the one above, the number of possible distinct R with P excluded from each subarray is at most An2-1 k2 . By again considering the Moore inequality, we find the number of arrays R which can be successors is less than the number of Q, and there are then two arrays of size (kn+2) x (kn+2), say Q and Q , which have the same successor. Since these have the same two outer layers, they form a mutually erasable pair. To find a pair of mutually erasable arrays in "Life" consider two 5x5 squares, one blank, the other almost, with a single live bit in the center. This application was apparently first noticed by Alvy Ray Smith III. This completes the result, but the "grandfather" problem is still unsolved: is there a configuration with a father, but every father of i is itself an orphan? |
|
Roger P. Linfield of Millersville, Pa. notes that the fourteen-bit string in 38 generations forms a single glider headed northwest. STEP NUMBER 0 |
Raynham notes that two pi-heptominoes of 'houses' as he calls them will, in 33 generations, form a beacon with two gliders sucessfully escaping to the southwest. house-house collision |
|
'Life will die if held too tightly, . . . Oscar Wilde. |
Lifecomic by Michael Moore of Utica, N.Y.
|
|
|
Page Scans
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 8
