InterJournal Complex Systems, 1056
Status: Accepted
Manuscript Number: [1056]
Submission Date: 2004
A Robust Game of Life
Author(s): Thomas Portegys ,Janet Wiles

Subject(s): CX.1

Category:

Abstract:

We propose a Game of Life enhancement in which disrupting noise in the form of random state changes is corrected. This enhancement does not change the original rules: a noiseless enhanced run is identical to an unenhanced run. To an extent the rules of Life provide for a certain level of self-correction, for example, a cell becoming alive due to noise in a neighborhood of dead cells will immediately die. However, in general the game is quite fragile. The error-correction scheme is based on a plausible mechanism for a networked node configuration involving propagating state information. Cells in the grid are visible to each other at the "speed of light" (one cell per step), limited by a maximum range. A cell uses this "light cone" information to construct a set of state histories for its locale. The most recent history, that of the previous step, is the conventional 3x3 Life neighborhood. The histories can then be used for error-correction. A neighbor's state is compared against its neighbors' states during the previous step. If they agree according to Life rules, then the neighbor is considered to be valid. If they disagree, then an error must have occurred either in the neighbor or its neighbors. The checking then continues back in time. Once a cell's neighborhood is verified, limited by the number of available histories, its value is corrected. The noise is a probabilistic tendency to toggle the state of a cell at each step, which not only affects current states but past ones as well. We believe this scheme could be applicable to other networked state-based computing systems.

Retrieve Manuscript
Submit referee report/comment


Public Comments: