Lifeline Volume 2
Lifeline Volume 2 | ||
Published in | June 1971 | |
---|---|---|
Preceded by | Volume 1 | |
Succeeded by | Volume 3 |
This page is a transcript of Volume 2 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 2JUNE 1971
Page 1
View scan of this page
The response to LIFELINE Number One and Martin Gardner's announcement in the April issue of Scientific American regarding this endeavor has been overwhelming! More than 340 inquiries have been received from readers in many industrial organizations, schools, and universities in fourteen different countries - and mail is still flowing in. The administrative burden accounts for what may seem to some of you (especially the early respondents) an indifference on my part. Following the establishment of a mailing list of subscribers, I will attempt to answer many of your individual inquiries via LIFELINE, an informal but relatively rapid and specific response to your area of interest.
LIFELINE Number Two extends and refines the ideas presented in the first issue and incorporates information from many of your responses. The main objective of this issue is to further the base of classification and common definition using your own developments as examples.
The fates of the unknown heptominoes E, F, H, and I were first sent in by Robert Bison of Hopewell Jct., N.Y. and subsequently confirmed by David W. Bray of Syracuse, N.Y., Charles L. Corderman of Winchester, Mass., Gary Goodman of Stanford, Calif., Stephen B. Gray of Los Angeles, Calif., Maxwell E. Manowski of New York (FPO), and Don Woods of Natick, Mass. The histories and final 'census' (an apt term coined by Woods) of these four interesting Life objects are shown here:
Fates of the last four unknown heptominoes | ||
---|---|---|
Heptomino | Age | Census |
E | 343 | 5 blocks, 4 beehives, 1 blinker, and 1 glider |
F | 437 | 3 blocks, 1 tub, 1 boat, 1 beehive, 1 pond, 7 blinkers (1 + 3/4 traffic lts.), and 1 glider |
H and I | 247 | 3 blocks, 1 boat, 1 beehive, 1 ship, and 2 gliders |
To save unnecessary effort on the part of those receiving issue Number One later than April, I appended a note to the effect that these results were known. Like seven other heptominoes (No. 1, Table 2), they all give birth to one or more gliders during their history. Interestingly, the direction of glider escape in all cases is to the northeast from the initial positions originally shown.
With many more objects being discovered in Classes I, II, and V it becomes tempting to subclassify them within the system proposed in issue Number One. The writer had previously arranged all Life objects into six primary classes based upon characteristics of their history and now proposes further definition (subclassification).
Page 2
View scan of this page
AN EXPANDED CLASSIFICATION SYSTEM FOR FINITE LIFE OBJECTS | |||||
---|---|---|---|---|---|
Primary Class | Subclassified According To: | Subclass | Example* | Size | |
I-Still Lifes | Degree of symmetry | 2-way orthogonal, 2-way diagonal, 90° rotational |
I.A | block | 4 |
2-way orthogonal, 180° rotational |
I.B.1 | beehive | 6 | ||
2-way diagonal, 2-way diagonal, 90° rotational |
I.B.2 | ship | 6 | ||
90° rotational | I.B.3 | spiral | 20 | ||
1-way orthogonal | I.C.1 | hat | 9 | ||
1-way diagonal | I.C.2 | boat | 5 | ||
180° rotational | I.C.3 | snake | 6 | ||
none | I.D | fishhook | 7 | ||
II-Oscillators | Type of periodic activity | flip-flops (all period two) |
II.A | blinker | 3 |
billiard table configurations | II.B | pinwheel | 35 | ||
inductors | II.C | tumbler | 16 | ||
pulsators | II.D | pentadecathalon | 12 | ||
shuttles | II.E | queen bee | 20 | ||
miscellaneous | II.F | M.I.T. osc. | 18 | ||
III-Spaceships | Motion of spaceship | orthogonal | III.A | lt.wt.s.s. | 8 |
diagonal | III.B | glider | 5 | ||
IV-Propagators | Nature of activity | spaceship guns | IV.A | the Gun | 36 |
puffer trains | IV.B | ? | ? | ||
V-Unstable (all objects not in above) |
Final census | dies (Θ) | V.A | bit | 1 |
Class I | V.B | latent block | 3 | ||
Class II | V.C | blinker pred. | 4 | ||
Class III | V.D.1 | R-pentomino | 5 | ||
Class III (only) | V.D.2 | glider pred. | 5 | ||
Class IV | V.E | Gun pred. | 26 | ||
unknown | V.F | acorn** | 7 | ||
* smallest known object (for Classes II, III, IV - minimum phase) | |||||
** 'apparently' unknown - see text, page six |
Page 3
View scan of this page
A modified classification system is presented on page two which attempts to recognize the specific, key characteristics of finite Life objects of each class. The examples shown represent, for each subclass, the smallest object (minimum number of bits) known to the writer. Most examples given are well known and have been previously described in either Scientific American or LIFELINE Number One. Those that are new are described in this newsletter. If anyone knows of smaller objects than any of these I will publish them in the next issue.
In general the number of new Class I objects reported is too large and common to mention. The 'spiral' was suggested by the writer merely to provide an example of a small Class I.B.3 object since none had previously been mentioned. The 'hat' a name given by Corderman and known by several other readers can be used to construct larger stable forms and is probably the smallest Class I.C.1 object. Class I.D objects exhibiting no symmetry whatsoever are the least common.
Some interesting examples of still life symmetry | ||||||
---|---|---|---|---|---|---|
Hat | Fishhook | Spiral | Shillelagh | Tub w/tail | ||
The 'fishhook', a name independently coined by Clement A. Lessner III of W. Lafayette, Ind. and William P. Webb of San Rafael, Calif., was sent in by a number of readers and certainly must be the smallest possible nonsymmetrical still life. The two made of eight bits were given by Corderman and Hugh Thompson of Lefrak City, N.Y., who suggested the name 'shillelagh'.
The hustler |
---|
Many Class II.A objects were reported, again too numerous and common to mention. Class II.B objects are fairly easy to develop starting with an empty m by n area (billiard table) bounded by 'inductor coils' and experimenting with various random patterns within. But if one excludes period two oscillators from this subclass, only a few are known. Other than the familiar Hertz oscillator (period eight) and pinwheel (period four) only the 'hustler' of an uneven period of three shown here has been added to this subclass. Note the now familiar fishhook used as an inductor coil for the crooked sides of the billiard table. Classes II.C and II.D are very uncommon and to date no one has reported anything new in either of these groups.
Page 4
View scan of this page
The hungry bee |
---|
If one uses the Gun, many Class II.E objects may be constructed, for example, the pentadecathlon 'eating' gliders (February column, page 114 . Incidentally, the illustration as shown is incorrect. The pentadecathlon and glider nearest it should be moved to the right one unit and in addition, an extra bit should be placed in the cell directly to the southeast of the glider). Earl C. Abbe of McLean, Va. has similarly positioned a queen bee near the glider stream. In this case however, the object eating the gliders will die if it is not fed every thirty generations!
Queen bees |
---|
Abbe has also placed two shuttles between two blocks to create a 'queen bees' oscillator of period thirty. Does anyone know of an 'active element' which can be used for these type of constructions other than the glider or shuttle?
The miscellaneous category II.F is unusual and had the single addition presented below with all its phases shown. Charles Trawick of Decatur, Ga, calls his discovery 'candelabra' and, like the M.I.T. oscillator (No.1,p.5) is also of period three.
Candelabra |
---|
Not surprisingly, no new spaceships (Class III) were reported. However, several intriguing (and delightfully simple) infinite patterns have been discovered that move orthogonally at the speed of light! These are discussed later in this newsletter. Notice Class III is now subdivided by the object's direction of motion.
Class IV, consisting only of the Gun, may (for the fun of it) be subclassified by type of activity into spaceship guns and puffer trains. In a sense, all Class III.A objects are puffer trains whose 'sparks' die rather than create any Class I or II objects. More will be said about puffer trains later.
Page 5
View scan of this page
A small predesesor to the blinker |
---|
Class V includes anything not in Classes I through IV and is now subdivided according to the object's final census. The single bit is, of course, the smallest object (Class V.A) that dies. I coined theta (Θ), the Greek symbol for death and which appears on the ecology flags, to represent this subclass. A latent block () is the smallest object (Class V.B) that becomes a still life. The blinker predecessor shown here is not only one of the smallest objects (Class V.C) that becomes periodic but does so in only a single generation. The tetromino () and two other four-bit objects, of course, form the traffic light but only after a varying number (nine or more) of generations. These three objects were the subject of issue Number One (p.6) and are discussed later in this issue. Can you identify the five other four-bit objects besides the one shown here that become a blinker?
A pure glider generating heptomino |
---|
A small predesesor to the glider |
---|
Class V.D objects are less common and very fascinating because of the one or more gliders created during their history. They include the R-pentomino, a hexomino, and the eleven heptominoes mentioned earlier. Of these, three heptominoes are of the 'pure glider generator' variety (Class V.D.2) one of which is shown at the left. Although not an omino, the five-bit object to the right is one of the several smallest known predecessors to the glider. Glider α () and glider β () are not included in the list even though they do evolve into a glider. Can you identify any of these objects including the two other heptominoes before I present them in the next issue?
Many readers have reported Class V.D.2 objects like the 4-8-12 diamond and biloaf presented in the first issue and also described by Martin Gardner in the April column. Shown below are two symmetrical objects yielding two gliders each and three nonsymmetrical single glider generators. 'No name' was sent in by Bray and also Roger H. Rosenbaum of Seattle, Wash., who supplied the two long undecominoes. You may recognize the third one as appearing in the spaceship conversion last issue. There seems to be an inordinate number (four now including the one mentioned last issue, p.3) of undecominoes in this subclass. Dale Edwin Cole of San Bernardino, Calif. sent in his 'biclock'.
Some more pure glider generators | |||
---|---|---|---|
no name | three undecominoes | biclock | |
|
|||
You might be interested in following the pattern made up entirely of ominoes at the top of the next page for a real surprise!
Page 6
View scan of this page
A family of ominoes with interesting great grandchildren |
---|
The smallest known ancestor of the Gun |
---|
No one responded to the challenge of finding a minimum predecessor pattern for the Gun (Class V.E). The 26-bit pattern mentioned in March (p.3) is shown here and the challenge still stands: Does a 25 or less bit pattern exist? This was given as the example for Class V.E even though it is not a true object since the idea was to get the minimum configuration (object or pattern). However, there undoubtedly are true objects that evolve into the Gun. More will be said about the meaning of an object later.
The 'acorn' |
---|
Class V.F is a catchall for anything whose outcome is not known. Notice the old Class VI is now defunct. The example mentioned on page two and shown to the left is a mere seven-bit object that is for all practical purposes unknown (to all but a few) because of its unusual history. Unless you have the resources of a large computer (and program), the patience, and are willing to spend a lot of time please do not try to determine its fate. As a surprise for LIFELINE Number Three, I will give its discoverer as well as present the fate of the 'acorn' - a term I coined after seeing its final census. It is given as a Class V.F example only to show how a simple object can, until census verified, be classified as unknown (just like the four heptominoes previously given.)
Page 7
View scan of this page
A large unexplored area of Life that is fast gaining popularity (with some real surprises!) involves 'transfinite objects'. In general, these are objects consisting of an infinite stable portion and (if activated) a finite unstable portion which 'feeds' on the stable portion. The stable portion may be a single infinite object (or an infinite set of finite objects) of Class I, II, III, or IV. The object (or set) may be infinite in one dimension (a fuse) or infinite in two dimensions (an agar). In a sense, transfinite objects (activated) may be considered very large Class V objects. But, for the fuses, the active portion exhibits characteristics of:
1. Periodicity.
2. Motion (speed).
3. Some visible rate of change of population (decreasing, constant, or increasing).
and most importantly:
4. An infinite life (as do classes I thru IV)
Fuses, therefore, seem most like the hypothetical puffer trains with the difference (very significant) being that they (the fuses) have an infinite mass provided (gratis) whereas a genuine puffer train, like the Gun, creates its own mass.
If the stable portion is infinite in two dimensions (an agar), the active portion will be an ever expanding oval boundary around an area which may continue to 'ferment'. Examples of the stable portion of these types of objects, many of which are familiar to you, are shown:
Stable portion | Fuse example | Agar example |
---|---|---|
Class I | diagonal | 'chicken wire' |
Class II | barber pole | oscillating field* |
Class III | flotilla | field of spaceships* |
Class IV | 'multibarreled Gun' | none |
* described with specific examples in the newsletter |
Note that in all cases, the examples given are true (single) objects and in order to exist must be infinite. In some cases, methods are known to stabilize the boundary thereby making it possible to construct a finite object of the desired size - for instance, the 'fencepost' () for the diagonal. Whatever their class, transfinite objects, and fuses especially, display a variety of interesting phenomena.
The number of fuses reported is increasing rapidly so I will present here only those that display some variation on what we have previously seen reported with these objects. [Regarding fuses, Woods points out an error in the Scientific American illustration (April, page 116) in fuse b. The bottom row of two bits should be one row lower in order to work properly.]
The top of page eight shows two orthogonal fuses both of which, unlike all of the diagonal ones, 'burn' slower than the speed of light. 'Washerwoman' was sent in by Abbe and every 18 generations converts two tubs into a pair of 'clotheslines' (traffic lights). 'Honey farm-II' supplied by the writer converts three fenceposts into a beehive every 12 generations.
Page 8
View scan of this page
Washerwoman |
---|
Honey farm-II |
Many fuses may be constructed by using objects other than the simple, single diagonal. Shown below are two such fuses which, at the speed of light, convert their fuse material into Class I and Class III (!) objects respectively. The first one converts its wavy diagonal (half-pond pieces) into a pond every six generations making it one of the two only known fuses that burns with a period not of multiple four. The other converts its double fuse into a glider every four generations thus creating a stream of gliders (20 generations apart in space). Question: what is the closest possible spacing for a stream of gliders in the same 'flight path'?
Two unusual fuses | |
---|---|
Page 9
View scan of this page
Squaredance |
---|
I would now like to describe five unusual agars (not activated) all of which are periodic. The one shown to the right oscillates with a period of two. 'Squaredance', a name I gave (because the bit pairs seem to move in and out around an open square) was sent in by Woods who actually named it the 'quilt'. The one below-left sent in by Steve Tower (no address given) looks as if it will completely die out (Θ). It does but only after creating an appropriate dispersion of bit pairs to replace it. Another oscillator discovered by Tower is truly unique for it is of period three! Each of its phases are shown. Can you detect anything unusual about this oscillator (besides the period) before it is revealed in Issue Three?
Surviving bits | The three phases of an oscillator field |
---|---|
The last two agars (which were referred to on page four) are actually spaceships! The first of these shown at the left below was discovered by Robert Kraus of Chicago, Ill. Each member can be made any length desired (greater than four) by extending the two 'fins'. The second one discovered by the writer only comes in two sizes. The smaller version (not shown) is four units long and without the single bit. Both of these period one objects move orthogonally at the speed of light!
Two spaceship flotillas moving at the speed of light | |
---|---|
Page 10
View scan of this page
The next three examples actually involve finite fuses but in all cases the length of the fuse may be increased in multiples of four to achieve the same effect. They all illustrate how a glider's direction may be altered using fuses. I will, in a scenario of events, show how three fuses can be placed to demonstrate these findings. The creative staff includes (in order of occurrence) Rosenbaum, Webb, and Woods. The sequence of exhibits on this and the opposite page show, first, the three fuses at generation zero, then a glider (created by the short clean fuse) heading in generation eight towards the diagonal fuse (burning at both ends) where in generation twelve it is altered in flight and directed toward the 'synapse fuse' which gets activated by the glider (a signal) transmitting the signal thru the network (shown at generation 44) until reaching the other end where the signal is returned in generation 66 (as a glider displaced in time and space).
Generation: 0 |
---|
One of the most appealing features of fuses, from an experimental standpoint, is their ease of tracking. As stated in issue Number One (p.6) you need only a good supply of graph paper and not as much patience. The fact that fuses are periodic means that after a fairly small number of generations you can determine the period and identify each phase.
For anyone new to the game, LIFEFILE contains, among other things, a brief description of a convenient and reliable method for manually calculating Life object histories. Also, for anyone with access to a computer, but no program, I have provided an efficient program (FORTRAN source listing) written by Paul Boltwood of Ottawa, Ontario. The program calculates about three generations per second on an 80 by 80 matrix.
Page 11
View scan of this page
Generation: 8 | Generation: 12 |
---|---|
Generation: 44 | Generation: 66 |
Page 12
View scan of this page
At this time we must deal with the inevitable question: what do we mean by an 'object'? My own criteria (arbitrary, of course) for determining if a pattern (of bits) is a single object are these:
1. Patterns whose bits are all connected (either orthogonally and/or diagonally) are objects.
2. Spatially connected patterns (a collection of objects, each of which is defined as above) are single objects if an empty cell between two or more of the 'subparts', and because of the subparts, is either a birth cell (when, without the subparts, would not have been) or a non-birth cell (when, without all the subparts, would have been.)
In other words, the subparts must have a mutual effect upon each other. The pattern at the left below {Figure 2.18, first pattern} is not a single object, but its next generation, center below, is a single object (by the definition just given). The smallest example of a stable spatially connected object is the 'aircraft carrier' (Conway's term) shown at the right below.
A pattern | An object | Aircraft carrier |
---|---|---|
Obvious exceptions to this definition include all objects in Classes II.E and IV.A because they are, by definition, 'shuttles' whose activity necessitates a movement thru open space. On page two my example given for Class V.E was purposely called a pattern (No.1,p.3) since it is not a true object. The idea there was to find the minimum pattern (object or not). Finally, members of Classes II.C, II.D, and the beacon may be considered objects since at least one of their phases meets the definition. This definition is important (at least for Class V objects) to preserve any meaning for the E.F. ratio discussed in March (page 6) since it excludes defining as an object (as was suggested by several readers) such things as 'a glider a long distance away from and heading towards a blinker, say'.
Three relatives (E.F. value) |
---|
This brings us to the challenges proposed last issue of finding objects with maximum M.I.P. and E.F. ratios. Philip M. Cohen of Aliquippa, Pa. and Woods pointed out the only two other four-bit objects with an M.I.P. value of 5.0. These are shown at the right along with the tetromino to illustrate their varying E.F. values. The third one, incidentally, sets the record for all four-bit objects.
Shown at the top of the next page are eight predecessor objects to the R-pentomino. The first three (a, b, and c) are the ones (all orthogonally-diagonally connected) that the writer had in mind when discussing this subject in March. The other five, all spatially connected, were sent in by Cohen (f), Corderman (a, c, and h), and Woods (a, b, d, e, f, and g). Three of these (a, c, and h) are all 'grandfathers' to the R-pentomino and therefore have an E.F. value (the one Woods had in mind) of 221.0. Does anyone know of a five-bit great grandfather to the R-pentomino?
Page 13
View scan of this page
A host of predecessors to the R-pentomino |
---|
Diehard |
---|
Another interesting measure is the ratio of age to initial population for Class V.A objects. For example, five generations is the longest any four-bit object can last before dying (E.F.=1.25) and apparently eight generations is the longest any five-bit object can survive before death (E.F.=1.6). Can you identify either of these? Rosenbaum has discovered the object at the right of a mere eight bits that manages to stay alive 118 generations before death (E.F.=14.75)! Even though E.F.V.A max ≤ E.F.V max for objects of the same size, I think this represents a very interesting challenge by virtue of the final extinction requirement. Any information received regarding this or the other two ratios will be presented in issue Three.
Practically any variation to Life that you can think of is probably being investigated by at least one individual. I would now like to mention several areas of Life and Cellular Automata Theory in general that are being investigated. It is still too early to report many detailed results on these subjects, however.
Several readers have tried playing Life on boards finite in either one or two dimensions which is analogous to playing on a cylindrical or a toroidal (doughnut) surface. The most noteworthy of these involves the work of Donovan Smith of El Cerritor, Calif. who has investigated families of 'necklaces' and 'radicals' as he calls them, on 4 by n toroidal surfaces (see example).
A necklace | A radical |
---|---|
Oscillators with periods greater than two are very common (usually a multiple of four) and shown below at the left is one Smith discovered of period five (!) which begins in generation seven starting with a 4 by 12 necklace. Interestingly, the very same finite surface will support a period four oscillator sent in by Trawick shown below at the right.
Period 5 | Two oscillators supported on a 4 by 12 torus |
Period 4 |
---|---|---|
Page 14
View scan of this page
Many phenomena exhibit interesting twists on a closed board. For instance, two overweight spaceships (November column, page 118) of any identical length could travel together along the surface of a cylinder twelve units in circumference. A spaceship like the one described on page nine could travel unescorted endlessly across a 6 by 7 surface at the speed of light!
Two person games seem to be popular as evidenced by the large number of readers either requesting information or actually submitting ideas for games that they have developed. Rules for such games are easy to think up and the ones proposed vary widely. I will present here one of the many games suggested because it seems to have been played for awhile (tested) so has been refined from the original idea. Also, it embodies the concept of many other games sent in.
IMMIGRATION, a two-person game invented by Woods, is played as follows:
- Equipment - a 25 by 25 board (used as a finite matrix like the toroidal surface just described) and a good supply of two different colored counters (chips or stones).
- To setup - each player alternately places one of his 'people' (counters) on the board until each has placed five people.
- Rules to play - colors are irrelevant in determining survivals and births which use the same rules as in the regular version. Since a birth requires three neighbors (an odd number) the majority color (i.e. the color with two or three) determines the color of the newborn 'child'. Remember, the 98 border squares also have eight neighbors.
Every ten generations the player with the most people places (immigrates) one extra person of his color in any empty cell. Then the other player does the same with his color. If neither player has a majority, they continue advancing thru additional generations until the tie is broken. The 'every ten generations' then applies to the tenth generation following the tie-breaking one. Unlike most other games IMMIGRATION involves a degree of skill (via the every tenth generation choice placement) and, as Woods says, 'also threatens stable Life forms'.
The game is won when, at the time for immigration, only one color remains on the board. If both colors are extinct the game is a draw. Experience has shown that some basic strategies may be developed to increase the chances of winning.
Life may also be played as some readers have done, on a hexagonal tessellation which can be translated into an equivalent game on a square tessellation by suitable definition of neighborhood (see below).
Page 15
View scan of this page
A 'hexaglider' |
---|
Notice the neighborhood is now six rather than eight cells and therein lies the big question: what rules do we use? Ken Preston, Jr. of Norwalk, Conn. using the following set of rules has reported the existence of a Class III object similar to a lightweight spaceship (!): Survival requires two (and only two) bits anywhere in the six-cell neighborhood. Birth requires two bits in the neighborhood but not if they are opposite each other (i.e. in the illustration on the previous page, bits in cells 1 and 2 or in 1 and 3 would give birth but bits in cells 1 and 4 would not). The object shown at the right every six generations moves three units in the direction indicated (one of the three major axes). A filled hexagon (whose sides are alternately of length four and three) after 116 generations forms six 'hexagliders' (my term) which successfully escape. Six more are formed in generation 406 but are immediately 'gobbled up'. Still six more appear in generation 470 and succeed in escaping as did the original six. Preston has yet to determine its eventual fate.
Several ambitious readers are attempting to play Life in a three-dimensional matrix. The greatest problem here, I think, is choosing a set of rules for the 26-cell neighborhood. One reader, Harvey Lerman of Maitland, Fla., suggests the following method which attempts to make use of Conway's sound two-dimensional rules:
- Consider the three orthogonal planes thru a cell.
- Use Conway's rules on each plane separately.
- If the cell survives in at least two (Lerman is also considering all three) of the planes then it survives in three dimensions.
- Likewise for birth.
Whichever rule it is really not too difficult to compute and plot (each layer, say) but you definitely are more limited in grid (computer core) size and it is extremely difficult to conceptualize what is going on.
Martin Gardner in the February column (page 113) mentions proof of the existence of 'Garden of Eden' (GoE) patterns. Recall, these are configurations that have no predecessor patterns so therefore could never be formed unless given in the initial (zero) generation. At that time we were assured that such patterns existed within a field 10^9 cells on a side. Two developments (one theoretical and the other experimental) since then have considerably reduced the area of search but unfortunately do not really help in finding such a GoE pattern. John Conway has succeeded in showing such patterns, 'orphans' as he calls them, exist on square boards of sides less than 4000. In connection with searching for GoE patterns, Gray has written such a program which uses brute force to examine and tabulate many candidate patterns. He has succeeded in proving that no GoE exist within a 4 by 4 square - a feat which required identifying predecessor patterns (fathers) for all the 65,536 possible 4 by 4 patterns (including rotations and reflections.) This effort required 90 minutes of computer (special purpose solid logic) time during which about 20 million 6 by 6 random patterns were created!
Page 16
View scan of this page
Along this same line, several readers have inquired about 'backward synthesis' algorithms for determining predecessor patterns. To my knowledge, nothing has been done in this regard. If anyone has, I will be pleased to report their work in the next issue of LIFELINE.
It is not practical to report here the details on all the other variations on Life which readers have sent in. As the level of interest or effort in any particular area increases, I will include these in the newsletter. I solicit your ideas and suggestions on how more of the detailed information can be effectively disseminated. In the meantime, LIFEFILE, the appendix to LIFELINE, will be used to fill this need.
In closing LIFELINE Number Two, I think it appropriate to give some indication as to the subjects planned for future issues which the writer has in mind and is already developing. These are not in any particular order, and in some cases not too descriptive, but all are definitely food for thought.
COMING EVENTS:
- methods of stabilizing the boundary of transfinite objects
- spiral fuses
- some more interesting scenarios of Life's events
- an entire field of gliders
- 'fly by fuses'
- F.I.P. - another ratio
- sparks
- a catalog of glider-derived objects
- implications of aging - another rule for death
- measuring the density and center of mass of an object or pattern
- 'constellations'
- some potential spaceships
- Life family trees
- 'channel' phenomena
- self-repairable Life objects
- 'tag alongs'
- minimum predecessor patterns
- seeded agars
- some potential spaceship guns (!)
- entropy of a system of bits
- primordial broths
- illusions of motion exhibited by certain Life objects
- 'beehive', a period 30 agar
- 'antibodies' that thrive on glider streams
- constructing a computer with glider guns
Page 17
View scan of this page
O OOO OOO OOO OOO OOO O OOO O O O O O O O O O O OO OO OO O O OO O O O O O O O O OOO OOO O OOO O OOO OOO OOO A COMPREHENSIVE FILE OF INFORMATION GENERATED BY LIFE EXPERIMENTERS
LIFEFILE this issue regards ways of calculating Life histories. Many readers have requested computer programs and nearly as many have supplied source listings in addition to algorithms, hints, etc. that they are using. I have decided to present here two sound and efficient Life algorithms. The first of these described below is simply a procedure for tracking patterns manually using graph paper. The second, given on the next page, is a source listing of a FORTRAN (IV G) program written by Boltwood and slightly modified by the writer to change the input requirement and output display. The algorithm, to my knowledge, is the most efficient one in use. Input requires a header card followed by a set of cards containing the pattern for generation zero.
Header Card: cc 01-05: limit of calculation (gen. no) 06-10: frequency of printing 11-15: top row of initial pattern
Example: 0 1 123456789012345 75 4 31
This specifies the termination of calculation at gen. 75 (unless pattern dies out sooner) and output printed every 4 gens. The pattern supplied on the set of cards begins in row 31.
Set of pattern cards: The first card corresponds to top row in pattern and the following cards for each row. The card columns correspond to output columns. A '0' (or any non-blank character) may be punched for @ bit.
A suggested manual method for 'playing Life' |
---|
|
* scanning can be done by either or both of these methods:
a. scan each empty cell of every row (or column) passing adjacent to and thru the pattern. b. scan each empty cell immediately around the pattern and within the pattern |
Page 18
View scan of this page
Boltwood's Life program in FORTRAN:
IMPLICIT INTEGER (A-Z) COMMON Q,ST,IT,C(6400) INTEGER R(80) DATA BL,BIT/' ','0'/ Q=80 QQ=Q*Q DO 1 1=1,QQ D(1)=Q ST=9999 Q2=Q/2 REAC(5,8) CY,PI,I FORMAT(315) REAC(5,9,END=11) FORMAT(80A1) DO 10 K=1,0 IF(R(K).BQ.BL) GO TO 10 L=I*Q+K-I D(L)=ST ST=L CONTINUE I=I+1 GO TO 5 WRITE(6,3) FORMAT('1') IT=0 CALL PRT DO 4 IT=1,CY CALL NEXGEN(&6) IF(MOD(IT,PI).EQ.0) CALL PRT GO TO 2 WRITE(6,7) IT FORMAT(' DIED AT ITERATION ',I4) STOP END SUBROUTINE PRT IMPLICIT INTEGER (A-Z) COMMON Q,ST,IT,D(1) INTEGER R(80) DATA BL,BIT/' ','O'/ O=0 L=10000 B=ST IF(K.EQ.9999) GO TO 21 J=MOD(K-1,Q) IF(J.GT.B) B=J IF(J.LT.A) A=J IF=(K.GT.U) U=K IF(K.LT.L) L=K R=D(K) GO TO 22 21 WRITE (6,23) IT 23 FORMAT(//' GENERATION', I5) WRITE (6,28) 28 FORMAT(4X,'.........1.........2.........3.........4.........5.........6.........7.........8') U=(U-1)/Q L=(L-1)/Q DO 27 K=1,Q 27 P(K)=BL DO 24 I=L,U DO 25 J=A,B P(J)=BL 25 IF(D(I*Q+J+1).NE.O) P(J)=B IT 24 WRITE (6,26) I,P,I 26 FORMAT(1X,I3,80A1,I2) WRITE (6,28) RETURN END SUBROUTINE NEXGEN(*) IMPLICIT INTEGER (A-Z) COMMON Q,ST,IT,D(1) INTEGER NK(8),NNK(8) NB=-9999 B8=N8 K=ST 1 IF(K.EQ.9999) GO TO 6 CALL NEIBR(K,NK,&13) NN=0 DO 2 I=1,8 NKI=NK(I) IF(D(NKI).LE.0) GO TO 3 NN=NN+1 GO TO 2 3 IF(D(NKI).LT.0) GO TO 2 CALL NEIBR(NKI,NNK,&13) NNN=0 DO 4 J=1,8 4 IF(C(NNK(J)).GT.0) NNN=NNN+1 IF(NNN.NE.3) GO TO 5 D(NKI)=NB ND=-NKI GO TO 2 5 D(NKI)=BB BB=-NKI 2 CONTINUE IF(NN.EQ.2.OR.NN.EQ.3) GO TO 12 13 D(K)=D(K)+10000 K=D(K)-10000 GO TO 1 12 K=D(K) GO TO 1 6 CONTINUE 16 IF(ST.EQ.9999) RETURN 1 IF(D(ST).LT.10000) GO TO 14 I=ST ST=D(ST)-10000 D(I)=0 GO TO 16 14 K=D(ST) DK=ST 15 IF(K.EQ.9999) GO TO 11 IF(D(K).LT.10000) GO TO 20 D(DK)=D(K)-10000 D(K)=0 K=D(DK) GO TO 15 11 IF(NB.EQ.-9999 GO TO 17 K=-NB 8 IF(K.EQ.-9999) GO TO 17 D(K)=-D(K) CK=K K=D(K) GO TO 8 7 D(CK)=ST ST=-NB 17 K=-BB IF(K.EQ.9999) RETURN I=K K=-D(K) D(I)=0 GO TO 9 END SUBROUTINE NEIBR(K,NK,*) IMPLICIT INTEGER (A-Z) COMMON Q INTEGER NK(8) Q1=Q-1 K1=K-1 I=K1/C J=MOD(KI,Q) IF(I.EQ.0.OR.I.EW.W1.OR.J.EQ.0.OR.J.EQ.Q1) RETURN 1 NK(1)=K1 NK(2)=K1+2 NK(3)=K1+Q NK(4)=NK(3)+1 NK(5)=NK(4)+1 NK(6)=K1-Q NK(7)=NK(6)+1 NK(8)=NK(7)+1 RETURN END