Jump to ContentJump to Main Navigation
New Constructions in Cellular Automata$
Users without a subscription are not able to see the full content.

David Griffeath and Cristopher Moore

Print publication date: 2003

Print ISBN-13: 9780195137170

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195137170.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 19 October 2021

Synthesis Of Complex Life Objects From Gliders

Synthesis Of Complex Life Objects From Gliders

(p.54) (p.55) Synthesis Of Complex Life Objects From Gliders
New Constructions in Cellular Automata

Mark D. Niemiec

Oxford University Press

Life, like many other cellular automata, contains many interesting objects, such as still lifes, oscillators, spaceships, spaceship guns, puffer trains, breeders, and the like. While many of these, like blocks, blinkers, and gliders, occur naturally with great frequency, there are many others that occur infrequently, and countless others that have never yet been observed in any natural context. This chapter deals with methods for synthesizing such complex objects from simple building blocks, such as gliders or other easy-to-synthesize objects. Once an object can be shown to be built in this manner, the object may be used as a building block in larger relocatable structures, such as Turing machines or universal constructors. In addition, the existence of a natural synthesis of an object from a bounded number of gliders implies that the object will form naturally in a sufficiently large, sufficiently sparse field [2]. Inasmuch as this chapter deals mainly with practical aspects of object synthesis, rather than theoretical ones, it may resemble a talk on chemical engineering, rather than abstract mathematics. All figures shown here, unless otherwise specified, show “before” and “after” images of collision sequences; the “before” sequences are shown on the left with dark cells, and the “after” sequences to the right of them in lighter cells. In some cases, unwanted debris is also generated and must be removed later; this debris is shown in the lightest color. There are several basic ways in which objects can be synthesized. The most common objects occur in great abundance in nature, so there are many random collisions of a small number of gliders that will produce them. There have been many random broth experiments conducted in Life, in which fields initialized to random initial configurations have been run until they became periodic, and then the resulting ash analyzed. The results of two such series of experiments, performed by Achim Flammenkamp [1] and Heinrich Koenig [3], are available on the Web. If the objects are sorted in order of decreasing frequency of natural occurrence, the list is also in order of increasing synthesis cost in gliders (with a few rare objects out of place).

Keywords:   Hertz oscillator, boats, computational machinery, flip-flop (defined), glider (defined), object (defined), predecessor objects, rescuable objects, spaceship (defined)

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .