Inverse and injectivity of parallel relations induced by cellular automata

Yaku, Takeo

doi:10.1090/S0002-9939-1976-0444346-6

Inverse and injectivity of parallel relations induced by cellular automata
HTML articles powered by AMS MathViewer

by Takeo Yaku PDF

Proc. Amer. Math. Soc. 58 (1976), 216-220 Request permission

Abstract:

Moore and Myhill showed that Garden-of-Eden theorem [2], [3]. A binary relation over the configurations is said to be “parallel” if it is induced by a cellular (tessellation) automaton. Richardson showed the equivalence between a parallel relation (a nondeterministic parallel map) with the quiescent state to be injective and its inverse to be parallel by the Garden-of-Eden theorem plus compactness of product topology [4]. This paper deals with the inverse and the injectivity when a cellular automaton is given that induces a parallel relation. We give an equivalent condition, concerning only the local map, for the inverse of a parallel relation to be parallel. Furthermore we show an equivalent condition, concerning only the local map, for the injectivity of a parallel map. Consequently, we note that these two conditions are represented by semirecursive predicates.

References

S. Amoroso and G. Cooper, The Garden-of-Eden theorem for finite configurations, Proc. Amer. Math. Soc. 26 (1970), 158–164. MR 276007, DOI 10.1090/S0002-9939-1970-0276007-5

Machine models of self-reproduction

John Myhill, The converse of Moore’s Garden-of-Eden theorem, Proc. Amer. Math. Soc. 14 (1963), 685–686. MR 155764, DOI 10.1090/S0002-9939-1963-0155764-9
D. Richardson, Tessellations with local transformations, J. Comput. System Sci. 6 (1972), 373–388. MR 319678, DOI 10.1016/S0022-0000(72)80009-6
Takeo Yaku, The constructibility of a configuration in a cellular automaton, J. Comput. System Sci. 7 (1973), 481–496. MR 332397, DOI 10.1016/S0022-0000(73)80004-2
Takeo Yaku, Surjectivity of nondeterministic parallel maps induced by nondeterministic cellular automata, J. Comput. System Sci. 12 (1976), no. 1, 1–5. MR 416802, DOI 10.1016/S0022-0000(76)80013-X