This paper contains a generalization of the existing theory of Garden of Eden configurations in tessellation automata. We consider spaces of at most two dimensions but with transition functions having arbitrarily large neighborhoods. A configuration c is said to be Garden of Eden of degree n just in case there is no configuration from which c can arise in n time steps; c is Garden of Eden of minimal degree n just in case there is no smaller m such that c is Garden of Eden of degree m. Necessary and sufficient conditions for the existence of Garden of Eden configurations of higher degree (and of degree 1) are established. Results are obtained relating decision procedures for Garden of Eden configurations of degree one to decision procedures for Garden of Eden configurations of higher degree.
CitationDownload as .RIS
MCB UP Ltd
Copyright © 1974, MCB UP Limited