patternMinor
What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?
Viewed 0 times
thewhatwithcellularsizeautomataedenpatternsgardenincreasing
Problem
-
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.
-
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.)
-
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 h
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.
-
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.)
-
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 h
Solution
-
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
-
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.
At the time of writing I don't see how to prove that the problem is NP
-
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.
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
-
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
-
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.
Context
StackExchange Computer Science Q#22532, answer score: 2
Revisions (0)
No revisions yet.