1
$\begingroup$

Is anyone familiar with results about properties of the limit set of the local rule for a cellular automaton? I haven't been able to find any good materials on the subject from an initial search, and I thought that someone might help refer me to such results. I recently asked the same question on a thread in math stack exchange, but maybe someone here will have a more helpful suggestion.

I am considering a cellular automaton (CA) $G$ on $\mathcal{A}^{\mathbb{Z}^d}$ with a local rule given by a local rule $f:\mathcal{A}^N\to \mathcal{A}$, where $N$ is some memory neighborhood and $\mathcal{A}$ is the finite set of states. If we denote the limit set $\Omega_G= \cap G^n \big( \mathcal{A}^{\mathbb{Z}^d}\big)$, which is a subshift, what properties can be said on $\Omega_G$ as a function of $f$? I am interesting in the following questions:

  • Is $\Omega_G$ a transitive\minimal , with respect to the shift action, if some conditions on $f$ hold?
  • Are there conditions on $f$ such that $\Omega_G$ is recurrent or linearly recurrent?

I know that there are implications of these sort if we talk instead on substitution and their limit set, but I do not know if there are similar statements for CA. I have been looking at these notes, by Jarkko Kari on his website, to try to see whether there are such statements but I haven't found any there. I also searched shortly in the book Cellular automata and groups and have not found anything productive.

Is anyone familiar with works in this direction?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

In "Rice's theorem for the limit sets of cellular automata" by Jarkko Kari it is shown that all nontrivial properties of limit sets of cellular automata are undecidable. So for none of the properties that you mention can there exist decidable conditions on $f$ that completely determine whether the property is satisfied or not.

$\endgroup$
5
  • $\begingroup$ Thank you for your answer. Looking at the paper, it does seem that these properties are undecidable. I couldn't see from the paper whether there are decidable sufficient conditions for some of the nontrivial properties. Do you happen to know about this? It seems like characterizations are impossible, but are sufficient conditions for the limit set also impossible? $\endgroup$ Commented Mar 21 at 12:55
  • $\begingroup$ For transitivity of the limit set it is sufficient that the limit set reached after a finite number of applications of $G$ (in other words, the limit set is equal to some $G^n(A^{\mathbb{Z}^d})$). Minimality of the limit set is equivalent to the limit set consisting of a single point (and in this case the limit set is necessarily equal to some $G^n(A^{\mathbb{Z}^d})$). $\endgroup$ Commented Mar 21 at 15:10
  • $\begingroup$ Are there no minimal limit sets for CA which are not just a singleton? Does that mean that the limit set is minimal if and only if the CA is nilpotent? $\endgroup$ Commented Mar 21 at 15:16
  • 1
    $\begingroup$ Every set $G^n(A^{\mathbb{Z}^d})$ contains a constant configuration, and therefore the limit set also contains some constant configuration $x$. If the limit set contains any other configurations, it is not minimal. So yes, minimality of the limit set is equivalent to nilpotency of the CA. $\endgroup$ Commented Mar 21 at 15:23
  • $\begingroup$ Okay, thank you very much for the explanations. $\endgroup$ Commented Mar 21 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.