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
DOI:
https://doi.org/10.1090/S0002-9939-1970-0276007-5
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.
-
Edward F. Moore, Machine models of self-reproduction, Proc. Sympos. Appl. Math., vol. 14, Amer. Math. Soc., Providence, R.I., 1962, pp. 17-33.
- John Myhill, The converse of Moore’s Garden-of-Eden theorem, Proc. Amer. Math. Soc. 14 (1963), 685–686. MR 155764, DOI https://doi.org/10.1090/S0002-9939-1963-0155764-9 John von Neumann, Theory of self-reproducing automata, Edited and completed by Arthur W. Burks, Univ. of Illinois Press, Urbana, 1966.
- Arthur W. Burks (ed.), Essays on cellular automata, University of Illinois Press, Urbana, Ill.-London, 1970. MR 0299409
- H. Yamada and S. Amoroso, A completeness problem for pattern generation in tessellation automata, J. Comput. System Sci. 4 (1970), 137–176. MR 265080, DOI https://doi.org/10.1016/S0022-0000%2870%2980005-8
Retrieve articles in Proceedings of the American Mathematical Society with MSC: 94.40
Retrieve articles in all journals with MSC: 94.40
Additional Information
Keywords:
Garden-of-Eden,
self-reproducing,
automata,
tessellation automata,
cellular automata,
iterative arrays
Article copyright:
© Copyright 1970
American Mathematical Society