NetNews Usenet Archive 1992 #19

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / cellaut / 350 < prev next >

Wrap

Text File | 1992-08-27 | 30.9 KB | 787 lines

Newsgroups: comp.theory.cell-automata Path: sparky!uunet!munnari.oz.au!manuel!sserve!pdact!dbell From: dbell@pdact.pd.necisa.oz.au (David I. Bell) Subject: Spaceships in Conway's Life (Part 2a) Organization: NEC Information Systems Australia, Canberra Date: Fri, 28 Aug 1992 01:38:19 GMT Message-ID: <1992Aug28.013819.27026@pdact.pd.necisa.oz.au> Keywords: life Sender: news@pdact.pd.necisa.oz.au (News Holder) Lines: 775 Spaceships in Conway's Life (Part 2) by David I. Bell dbell@pdact.pd.necisa.oz.au 28 Aug 1992 This is the second in a series of articles concerning Conway's Game of Life. In this article, I will describe the early history of the discovery of the new classes of spaceships, and then survey the results for all the known period 2 spaceships. All period 2 spaceships must be orthogonal, and must travel at the speed of c/2. This follows from the speed restrictions mentioned in my previous article. In July of 1989 Dean Hickerson started writing a Life search program for his Apple IIe. It was written in 6502 assembly language and Applesoft BASIC. Dean's Life search program looks for patterns that repeat themselves after a small number of generations, with or without translations. (Translations are used when you want to find spaceships instead of oscillators.) During a search, the program recursively attempts to set cells ON or OFF, and for each cell that is set uses transition and implication rules in order to detect contradictions in the current state of cells. This allows the program to quickly stop and backtrack over impossible situations, and thus reduce enormously the size of the search. This program was described in the xlife 3.0 distribution. Search programs typically attempt to set the cells in a column-by-column order. Since a cell's fate in N generations is usually dependent on the state of all cells within a distance of N, contradictions cannot usually be detected until the state of the next N columns has been specified. This means that looking for oscillators or spaceships is much harder for larger periods. The current useful limit on search programs of this type is for period 5. Some searches in small areas have been done for periods 6 and 7. Another effect of the order of setting cells column-by-column is that objects which have many rows are harder to find than those with fewer rows. (The number of columns can be very large and has little effect on the search.) The current search programs can usefully look for objects which have about 10 rows (20 rows if symmetry is used), but this limit can be raised somewhat for low-period searches, such as up to 14 rows for period 2. Since the useful number of rows being searched is limited, many of the spaceships which are found are of one of two types. They are either wide and short or are thin and long. These terms refer to the dimensions of the spaceship with respect to the direction that it travels. Therefore a thin and long spaceship looks like an "arrow", whereas a wide and short spaceship looks like a "wave". However, for many smaller space ships where both dimensions fit within the row limit and are of comparable size, they can look like "blobs". Using his program, and looking for short, wide spaceships, Dean Hickerson found the first period 2 spaceships on July 28, 1989. These were the first examples of a new class of spaceship. He does not remember which specific spaceship was found first, but the following ship was among the first ones found, and is the smallest known period 2 spaceship. [Smallest known period 2 spaceship (speed c/2)] .....O.O ....O..O ...OO... ..O..... .OOOO... O....O.. O..O.... O..O.... .O...... ..OOOO.O ...O...O ....O... ....O.O. ........ ...OOO.. ...OO... ...OOO.. ........ ....O.O. ....O... ...O...O ..OOOO.O .O...... O..O.... O..O.... O....O.. .OOOO... ..O..... ...OO... ....O..O .....O.O Within a few hours of finding the first period 2 ship, Dean had discovered a grammar for constructing an infinite number of different short, wide, period 2 spaceships. A grammar is an "alphabet" of "components", along with rules for the possible sequences of connections between components. Components are simply the identifiable pieces of a ship which reappear over and over in different ships in different combinations. There are three components in the above spaceship, as will be seen below. The complete grammar describes the components, the allowed sequences of the components, and the manner in which the components are joined together. The following are the components of Dean's first grammar. [A] [A'] [B] [B'] [C] [C'] .....O.O .......O X X X X ....O..O ....OOOO ... .O.. ..... .O... ...OO... ....OO.. OOO .O.O OOO.. .O.O. ..O..... ..O..... OO. O... OO... O.... .OOOO... ..OOOO.. OOO .O.O OO... O...O O....O.. .O...... ... .O.. OOOOO .O..O O..O.... OOO..O.. X X ..O.. .O.O. O..O.... .OOO.... X X .O...... ..O..... ..OOOO.O ...OOO.O ...O...O ...O..OO ....O... ....OOO. ....O.O. ......O. X X [D] [D'] [E] [E'] [F] [F'] X X X X X X ... .O.. ...O.O ....O ...O .O.O OOO .O.O ..O..O ..OOO .OOO O..O OO. O... ..O... .OOO. OOO. O... OO. O... .O..O. O..O. .OOO O..O OOO .O.O OOO... O.... ...O .O.O ... .O.. .OOO.. O..O. X X X X ...O.. .O.O. X X [G] [G'] X X .O.O.. ...O... O..O.. .OOO... O..... OOO.... O..... .OO.... .O..OO ..OO..O ..OOOO ...OO.O ...... ....... ..OOOO ...OO.O .O..OO ..OO..O O..... .OO.... O..... OOO.... O..O.. .OOO... .O.O.. ...O... X X The components occur in pairs identified by the same letter, but with or without a quote mark (e.g., A and A'). Such pairs are related in that they are the two phases of the same section of a period 2 spaceship. So that, for example, if a period 2 spaceship contains component B in generation 0, then in generation 1 it must contain component B' in the same position within the ship. Besides the listed components, there are other components which are their mirror images. The mirroring is done by flipping the component across a horizontal line. The mirrored component names are the same as for the original components, except that they end with a trailing dash. So that, for example, the mirror image of component A' is A'-. Mirror images for symmetrical components such as B would be duplicates and so are not used. The components that make up a spaceship are strung together like beads on a string, stacked one above the other. A sequence of components specifies the order of components, arranged from top to bottom. When doing this, the components must be correctly aligned horizontally. The 'X' characters in the component diagrams specify the proper alignment. When two components are stacked together, they must be placed adjacent to each other so that the 'X' characters are in the same column. The rows containing the 'X' characters are not part of the components, and should be removed. The following shows an example of stacking two components correctly. [Section B F' of a period 2 spaceship] X .... OOO. OO.. OOO. .... .O.O O..O O... O..O .O.O X The final part of the grammar specifies the allowed sequences of components. Only certain sequences of components can be used to make a valid spaceship. The following rules specify these allowed sequences. The sequence must begin with A or A'. The sequence must end with A- or A'-. Each pair of adjacent symbols must appear in one line of the following table, with the first symbol found before the vertical bar, and the second symbol found after the vertical bar. A C' E- E' F' G | B C D A' C E E'- F G' | B' C' D' B C- D | A- C'- E E'- F' G B' C'- D' | A'- C- E- E' F G' The simplest example of a sequence which follows these rules is A B A-, which represents the c/2 period 2 ship given above. Another example of a spaceship created using these rules is A D E B' A'-, which represents the following spaceship. [One of many period 2 spaceships constructed by the above grammar (speed c/2)] .......O.O ......O..O .....OO... ....O..... ...OOOO... ..O....O.. ..O..O.... ..O..O.... ...O...... ....OOOO.O .....O...O ......O... ......O.O. .......... .....OOO.. .....OO... .....OO... .....OOO.. .......... ......O.O. .....O..O. .....O.... ....O..O.. ...OOO.... ....OOO... ......O... ....O..... ....O.O... ...O...... ....O.O... ....O..... ......O... ....OOO... ...O..OO.. ...OOO.O.. ..O....... .OOO...... OOO..O.... .O........ ..OOOO.... ..O....... ....OO.... ....OOOO.. .......O.. Small tagalongs were soon found for several of these components. (These tagalongs can also be attached to many of the other period 2 spaceships.) The one for component C was found by Robert Wainwright, and the one for component A was found by Bill Gosper. [C component with tagalong] [A component with tagalong] X ........O. ......... .....O.O.O OOO...... ....O..O.. OO....... ...OO..... OO....O.. ..O....... OOOOO.O.O .OOOO..... .O.....O. O....O.... X O..O...... O..O...... .O........ ..OOOO.O.. ...O...O.. ....O..... ....O.O... X Dean Hickerson also looked for thin, long period 2 ships in those first weeks. These spaceships are much harder to find, and so he only found one basic ship before moving on to search for other things. This spaceship is shown below. [First long period 2 spaceship (speed c/2)] .............O....... ...........OO........ ........OOOO.O....... ........OO.......OO.. ......O...OO.O...OOOO ......OOOO.O.O.O....O ...O.O......OO....... ..OOOOOO.OO.OO.OO.... .OO.....OO...O....... OO....OO....O........ .OO....OOOO.......... ..................... .OO....OOOO.......... OO....OO....O........ .OO.....OO...O....... ..OOOOOO.OO.OO.OO.... ...O.O......OO....... ......OOOO.O.O.O....O ......O...OO.O...OOOO ........OO.......OO.. ........OOOO.O....... ...........OO........ .............O....... At the end of September, 1989, Dean discovered an extensible tagalong for the above ship that is now named a wicktrailer. This tagalong allows the ship to be made as long as desired. Such a tagalong can be described as having a period, which is the number of generations it takes before a unit of the tagalong reappears in the same place. [Period 2 ship with wicktrailer (period 20 extensible tagalong) (speed c/2)] ............................O.........O.........O.. .............O...........OOOO......OOOO......OOOO.. ...........OO..........OOO.O.....OOO.O.....OOO.O... ........OOOO.O........OO...O....OO...O....OO...O... ........OO.......OO...O....OO...O....OO...O....OO.. ......O...OO.O...OOOO.O.....OOO.O.....OOO.O.....OOO ......OOOO.O.O.O....OOOO......OOOO......OOOO......O ...O.O......OO.........O.........O.........O....... ..OOOOOO.OO.OO.OO.................................. .OO.....OO...O..................................... OO....OO....O...................................... .OO....OOOO........................................ ................................................... .OO....OOOO........................................ OO....OO....O...................................... .OO.....OO...O..................................... ..OOOOOO.OO.OO.OO.................................. ...O.O......OO..................................... ......OOOO.O.O.O....O.............................. ......O...OO.O...OOOO.............................. ........OO.......OO................................ ........OOOO.O..................................... ...........OO...................................... .............O..................................... The tagalong can be attached to the other "foot" of this ship in a similar manner to produce a symmetrical ship of any length, or with two unequal length wicks. The tagalong can also be attached to the "foot" of the other period 2 ships on component A'. Doing this allows the construction of a ship which is as wide and as long as desired. There is a hidden motivation in looking for new ships and their tagalongs. Besides the elegance of new ships, Dean was hunting for new puffer trains. Puffer trains allow for the construction of interesting large Life objects, including devices which perform logic operations or numeric calculations. There are only a small number of basic types of puffer trains, and new methods for making puffer trains would be useful. For every new spaceship which is found, there is the possibility that it contains a new set of "sparks" that has not been seen before. Such a new set of sparks might allow a new type of puffer engine to work, or might be useful to catalyze a reaction in a new manner. So far this has not been successful. Another way that a new puffer train might be constructed is by perturbing an extensible tagalong such as the one in the above ship. If the perturbation results in a reaction that travels at a speed less than or equal to the ship (c/2 in this case), and that reaction leaves debris behind, then a puffer train results. Unfortunately, this process has so far not worked with any extensible tagalong. The reaction either breaks off, or travels faster than the ship and ends up destroying the ship. For example, deleting one cell from the end of the wicktrailer, or adding one cell to it almost always results in one of either two reactions which travel at 6c/7 or 11c/12 and catch up to the ship and destroy it. After Dean found the above results, he went looking for other things, and so the class of period 2 spaceships wasn't further developed for a while. Meanwhile, I had heard of Dean's search program, read his notes about it, and wrote my own program in C, and started making my own discoveries. I sent a copy of the program to Hartmut Holzwart. He made some modifications to it (such as speedups, new symmetries, and different search orders), and then also started making many new discoveries. But it wasn't until June of this year that we started looking for period 2 spaceships. On June 7, 1992, I was experimenting with a new search feature, and found three new components for period 2 ships. The most interesting component is a repeatable diagonal component which bends the ship backwards with a slope of 3/6. The other two larger components just provide a connection to an already known ship component, and terminate the end of the new component. The following shows a ship using all three components, with the diagonal one repeated twice. [Period 2 spaceship with repeatable "barber pole" component (speed c/2)] ........................O ......................OOO .....................OO.. .....................O... ...................O.O... .................OOO..... ................OO..O.... ................O.O...... ................OOO...... ................O.OOO.... ...............OO........ ..............OO.O....... .................O.O..... .............O........... .............OO.O........ .............O.O......... ............OO........... ...........OO.O.......... ..............O.......... ..........O.............. ..........OO.O........... ..........O.O............ .........OO.............. ........OO.O............. ...........O............. .......O................. .......OO.O.............. .......O.O............... ......OO................. ...OO.OOO................ ...O....O................ ...O..................... ....O..O................. .....OO.................. ......OO................. ...OOO.O................. ..O...OO.O.O............. .O...O..O..O............. .O..O.O.O................ .O........O.............. ..O..OO...O.............. ...OO.OOOOOO............. ....OO...O.O............. ....O.O.................. ...O..................... ....O..O................. ....O.O.................. ......................... ...OOO................... ...OO.................... ...OOO................... ......................... ....O.O.................. ....O.................... ...O...O................. ..OOOO.O................. .O....................... O..O..................... O..O..................... O....O................... .OOOO.................... ..O...................... ...OO.................... ....O..O................. .....O.O................. The diagonal component can obviously be repeated arbitrarily often to make an "arm" as long as desired. The same arm can also be constructed on the other side of the ship to make it symmetrical, creating a bow shaped ship. One interesting thing about a long string of these diagonal components is that both phases appear identical to each other, but shifted. This makes the arm act somewhat like a "barber pole" with a pattern appearing to move up (or down) the arm as the ship moves. A few days later I found a second repeatable diagonal component. This component is actually a tagalong since it just attaches to a "foot" of an intact period 2 ship. The slope of this tagalong is 8/13. This tagalong is called the "glancing head" because it resembles a head with two eyes looking sideways. The following shows two copies of this tagalong, one attached to the base ship and the second to the first tagalong. Again, this arm can be made as long as desired. [Period 2 spaceship with repeatable "glancing head" tagalong (speed c/2)] .......................O .....................OOO ....................OO.. ....................O... ..................O.O... ................OOO..... ...............OO..O.... ..............O..O...... ..............O..O...... ..............O......... ...............O..O..... ................OO...... .................OO..... ...............O.O...... .............OOO.O...... ............OO.......... ............O........... ..........O.O........... ........OOO............. .......OO..O............ ......O..O.............. ......O..O.............. ......O................. .......O..O............. ........OO.............. .........OO............. .......O.O.............. ....OOOO.O.............. ....OO.................. ..O..................... ..OOOO.................. .O...................... OOO..O.................. .OOO.................... ..O..................... ...OOO.O................ ...O..OO................ ....OOO................. ......O................. ....O................... ....O.O................. ...O.................... ....O.O................. ....O................... ......O................. ....OOO................. ...O..OO................ ...OOO.O................ ..O..................... .OOO.................... OOO..O.................. .O...................... ..OOOO.................. ..O..................... ....OO.................. ....OOOO................ .......O................ By using a piece of Dean Hickerson's wicktrailer, one foot can be turned into two feet. This allows the construction of a "binary tree" spaceship, which branches an arbitrary number of times. Here the wicktrailer tagalong can be attached to any foot, and two copies of the glancing head tagalong can be attached to the two feet of the wicktrailer. The following shows a simple example of connecting these tagalongs together to make a branching spaceship. [Period 2 binary tree spaceship (speed c/2)] .......................................O.. .....................................OOO.. ....................................OO.... ....................................O..... ..................................O.O..... ................................OOO....... ...............................OO..O...... ..............................O..O........ ..............................O..O........ ..............................O........... ...............................O..O....... ................................OO........ .................................OO....... ...............................O.O........ ............................OOOO.O........ .......O..................OOO.O........... ....OOOO.................OO...O........... ....OO...................O....OO.......... ..O....................O.O.....OOO.O...... ..OOOO...............OOO.........O.O...... .O..................OO..O..........OO..... OOO..O.............O..O...........OO...... .OOO...............O..O..........O..O..... ..O................O............O......... ...OOO.O............O..O........O..O...... ...O..OO.............OO.........O..O...... ....OOO...............OO.........OO..O.... ......O.............O.O...........OOO..... ....O.............OOO.O.............O.O... ....O.O..........OO...................O... ...O.............O....................OO.. ....O.O........O.O.....................OOO ....O........OOO.........................O ......O.....OO..O......................... ....OOO....O..O........................... ...O..OO...O..O........................... ...OOO.O...O.............................. ..O.........O..O.......................... .OOO.........OO........................... OOO..O........OO.......................... .O..........O.O........................... ..OOOO....OOO.O................O.......... ..O......OO..................OOO.......... ....OO...O..................OO............ ....OOOO.O..................O............. .......OOOO.O.............O.O............. ..........O.O...........OOO............... ............OO.........OO..O.............. ...........OO.........O..O................ ..........O..O........O..O................ .........O............O................... .........O..O..........O..O............... .........O..O...........OO................ ..........OO..O..........OO............... ...........OOO.........O.O................ .............O.O.....OOO.O................ ...............O....OO.................... ...............OO...O..................... ................OOO.O..................... ..................OOOO.O.................. .....................O.O.................. .......................OO................. ......................OO.................. .....................O..O................. ....................O..................... ....................O..O.................. ....................O..O.................. .....................OO..O................ ......................OOO................. ........................O.O............... ..........................O............... ..........................OO.............. ...........................OOO............ .............................O............ Since each branch can be extended to be as long as necessary by using more glancing head tagalongs, enough room can be created to build a fully populated binary tree ship, containing 2^N nodes. The wicktrailer is even more versatile than is shown above. A longer section of the wicktrailer has even more feet. There is room for the glancing head tagalong to be attached to each one of those feet, and for more glancing head tagalongs to be attached to those tagalongs. Counting each section of wicktrailer as a node, this means that not only can full binary trees be constructed, but full N-ary trees can also be constructed, for any N. The following illustrates the construction details that allow such a spaceship to be made. [Period 2 N-ary tree spaceship details (speed c/2)] .............................O.........O.........O.......... ...........................OOO.......OOO.......OOO.......... ..........................OO........OO........OO............ ..........................O.........O.........O............. ........................O.O.......O.O.......O.O............. ......................OOO.......OOO.......OOO............... .....................OO..O.....OO..O.....OO..O.............. ....................O..O......O..O......O..O................ ....................O..O......O..O......O..O................ ....................O.........O.........O................... .....................O..O......O..O......O..O............... ......................OO........OO........OO................ .......................OO........OO........OO............... .....................O.O.......O.O.......O.O................ ..................OOOO.O....OOOO.O....OOOO.O....O........... ................OOO.O.....OOO.O.....OOO.O.....OOO........... ...............OO...O....OO...O....OO...O....OO............. ...............O....OO...O....OO...O....OO...O.............. .............O.O.....OOO.O.....OOO.O.....OOO.O.............. ...........OOO.........OOOO.O....OOOO.O....OOOO.O........... ..........OO..O...........O.O.......O.O.......O.O........... .........O..O...............OO........OO........OO.......... .........O..O..............OO........OO........OO........... .........O................O..O......O..O......O..O.......... ..........O..O...........O.........O.........O.............. ...........OO............O..O......O..O......O..O........... ............OO...........O..O......O..O......O..O........... ..........O.O.............OO..O.....OO..O.....OO..O......... .......OOOO.O..............OOO.......OOO.......OOO.......... ....OOOO.O...................O.O.......O.O.......O.O........ ....OO...O.....................O.........O.........O........ ..O......OO....................OO........OO........OO....... ..OOOO....OOO.O.................OOO.......OOO.......OOO..... .O..........O.O...................O.........O.........O..... OOO..O........OO............................................ .OOO.........OO............................................. ..O.........O..O............................................ ...OOO.O...O................................................ ...O..OO...O..O............................................. ....OOO....O..O............................................. ......O.....OO..O...........O.........O.........O........... ....O........OOO.........OOOO......OOOO......OOOO........... ....O.O........O.O.....OOO.O.....OOO.O.....OOO.O............ ...O.............O....OO...O....OO...O....OO...O............ ....O.O..........OO...O....OO...O....OO...O....OO........... ....O.............OOO.O.....OOO.O.....OOO.O.....OOO......... ......O.............OOOO.O....OOOO.O....OOOO.O....O......... ....OOO................O.O.......O.O.......O.O.............. ...O..OO.................OO........OO........OO............. ...OOO.O................OO........OO........OO.............. ..O....................O..O......O..O......O..O............. .OOO..................O.........O.........O................. OOO..O................O..O......O..O......O..O.............. .O....................O..O......O..O......O..O.............. ..OOOO.................OO..O.....OO..O.....OO..O............ ..O.....................OOO.......OOO.......OOO............. ....OO....................O.O.......O.O.......O.O........... ....OOOO....................O.........O.........O........... .......O....................OO........OO........OO.......... .............................OOO.O.....OOO.O.....OOO.O...... ...............................O.O.......O.O.......O.O...... .................................OO........OO........OO..... ................................OO........OO........OO...... ...............................O..O......O..O......O..O..... ..............................O.........O.........O......... ..............................O..O......O..O......O..O...... ..............................O..O......O..O......O..O...... ...............................OO..O.....OO..O.....OO..O.... ................................OOO.......OOO.......OOO..... ..................................O.O.......O.O.......O.O... ....................................O.........O.........O... ....................................OO........OO........OO.. .....................................OOO.......OOO.......OOO .......................................O.........O.........O A side effect of this construction is that for any sized square, no matter how large, there exists a period 2 spaceship whose cells occupy at least some constant percentage of the area of the square (around 10%). Later, another repeating diagonal tagalong was discovered, which also allows N-ary tree ships to be built. Here the slope is 4/17, which is shallower than the previous tagalong. This tagalong has the name "staring head", and looks similar to the main component of the base ship. The following illustrates this tagalong and how it may be connected. [Period 2 spaceship demonstrating "staring head" tagalong (speed c/2)] ..........O.........O............. .......OOOO......OOOO......O...... ....OOOO.O.....OOO.O.....OOO...... ....OO...O....OO...O....OO........ ..O......OO...O....OO...O......... ..OOOO....OOO.O.....OOO.O......... .O..........OOOO.O....OOOO.O...... OOO..O.........O.O.......O.O...... .OOO.............OO........OO..... ..O.............OO........OO...... ...OOO.O.......O..O......O..O..... ...O..OO......O.........O......... ....OOO.......O.........O......... ......O.......OOO.......OOO....... ....O..........O..O......O..O..... ....O.O........OOO.......OOO...... ...O..........O.........O......... ....O.O......OOO.......OOO........ ....O.......OOO..O....OOO..O...... ......O......O.........O.......... ....OOO.......OOOO......OOOO...... ...O..OO......O.........O......... ...OOO.O........OO........OO...... ..O.............OOOO.O....OOOO.O.. .OOO...............O.O.......O.O.. OOO..O...............OO........OO. .O..................OO........OO.. ..OOOO.............O..O......O..O. ..O...............O.........O..... ....OO............O.........O..... ....OOOO.O........OOO.......OOO... .......O.O.........O..O......O..O. .........OO........OOO.......OOO.. ........OO........O.........O..... .......O..O......OOO.......OOO.... ......O.........OOO..O....OOO..O.. ......O..........O.........O...... ......OOO.........OOOO......OOOO.. .......O..O.......O.........O..... .......OOO..........OO........OO.. ......O.............OOOO......OOOO .....OOO...............O.........O ....OOO..O........................ .....O............................ ......OOOO........................ ......O........................... ........OO........................ ........OOOO...................... ...........O...................... --------------------- [Continued in next mail article] ----------------------