What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?

Question

1. In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the likelihood that a random pattern is a GoE as n increases?

   Also, by the Garden of Eden-theorem, only cellular automata which are non-injective, that is, for which a given pattern may have more than one predecessor, contain Gardens of Eden.

2. Is it then in general impossible to see whether a given cellular automaton pattern at some time-step is derived from a GoE (since there could also have been a non-GoE ancestor leading to the same state)? That is, does the evolution of the CA 'wash out' the information that it is derived from a GoE? (I hope it's sufficiently clear what I mean.)

3. Furthermore, is there a relation between GoE-patterns and uncomputability/undecidability? It seems to me that if you consider the CA to be implementing some computation, then the GoEs are 'outputs that could never be produced', at least heuristically, but a brief Google search led nowhere. Perhaps asked another way, is there a relation between the existence of GoEs and the universality of a CA? I know Life is both universal and has GoEs, but I don't know about the general case. Any pointers would be much appreciated.

Having done some additional reading, I think I can strike out the third question: since reversible cellular automata that are computationally universal exist (according to wiki), there doesn't seem to be any connection between computational universality and GoEs. Now, what about universal constructors? Are there reversible universal constructors? Von Neumann's original rule happens not to be reversible, and in fact, has GoEs, but again, this need not say much.

The wikipedia page above mentions a way to emulate d dimensional irreversible CAs within d + 1 dimensional reversible ones, which readily establishes the computational universality of the latter, but I'm not sure if this holds as well for universal construction: the emulated constructor would only construct patterns on a d-dimensional sub-grid of the automaton (?).

Answer 1

1. as said by vzn, any pattern containing a Garden of Eden pattern is itself a Garden of Eden Pattern, the probability that a random nxn pattern is actually GoE goes to 1 as n goes to infinity (in the case of a non-surjective CA of course, otherwise it's 0). More precisely, it is lower bounded by $1 - \alpha^{n²}$ for some $0<\alpha<1$. Indeed, consider a fixed GoE pattern P of size $k\times k$, then the probability for a random pattern of size $n\times n$ to be a GoE is at least $1 - (\frac{1}{q^{k^2}})^{(\frac{n}{k})^2}$, where $q$ is the number of states of the CA.

2. you can generate all the possible pre-image of a given pattern in finite time and you can also test whether a pattern is a GoE so your problem is clearly decidable. It's polynomial-time decidable in 1D and NP-hard in 2D.

   • in the 1D case, a CA can be seen as a finite state transducer. So the language $L_{GoE}$ of all GoE patterns is a regular language because it is the complement of $T(Q^\ast)$ (where $T$ is the transducer and $Q$ the set of states of the CA) which is itself a regular language as the image of a regular language by a transducer. Then $T(L_{GoE})$ is also regular and its the set you asked.
   • in the 2D case, I think we can show that it is NP-hard using the classical simulation of Turing machines by Wang tiles. The rough idea is the following. Consider any NP-complete problem $L$ and take a Turing machine $T$ which is a polynomial time verifier for the problem. Then construct a CA that basically checks that the input, if written in some special alphabet $A$, encodes a successful computation $T(x,y)$ of $T$ working on input $x$ and witness $y$. If so erases everything with a special state $a\not\in A$, but keep the input x. If some error is detected produce some special state $b\not\in A$. Finally, the CA does nothing on states which are not in $A$. Now consider a pattern formed by an input $x$ surrounded by many $a$. The pattern as always itself as a preimage, but it as a GoE preimage if and only if there is some $y$ such that $T(x,y)$ says "yes", i.e. iff $x\in L$. CQFD
     At the time of writing I don't see how to prove that the problem is NP

3. as pointed-out Turing-universality is still possible without GoE patterns (in reversible CA for instance). But intrinsic universality requires GoE patterns. This comes from the fact that, first, a surjective CA only admits surjective CA as subautomata, and, second, grouping and iterating a CA doesn't change its surjectivity.

Answer 2

have not seen a strict technical definition of GOE, and one would seem to need to take into account the concept of what exactly constitutes "space" around the figure. in Life it is well determined, but for CAs in general which CA state denotes "space" needs to be defined.

1. the concept of "orphans" is relevant as cited on the wikipedia GOE page. basically there exist finite patterns called orphans that are GOEs and such that any addition around the finite pattern is also a GOE. this allows a lower bound on total GOEs, roughly, there are at least as many GOEs of a given size as there are orphans of a smaller size plus arbitrary bits surrouding the orphan. of course this is a very rough measure. on brief search did not see a paper that studied this specific question of incidence of GOEs at different sizes.

2. if you have a pattern and want to know if it has an ancestor thats a GOE, thats decidable to ask if the GOE is bounded by some size around the initial pattern because thats a finite search space (with some assumptions about how rules behave wrt "space" around the pattern). otherwise (conjecture) its undecidable (circumstantial evidence next).

3. indeed GOE testing is basically undecidable in general, in fact to any "undecidability degree" see thm 4.1 in this paper Cellular Automata and Intermediate Reachability Problems Sutner p 1006:

   Theorem 4.1. For any recursively enumerable degree $d$ there is a two-dimensional cellular automaton whose Garden-of-Eden Problem for finite configurations is of degree $d$.

Answer 3

Question 1:

I'd say that it's a function $F(k,r)$ where $k$ is the width of the neighbourhood the rules take into account (say $k=3$ in Conway) and $r$ a measure of the 'injectivity' of the rules (the probability 2 distinct configurations produce 2 distinct new states). In particular, as a first approximation, I would expect $F \propto k^2, F \propto r$.