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: 04 August 2021

A Two-Dimensional Cellular Automaton Crystal with Irrational Density

A Two-Dimensional Cellular Automaton Crystal with Irrational Density

(p.78) (p.79) A Two-Dimensional Cellular Automaton Crystal with Irrational Density
New Constructions in Cellular Automata

David Griffeath

Dean Hickerson

Oxford University Press

We solve a problem posed recently by Gravner and Griffeath [4]: to find a finite seed A0 of 1s for a simple {0, l}-valued cellular automaton growth model on Z2 such that the occupied crystal An after n updates spreads with a two-dimensional asymptotic shape and a provably irrational density. Our solution exhibits an initial A0 of 2,392 cells for Conway’s Game Of Life from which An cover nT with asymptotic density (3 - √5/90, where T is the triangle with vertices (0,0), (-1/4,-1/4), and (1/6,0). In “Cellular Automaton Growth on Z2: Theorems, Examples, and Problems” [4], Gravner and Griffeath recently presented a mathematical framework for the study of Cellular Automata (CA) crystal growth and asymptotic shape, focusing on two-dimensional dynamics. For simplicity, at any discrete time n, each lattice site is assumed to be either empty (0) or occupied (1). Occupied sites after n updates grows linearly in each dimension, attaining an asymptotic density p within a limit shape L: . . . n-1 A → p • 1L • (1) . . . This phenomenology is developed rigorously in Gravner and Griffeath [4] for Threshold Growth, a class of monotone solidification automata (in which case p = 1), and for various nonmonotone CA which evolve recursively. The coarse-grain crystal geometry of models which do not fill the lattice completely is captured by their asymptotic density, as precisely formulated in Gravner and Griffeath [4]. It may happen that a varying “hydrodynamic” profile p(x) emerges over the normalized support L of the crystal. The most common scenario, however, would appear to be eq. (1), with some constant density p throughout L. All the asymptotic densities identified by Gravner and Griffeath are rational, corresponding to growth which is either exactly periodic in space and time, or nearly so. For instance, it is shown that Exactly 1 Solidification, in which an empty cell permanently joins the crystal if exactly one of its eight nearest (Moore) neighbors is occupied, fills the plane with density 4/9 starting from a singleton.

Keywords:   Exactly, Stifled Breeder pattern, blocks, golden string, lightweight spaceships, medium-weight spaceships, puffers, solidification rules

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 .