home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / cellaut / 338 < prev    next >
Encoding:
Text File  |  1992-08-14  |  18.8 KB  |  532 lines

  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!gatech!darwin.sura.net!mips!mips!munnari.oz.au!manuel!sserve!pdact!dbell
  3. From: dbell@pdact.pd.necisa.oz.au (David I. Bell)
  4. Subject: Spaceships in Conway's Life (Part 1)
  5. Organization: NEC Information Systems Australia, Canberra
  6. Date: Fri, 14 Aug 1992 01:20:52 GMT
  7. Message-ID: <1992Aug14.012052.6306@pdact.pd.necisa.oz.au>
  8. Summary: First in a series of recent results in Life
  9. Keywords: life
  10. Sender: news@pdact.pd.necisa.oz.au (News Holder)
  11. Lines: 519
  12.  
  13.  
  14.         Spaceships in Conway's Life (Part 1)
  15.             by David I. Bell
  16.             dbell@pdact.pd.necisa.oz.au
  17.             12 Aug 1992
  18.  
  19.  
  20. This is the first of a series of articles on recent results in Conway's
  21. Game of Life.  There are many aspects of Life that are interesting and
  22. have recent developments, such as glider guns, spaceships, puffer trains,
  23. large period oscillators, and the construction of objects with desired
  24. properties.
  25.  
  26. I am restricting this set of articles to spaceships because of two reasons.
  27. Firstly, since the earliest days of Life around 1970, no truly new spaceships
  28. had been discovered until just about three years ago, and therefore this area
  29. is very new and exciting.  And secondly, I have had a part in developing
  30. this area, and therefore know first hand about some of the results.  But I
  31. will touch on several of the other areas as I go.
  32.  
  33. Almost all of the new spaceship results I will be describing were found by
  34. one of three people.  Possibly others have independently discovered some of
  35. these things, and if so, we certainly should share credit with them.  But
  36. until I know otherwise, the credit for the discoveries belongs to the people
  37. I mention.  These people are Dean Hickerson, David Bell (myself), and
  38. Hartmut Holzwart (listed in order of involvement).
  39.  
  40. Most of the new spaceships were found by computer search.  The size and
  41. complexity of most of the discoveries are such that they would not be
  42. expected to turn up by running random patterns, or by manually trying a
  43. set of possibilities.  However, some of the "fine tuning" of the results
  44. are the work of human thinking and manipulating pieces of the found results.
  45.  
  46. Firstly, I should define some terminology.  A spaceship is a finite pattern
  47. of live cells in Life that after a certain number of generations reappears,
  48. but translated in some direction by a nonzero distance.   Translation is
  49. measured by the shortest king-wise connected path between two cells.  So two
  50. cells adjacent to each other are one cell apart, whether or not the cells
  51. are adjacent orthogonally or diagonally.  The process of translating after
  52. a certain number of generations is called moving or traveling.
  53.  
  54. The number of generations before the pattern reappears (but translated)
  55. is called the period of the spaceship.  (This is analogous to the period of
  56. stationary oscillators.)  Many spaceships appear to be the same pattern
  57. after a number of generations, but on closer examination are not really
  58. the same.  Instead of being merely translated, they are also reflected (or
  59. flipped) as in a mirror.  After twice that number of generations, the
  60. spaceship does reappear in its original form, with just a translation.
  61. The period always measures this full number of generations.  Spaceships
  62. which show their mirror image after half their period are called glide-
  63. reflection spaceships.
  64.  
  65. Spaceships can travel orthogonally (straight left-right or up-down), or
  66. diagonally.  All known diagonal spaceships travel the same distance left-
  67. right as they do up-down.  There is no reason why a spaceship could not
  68. travel (for example) two units across and one unit up for its translation.
  69. However no example of such a spaceship is known.  Theoretically, we could
  70. build ships with any translation by using a universal computer/constructor.
  71. But they would be very large and slow.
  72.  
  73. The translated distance divided by the period is the speed of the spaceship.
  74. Since the maximum speed of propagation of a signal in Life is one cell per
  75. generation, this speed is known as c (the speed of light).  This speed is
  76. also the fastest possible growth of any finite object for a finite number
  77. of generations (think of a long line of ON cells).  However, growth (or
  78. even just movement) of a finite object for an infinite time cannot occur
  79. at this speed.  It was proven in the early days of Life that the maximum
  80. possible speed of any spaceship is c/2 for orthogonal spaceships, and c/4
  81. for purely diagonal spaceships.  More generally, if a spaceship moves A
  82. cells across and B cells up, then its period must be at least 2 * (A + B).
  83. This means (for example) that an orthogonal spaceship might move by one cell
  84. in two generations, or two cells in four generations, or three cells in six
  85. generations, and so on.  But no spaceship (for example) can move by one cell
  86. in one generation, or two cells in three generations, or three cells in four
  87. generations.
  88.  
  89. Whenever I list spaceships or puffers, I will follow some standard rules.
  90. Since most known spaceships move orthogonally, that movement will not be
  91. explicitly mentioned.  They will always be drawn so as to move from right
  92. to left.  The few diagonal spaceships will be marked as such, and will
  93. move in the indicated direction.
  94.  
  95. To begin with and to be complete, I will list the original spaceships.
  96. These are the glider, the lightweight spaceship (LWSS), middleweight
  97. spaceship (MWSS), and the heavyweight spaceship (HWSS).  These were all
  98. found very soon after Life was invented by Conway.  They are:
  99.  
  100. [glider (diagonal to lower left, glide-reflective, period 4, speed c/4)]
  101.  .O.
  102.  O..
  103.  OOO
  104.  
  105.  
  106. [LWSS (glide-reflective, period 4, speed c/2)]
  107.  .O..O
  108.  O....
  109.  O...O
  110.  OOOO.
  111.  
  112.  
  113. [MWSS (glide-reflective, period 4, speed c/2)]
  114.  ...O..
  115.  .O...O
  116.  O.....
  117.  O....O
  118.  OOOOO.
  119.  
  120.  
  121. [HWSS (glide-reflective, period 4, speed c/2)]
  122.  ...OO..
  123.  .O....O
  124.  O......
  125.  O.....O
  126.  OOOOOO.
  127.  
  128.  
  129. The glider is the most basic spaceship.  Since it is so small, it appears
  130. spontaneously from random objects.  Collisions between gliders produce
  131. many useful things.  For example, two gliders can produce another glider,
  132. and three gliders can produce a LWSS or MWSS or a HWSS.  Gliders can be
  133. produced indefinitely by many kinds of "glider guns".  The first glider gun
  134. was found by Bill Gosper in 1970, and was the first example of a Life object
  135. whose population grew arbitrarily large.
  136.  
  137. The three orthogonal spaceships are very useful because of the presence of
  138. their "sparks".  Sparks are cells at the edge of an object which die off,
  139. and which can perturb other objects without destroying the object which
  140. generates the spark.  The commonest use of sparks from these spaceships is
  141. to perturb an "engine" to produce puffer trains, or to modify stationary
  142. objects when the spaceships pass by.
  143.  
  144. The three orthogonal spaceships above show an obvious pattern, and the
  145. casual Life-player might wonder why the pattern cannot be continued to
  146. make even larger spaceships.  This will not work directly because the
  147. sparks do not die off anymore for larger ships, but wreck the ship.
  148.  
  149. The following for example, doesn't work because the spark at the top
  150. is actually a blinker, and doesn't die.  Without the blinker, this object
  151. is known as an OWSS (overweight spaceship).  This name is also given to
  152. even larger objects following the same pattern.
  153.  
  154. [non-working OWSS]
  155.  ...OOO..
  156.  .O.....O
  157.  O.......
  158.  O......O
  159.  OOOOOOO.
  160.  
  161.  
  162. It was discovered rather early that an OWSS can survive if it is "escorted"
  163. by other smaller spaceships.  The escorting spaceships are positioned to
  164. prevent the formation of the deadly non-sparks.  The following is an extreme
  165. example of this.  This shows the largest overweight spaceship which can be
  166. safely escorted by only two other spaceships.
  167.  
  168. [OWSS escorted by two HWSS (period 4, speed c/2)]
  169.  ....OOOO.......
  170.  ...OOOOOO......
  171.  ..OO.OOOO......
  172.  ...OO..........
  173.  ...............
  174.  ...........OO..
  175.  .O............O
  176.  O..............
  177.  O.............O
  178.  OOOOOOOOOOOOOO.
  179.  ...............
  180.  ...............
  181.  ....OOOO.......
  182.  ...OOOOOO......
  183.  ..OO.OOOO......
  184.  ...OO..........
  185.  
  186.  
  187. There are many other combinations of spaceships that will support one or
  188. more OWSS.  Some OWSS can be supported by a convoy of two spaceships on
  189. each side.  But for very long OWSS, no convoy of small spaceships can work
  190. to stabilize it.  However, it is possible to support an arbitrarily long
  191. OWSS by nesting different sized OWSS side by side to stabilize them all,
  192. with final small spaceships on the outside.
  193.  
  194. The next topic related to spaceships is called a tagalong.  A tagalong is
  195. something which follows behind one or more spaceships, and needs the
  196. spaceships in order to survive.  Generally, tagalongs are attached to the
  197. sparks of a spaceship so that they don't destroy the spaceship.  But some
  198. tagalongs attach right to the base ship itself, and some even need some
  199. modification of the base ships in order to work.  A tagalong along with its
  200. base ship can be considered as a large spaceship.
  201.  
  202. One of the first tagalongs was found a couple of years into the history of
  203. Life.  This is the Schick engine, found by Paul Schick in 1972.  It uses
  204. the sparks from two adjacent LWSS to keep the engine going.
  205.  
  206. [Schick engine tagalong (period 12, speed c/2)]
  207.  OOOO.....
  208.  O...O....
  209.  O........
  210.  .O..O..OO
  211.  ......OOO
  212.  .O..O..OO
  213.  O........
  214.  O...O....
  215.  OOOO.....
  216.  
  217.  
  218. This tagalong is very useful, because it splits into two separate parts.
  219. The back part dies off on its own.  But it can be perturbed by adjacent
  220. LWSS, MWSS, or HWSS in many ways to produce output which remains.  It
  221. then becomes a puffer train.  For example, adding one LWSS gives:
  222.  
  223. [Simple puffer train producing pairs of beehives (period 24, speed c/2)]
  224.  ...........OO.
  225.  ..........OOOO
  226.  .........OO.OO
  227.  ..........OO..
  228.  OOOO..........
  229.  O...O.........
  230.  O.............
  231.  .O..O..OO.....
  232.  ......OOO.....
  233.  .O..O..OO.....
  234.  O.............
  235.  O...O.........
  236.  OOOO..........
  237.  
  238.  
  239. If a second LWSS is also placed at the bottom of the above object
  240. symmetrically to the top LWSS, then the puffer produces a stream of
  241. blinkers with period 12.
  242.  
  243. A tagalong can be changed into a puffer engine by perturbations as in
  244. the above example.  The reverse can also happen.  A puffer engine can
  245. be tamed and turned into a tagalong.  This can generally be done by
  246. using passing spaceships to destroy all of the puffer output.  Such an
  247. object will then be a large spaceship.  I will give two examples.
  248.  
  249. The first example uses a well known puffer engine, the B heptomino.  The
  250. first two puffers in Life were found by Bill Gosper and are both based on
  251. the B heptomino.  The one given here is the second one he found, where a
  252. single engine is perturbed by two LWSS to become a very dirty puffer.  It
  253. takes over 4600 generations for this puffer to settle down.  It then
  254. produces a large collection of objects with period 140.
  255.  
  256. [Dirty puffer train based on B heptomino (eventual period 140, speed c/2)]
  257.  .....
  258.  .OO..
  259.  OO.OO
  260.  .OOOO
  261.  ..OO.
  262.  .....
  263.  .....
  264.  ....O
  265.  ...OO
  266.  ..OO.
  267.  ...OO
  268.  .....
  269.  .....
  270.  .....
  271.  .....
  272.  .OO..
  273.  OO.OO
  274.  .OOOO
  275.  ..OO.
  276.  
  277.  
  278. By adding another LWSS, this dirty puffer is tamed and becomes a spaceship
  279. with period 20.  This object has a rather large spark which can then be
  280. perturbed with other spaceships to produce simple useful outputs such as
  281. gliders.
  282.  
  283. [Period 20 spaceship based on B heptomino (period 20, speed c/2)]
  284.  ..........O..O........
  285.  .OO......O............
  286.  OO.OO....O...O........
  287.  .OOOO....OOOO.........
  288.  ..OO..................
  289.  ......................
  290.  ...........O..........
  291.  ....O...O....O........
  292.  ...OO....O...O...OO.OO
  293.  ..OO.....O........O..O
  294.  ...OO.............OOO.
  295.  ............O..O......
  296.  .............OO.......
  297.  ......................
  298.  ......................
  299.  .OO...................
  300.  OO.OO.................
  301.  .OOOO.................
  302.  ..OO..................
  303.  
  304.  
  305. The second example is based on a puffer discovered by Bob Wainwright
  306. in 1984.  The period of this puffer is only eight, which is the minimum
  307. puffer period known.  (There are several other different period 8 puffers
  308. known.)  The one shown here produces a row of blinkers.
  309.  
  310. [Period 8 puffer train producing blinkers (speed c/2)]
  311.  ...O.....
  312.  .O...O...
  313.  O........
  314.  O....O...
  315.  OOOOO....
  316.  .........
  317.  .........
  318.  .........
  319.  .OO......
  320.  OO.OOO...
  321.  .OOOO....
  322.  ..OO.....
  323.  .........
  324.  .....OO..
  325.  ...O....O
  326.  ..O......
  327.  ..O.....O
  328.  ..OOOOOO.
  329.  
  330.  
  331. By using a passing HWSS, the blinkers can be deleted, producing a true
  332. spaceship which can be made as large as desired by moving the trailing
  333. HWSS back.
  334.  
  335. [Period 8 spaceship (speed c/2)]
  336.  ...O.............
  337.  .O...O...........
  338.  O................
  339.  O....O.....OO....
  340.  OOOOO.....OO.OOOO
  341.  ...........OOOOOO
  342.  ............OOOO.
  343.  .................
  344.  .OO..............
  345.  OO.OOO...........
  346.  .OOOO...OOO.OOO..
  347.  ..OO.............
  348.  .................
  349.  .....OO..........
  350.  ...O....O........
  351.  ..O..............
  352.  ..O.....O........
  353.  ..OOOOOO.........
  354.  
  355.  
  356. By using different puffers, and deleting the output in many many different
  357. ways, a very large number of spaceships can be produced.  But they all
  358. have a few things in common.  All of these orthogonal spaceships use the
  359. LWSS, MWSS, or HWSS as essential components.  Therefore they must all have
  360. a speed of c/2, and a period which is a multiple of four.  The question
  361. arises as to whether there are some spaceships which move at different
  362. speeds, have other periods, or don't make use of the normal spaceships.
  363. The answer is YES, and is why this area has been exciting in the last
  364. few years.
  365.  
  366. Before proceeding to these new things, I will recap two tantalizing
  367. early results which showed that possibly such ships might be found.
  368.  
  369. This first one was noticed by many people, and is the pi heptomino.
  370. The following is generation 1 of the pi heptomino.  It reappears 30
  371. generations later, with a translation of 9, for a very obscure speed
  372. of 3c/10.
  373.  
  374. [generation 1 of pi heptomino, a non-working spaceship]
  375.  ..O
  376.  .OO
  377.  O..
  378.  .OO
  379.  ..O
  380.  
  381.  
  382. Unfortunately, it also produces a large amount of other debris which
  383. then quickly destroys the object.  That debris can be controlled by
  384. carefully placed blocks in its path, or by placing many copies of the
  385. pi heptomino side by side.  But all such constructions must be carried
  386. out to infinity to work forever.  No one has figured out how to make a
  387. finite object based on this work.
  388.  
  389. The second tantalizing result was discovered by Charles Corderman in 1971
  390. while doing an exhaustive search of polyominoes.  A small object was
  391. discovered which translated itself diagonally by 8 cells, with some other
  392. debris remaining.  The debris doesn't interfere immediately with the object,
  393. and so it translates itself again.  Only after many such translations does
  394. the debris catch up to the engine and destroy it.  Corderman found that by
  395. perturbing the debris in various ways, or by placing multiple copies of the
  396. engine alongside each other, the engine can survive forever.  However, in
  397. none of these cases was it a spaceship.  It was instead a puffer, and left
  398. debris behind.  The following is one of the simplest of these puffers, and
  399. leaves just blocks behind.
  400.  
  401. [Switch Engine puffer train (diagonal to upper left, glide-reflective,
  402. period 288, speed c/12)]
  403.  .O.O........................
  404.  O...........................
  405.  .O..O.......................
  406.  ...OOO......................
  407.  ............................
  408.  ..........................OO
  409.  ..........................O.
  410.  
  411.  
  412. The above object is one of the smallest known objects whose population grows
  413. arbitrarily large.  (All of these are based on the switch engine and have
  414. only 11 ON cells.)  The only known diagonal puffer trains are all based on
  415. the switch engine.  But no one succeeded in taming the debris completely to
  416. create a spaceship until Dean Hickerson did this in April, 1991.  He did
  417. this by placing a large number of switch engines together so as to eliminate
  418. all debris.  His original ship required 13 switch engines, but his smaller
  419. one given here only uses 10 of them.  The number of them needed can possibly
  420. be reduced even further, but this isn't known.
  421.  
  422. The spaceship is just a little too wide to be seen in an 80 column width,
  423. so the description below is compressed in the following manner.  Each
  424. dollar sign represents 10 empty cells.  Just use an editor to replace
  425. each dollar sign by 10 periods, and you will be able to reconstruct the
  426. picture of the full object.
  427.  
  428. [Cordership (diagonal to upper right, symmetrical, period 96, speed c/12)]
  429.  $$$.....OO$$$$$
  430.  $$$.....O...OO$$$$......
  431.  $$$....O......O.......OOO$$$.....
  432.  $$$..OOOOO...O.....OOO$$$........
  433.  $$$.....O...O......OOO$$$........
  434.  $$$..O..O$.O$$$.........
  435.  $$....OO.......OO$$$$$..
  436.  $$....OO$$$$$$.
  437.  $$$$$$$$.......
  438.  $$$$$........O$$........
  439.  $$$$$........O$$........
  440.  $$$$$........O$$........
  441.  $$$$$......OO$$.........
  442.  $$$$$.....OOO$$.........
  443.  $......OO$$$........OO$$.........
  444.  $......OO$$$$$$.........
  445.  $$$$$$$$.......
  446.  $$$$$$$$.......
  447.  $$$$$$$$.......
  448.  $$$$$........O$$........
  449.  $$$$$.......O$$.........
  450.  $$$$$........O$$........
  451.  ........OO$$$$$$$.......
  452.  ........OO$$$......O$$$$
  453.  $$$$.....O.O$$$.........
  454.  $$$$....OO.OO$$$........
  455.  $$$$.......OO$$$........
  456.  $$$$.OO$$$$....
  457.  $$$$...O..OOO$......O.O.......OOO.........
  458.  $$$$.OO.O$$.O.....OOO$..
  459.  OO$$$$.O..O$$.....OOO$..
  460.  OO...O.......O$$.........O$$.........O$...
  461.  ....O.O.....OOO$$.........OO$$$$.
  462.  ...O..O..OOOO.OO$$$$$$$.
  463.  .........O..OOO$$$O$$$$.
  464.  ......O..OO..O$$.........OO.OO$$$......O..
  465.  ....O.O.OO$$$....O$$$.........O..
  466.  .....O$$$$.O$$$......O..
  467.  $$$$.....O$..O.OO$$OO...
  468.  $$$$.........O.O......O.OOO$........OOO...
  469.  $$$$$.O....O.O....O$........OO...
  470.  $$$$........O...O.O......OO$$....
  471.  $$$$$OO..O..O...O$$.....
  472.  $$$$$.O...OO.O$$........
  473.  $$$$$.......O.O$$.......
  474.  $$.......O$$.........O.O$$....O..
  475.  $$......OOO$$$$$....O.O.
  476.  $$.....OO.OO$$$$$..O..O.
  477.  $$......OOO$$$$$........
  478.  $$.......O$$$$$.........
  479.  $$.....O.O$$$$$.....O..O
  480.  $$....OOOO$$$$$...OOO.OO
  481.  $$....O$$$$$.....O..OO..
  482.  $$$$$$$$O..O...
  483.  $$....OO.OO$$$$$..O.O...
  484.  $$...O.....O$$$$$.......
  485.  $$....O...O$$$$$........
  486.  $$.......O...O.......O$$$$.......
  487.  $$$O.O.....OOO$$$$......
  488.  $$.........O..O..OOOO.OO$$$$.....
  489.  $$$.....O..OOO$$$$......
  490.  $$$..O..OO..O$$$.........OO......
  491.  $$$O.O.OO$$$$...OO......
  492.  $$$.O$$$$$.....
  493.  $$$$$$$$.......
  494.  $$$$$$$$.......
  495.  $$$$$$$$.......
  496.  $$$$$$$$.......
  497.  $$$$$$$$.......
  498.  $$$$$$$.OO$....
  499.  $$$$$$$.OO$....
  500.  $$$$$...O$$$...
  501.  $$$$$..OOO$$$..
  502.  $$$$$.OO.OO$$$.
  503.  $$$$$..OOO$$$..
  504.  $$$$$...O$$$...
  505.  $$$$$.O.O$$$...
  506.  $$$$$OOOO.........OO$$..
  507.  $$$$$O$..OO$$..
  508.  $$$$$$$$.......
  509.  $$$$$OO.OO$$$..
  510.  $$$$.........O.....O$$$.
  511.  $$$$$O...O$$$..
  512.  $$$$$...O$$$...
  513.  $$$$$$$$.......
  514.  $$$$$.....OO$$$
  515.  $$$$$.....OO$$$
  516.  
  517.  
  518. The Cordership has lots of debris that dies away.  Gliders can hit this
  519. debris and do interesting things.  In particular, gliders can be turned
  520. by 90 or 180 degrees by hitting the debris appropriately.  Dean Hickerson
  521. has used this fact to create some interesting constructions, such as
  522. reflecting gliders back and forth forever between two Corderships that are
  523. slowly pulling apart.
  524.  
  525. The Corderships form one of several new classes of spaceships, ending a
  526. period of about 20 years when no new classes were found.  However, it was
  527. not the first of these new classes.  The next part of this series will begin
  528. exploring these new classes in earnest, starting with the c/2 period 2
  529. spaceships.
  530.  
  531. That next article should appear in about two weeks.
  532.