1963/08/01 by John Myhill · 2 citations
Engineering · Mathematics · #graph theory and CDMA systems #Mathematics and Applications #Advanced Mathematical Theories #Converse #Proposition #Mathematics #Square (algebra) #Universe #State (computer science) #Space (punctuation) #Morphism #Tessellation (computer graphics) #Garden of Eden #Pure mathematics #Philosophy #Physics #Algorithm #Epistemology #Linguistics #Geometry
paper · pdf · doi:10.1090/s0002-9939-1963-0155764-9
openalex publication_date 1963/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/05
We presuppose the terminology of Moore [1]. In this paper, Moore proves that the existence of two mutually erasable configurations in a tessellation universe is a sufficient condition for the existence of Garden-of-Eden configurations therein. We shall show that this condition2 is both necessary and sufficient. By an environment is meant a specification of states for all cells of the entire two-dimensional tessellation space with the exception of a square piece. By the insertion E(C) of a configuration3 C of appropriate size into an environment E is meant simply the result of specifying the states of the unspecified cells of E to be the states of the corresponding cells of C. By the sequent E(C)' of C in E is meant the state of the universe at t = 1, if E(C) is the state of the universe at t=O. Two configurations C,, C2 of the same size are said to be distinguished by the environment E, if E(C1)' ,E(C2)'. Moore's argument shows that if there are two configurations which cannot be distinguished, there are Garden-of-Eden configurations. For the converse proposition suppose if possible that every pair of configurations can be distinguished, and that there exists a (square) Garden-of-Eden configuration G of side n. We easily establish the