2
$\begingroup$

This question tries to get right what went wrong in an earlier question.

Let $\{0,1\}^\mathbb{Z}$ denote the set of all functions $x:\mathbb{Z}\to \{0,1\}$. Let $+$ denote addition modulo $2$ on $\{0,1\}$ (corresponding to ${\sf XOR}$ in computer science).

Define a function $f:\{0,1\}^\mathbb{Z} \to \{0,1\}^\mathbb{Z}$ by $x \mapsto f(x)$ where $f(x):\mathbb{Z}\to\{0,1\}$ is defined by $$f(x)(i) = x(i-1) \; + \;\max\{x(i), x(i+1)\}\ \text{ for all }i\in \mathbb{Z}.$$ Inductively define $f^{(0)}(x) = x$, and $f^{(n+1)}(x) = f(f^{(n)}(x))$ for all integers $n\geq 0$.

Question. For what integers $n>1$ is there $x\in \{0,1\}^\mathbb{Z}$ such that $f^{(n)}(x) = x$ but $f^{(k)}(x) \neq x$ for all integers $k\geq 1$ with $k<n$?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I think Rule 30 is $f(x)(i)=x(i-1)+\max\{x(i),x(i+1)\}$. $\endgroup$
    – Johan Kopra
    Commented Aug 31, 2022 at 14:55
  • 2
    $\begingroup$ To others who like me don't want to waste time trying to decipher the formulas, you can find the explicit rule table for Rule 30 for instance here $\endgroup$
    – Wojowu
    Commented Aug 31, 2022 at 14:59
  • 3
    $\begingroup$ Which rule do you want? The formula describes a CA that's not even surjective and is left-right symmetric, again of completely different nature than Rule 30. $\endgroup$
    – Ville Salo
    Commented Aug 31, 2022 at 16:42
  • 2
    $\begingroup$ This formula is not giving rule 30. It differs on 101 and 011. $\endgroup$
    – Dan Turetsky
    Commented Aug 31, 2022 at 18:42
  • 2
    $\begingroup$ If you mean "periodic points", this is sometimes called "omniperiodicity". (At least in the cellular automaton context.) $\endgroup$
    – Ville Salo
    Commented Sep 1, 2022 at 6:30

1 Answer 1

Reset to default
4
$\begingroup$

A partial answer: Table A.1 of https://core.ac.uk/download/pdf/236376428.pdf lists the number of preperiodic points with minimal preperiod $q$ and minimal period $p$ with small $q$ and $p$ for various elementary cellular automata. For example, for Rule 30 and for $q=0$, $p=1,2,3,4,5,6$ these cardinalities are $3,0,12,28,45,84$ and in particular there does not exist a configuration with minimal period $2$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ A few more data points: number of periodic points of period 1: 3; period 2: 3; period 3: 15; period 4: 31; period 5: 48; period 6: 99; period 7: 108; period 8: 119; period 9: 195; period 10: 598. (Non-minimal periods, do inclusion-exclusion to convert.) $\endgroup$
    – Ville Salo
    Commented Sep 1, 2022 at 8:43
  • $\begingroup$ Thanks to Johan for this partial answer - I won't accept it yet, I hope you don't mind. Thanks also to Ville Salo for the additional information! $\endgroup$
    – Dominic van der Zypen
    Commented Sep 1, 2022 at 15:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .