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

Self-Organized Construction in Sparse Random Arrays of Conway’s Game of Life

Self-Organized Construction in Sparse Random Arrays of Conway’s Game of Life

(p.1) Self-Organized Construction in Sparse Random Arrays of Conway’s Game of Life
New Constructions in Cellular Automata

Nicholas M. Gotts

Oxford University Press

The construction problems and techniques described in this chapter arose out of a single problem: . . . What happens in very low density infinite random arrays of Conway’s Game of Life? . . . However, the work reported has wider implications, briefly discussed in the final section. Conway’s Game of Life (henceforth GoL) is a deterministic cellular automaton (CA), which is binary (a cell has two possible states: 0 and 1) and runs on an infinite two-dimensional grid of cells. A deterministic CA cell’s state at time step t is determined, according to a transition rule, by those of a set of in-neighbors at step t — 1, and its own state at step t — 1 can affect the state of i out-neighbors at t. In GoL, in-neighbors and out-neighbors coincide, and include the cell itself. The neighborhood is a 3 x 3 square of cells. GoL’s transition rule specifies that a cell is in state 1 at step t if and only if either of the following held at t - 1. 1. The cell and either two or three other cells in its neighborhood were in state 1. 2. The cell was in state 0, and exactly three other cells in its neighborhood were in state 1. By a random array, I mean one in which the initial probability p of each cell being in state 1 is the same for all cells, and the initial state is determined independently for each cell. Of course, we cannot actually construct such an array, but we can reason about it. Toward the end of the chapter, large finite random arrays will be considered, but it is simpler to start with the infinite case. In fact, none of the reasoning used in the infinite case depends upon the distribution of state 1 cells being strictly random, provided the frequency of all finite arrangements of cell-states is as expected in a random array with the same density of state 1 cells. A sparse random array is one in which p is very low (a more precise definition is given below).

Keywords:   adjustment fleets, blinkers, finite-difference classes, global configurations, lightweight spaceships, nicely-ordered fleets, orphan chunks, quiet clusters, rakes

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 .