The Garden of Eden theorem for cellular automata on group sets. Issue 1 (2nd January 2019)

• Record Type: Journal Article
• Authors: Wacker, Simon
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 34:Issue 1(2019)
• Page Start: 78
• Page End: 114
• Publication Date: 2019-01-02
• Subjects: Cellular automata -- group actions -- homogeneous spaces -- amenability -- entropy -- Garden of Eden theorem; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2017.1337900
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: We prove the Garden of Eden theorem for big-cellular automata with finite set of states and finite neighbourhood on right amenable left homogeneous spaces with finite stabilisers. It states that the global transition function of such an automaton is surjective if and only if it is pre-injective. Pre-Injectivity means that two global configurations that differ at most on a finite subset and have the same image under the global transition function must be identical. The theorem is proven by showing that the global transition function of an automaton as above is surjective if and only if its image has maximal entropy and that its image has maximal entropy if and only if it is pre-injective. Entropy of a subset of global configurations measures the asymptotic growth rate of the number of finite patterns with growing domains that occur in the subset. Graphical Abstract: Surjectivity, depicted on the left, is equivalent to pre-infectivity, depicted on the right, for global transition functions of certain cellular automata.