2010 | OriginalPaper | Buchkapitel
The Garden of Eden Theorem
verfasst von : Tullio Ceccherini-Silberstein, Michel Coornaert
Erschienen in: Cellular Automata and Groups
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Garden of Eden Theorem gives a necessary and sufficient condition for the surjectivity of a cellular automaton with finite alphabet over an amenable group. It states that such an automaton is surjective if and only if it is pre-injective. As the name suggests it, pre-injectivity is a weaker notion than injectivity. It means that any two configurations which have the same image under the automaton must be equal if they coincide outside a finite subset of the underlying group (see Sect. 5.2). We shall establish the Garden of Eden theorem in Sect. 5.8 by showing that both the surjectivity and the pre-injectivity are equivalent to the maximality of the entropy of the image of the cellular automaton. The entropy of a set of configurations with respect to a Følner net of an amenable group is defined in Sect. 5.7. Another important tool in the proof of the Garden of Eden theorem is a notion of tiling for groups introduced in Sect. 5.6. The Garden of Eden theorem is used in Sect. 5.9 to prove that every residually amenable (and hence every amenable) group is surjunctive. In Sect. 5.10 and Sect. 5.11, we give simple examples showing that both implications in the Garden of Eden theorem become false over a free group of rank two. In Sect. 5.12 it is shown that a group G is amenable if and only if every surjective cellular automaton with finite alphabet over G is pre-injective. This last result gives a characterization of amenability in terms of cellular automata.