Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

The Garden-of-Eden theorem for finite configurations


Authors: S. Amoroso and G. Cooper
Journal: Proc. Amer. Math. Soc. 26 (1970), 158-164
MSC: Primary 94.40
MathSciNet review: 0276007
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In [1] Moore showed that the existence of mutually erasable configurations in a two-dimensional tessellation space is sufficient for the existence of Garden-of-Eden configurations. In [2] Myhill showed that the existence of mutually indistinguishable configurations is both necessary and sufficient for the existence of Garden-of-Eden configurations.

After redefining the basic concepts with some minor changes in terminology, and after restating the main results from [l] and [2], we shall establish the equivalence between the existence of mutually erasable configurations and the existence of mutually indistinguishable configurations. This implies that the converse of Moore's result is true as well. We then show that by limiting the universe to the set of all finite configurations of the tessellation array, both of the above conditions remain sufficient, but neither is then necessary. Finally, we establish a necessary and sufficient condition for the existence of Garden-of-Eden configurations when only finite configurations are considered.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 94.40

Retrieve articles in all journals with MSC: 94.40


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1970-0276007-5
Keywords: Garden-of-Eden, self-reproducing, automata, tessellation automata, cellular automata, iterative arrays
Article copyright: © Copyright 1970 American Mathematical Society