Garden of Eden States
A Garden of Eden state is a configuration with no predecessor. It can be written down as a starting arrangement, but it cannot be reached by evolving the automaton forward from any earlier configuration.
McKenna’s eschaton similarly violates ordinary historical intuition. You look at human culture and think: “History proceeds from the past.” McKenna says: not only that. The future endpoint also structures the path.
1“History is the shockwave of eschatology.”
Terence McKenna, quoted in Dominic Pettman, After the Orgy: Toward a Politics of Exhaustion (2002), Preface, p. x
2“The Eschaton is an enigmatic name applied to a transcendental object which lies at the end of history. It is the last of the Last Things.”
Dominic Pettman, After the Orgy: Toward a Politics of Exhaustion (2002), note 1, p. 183
3From these six assumptions (and perhaps other hidden ones which I have not noticed) it can be concluded that Garden-of-Eden configurations exist.
Edward F. Moore, “Machine Models of Self-Reproduction,” Proceedings of Symposia in Applied Mathematics 14 (1962), p. 31
4If G is not surjective then there exist Garden-of-Eden configurations, that is, configurations without a pre-image.
- Theorem 6 (Garden-of-Eden theorem, Moore [53] and Myhill [55]). GF is injective if and only if G is surjective.
Jarkko Kari, “Theory of cellular automata: A survey,” Theoretical Computer Science 334 (2005), p. 16
5It was determined already in 1972 by S. Amoroso and Y. Patt that it is possible to decide if a given one-dimensional CA is reversible [2]. In the same paper, they also provided an algorithm to determine if a given CA is surjective:
- Theorem 9 (Amoroso and Patt [2]). There exist algorithms to determine if a given one-dimensional CA is injective or surjective.
Jarkko Kari, “Theory of cellular automata: A survey,” Theoretical Computer Science 334 (2005), p. 22
6In higher-dimensional spaces the questions are, however much harder. It was shown in [38,41] that
- Theorem 10 (Kari [41]). There are no algorithms to determine if a given two-dimensional CA is injective or surjective.
Jarkko Kari, “Theory of cellular automata: A survey,” Theoretical Computer Science 334 (2005), p. 22
Bibliography
- Serafino Amoroso and Yale N. Patt, “Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures,” Journal of Computer and System Sciences 6(5) (1972).
- Jarkko Kari, “Theory of cellular automata: A survey,” Theoretical Computer Science 334 (2005).
- John Myhill, “The converse of Moore’s Garden-of-Eden theorem,” Proceedings of the American Mathematical Society 14 (1963).
- Edward F. Moore, “Machine Models of Self-Reproduction,” Proceedings of Symposia in Applied Mathematics 14 (1962).
- Dominic Pettman, After the Orgy: Toward a Politics of Exhaustion (Albany: SUNY Press, 2002).