6
$\begingroup$

Let $A$ be a finite set, and suppose $0\in A$.

For each $a\in A\setminus\{0\}$, let $w_{a}$ be a positive integer called the weight of $a$, and let $w_{0}=0$. Give $A$ the discrete topology and $A^{\mathbb{Z}}$ the product topology. We say that a mapping $\phi:A^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}$ is a one-dimensional cellular automaton if $\phi$ is continuous and if $\phi\tau=\tau\phi$ where $\tau(x_{n})_{n\in\mathbb{Z}}=(x_{n-1})_{n\in\mathbb{Z}}$ is the shift map. Let $\Sigma(x_{n})_{n\in\mathbb{Z}}=\sum_{n\in\mathbb{Z}}w_{x_{n}}$. We say that $\phi$ is conservative for the weights $(w_{a})_{a\in A}$ if $\Sigma(\mathbb{x})=\Sigma(\phi(\mathbb{x}))$ for all $\mathbb{x}\in\mathbb{A}^{\mathbb{Z}}$.

Suppose that $f,g:\mathbb{N}\rightarrow\mathbb{N}$ are strictly increasing and nowhere zero. Then we say that $f\simeq g$ if there are $r,s$ where $f(n)\leq r\cdot g(rn)$ and $g(n)\leq s\cdot f(sn)$ for all $n$.

Suppose now that $\Sigma(\mathbb{x})<\infty$. Then define the width $W(\mathbb{x})=\max(\{m-n|x_{m}\neq 0,y_{n}\neq 0\})$.

Let $G(\phi,\mathbb{x}):\mathbb{N}\rightarrow\mathbb{N}$ be defined by $G(\phi,\mathbb{x})(n)=W(\phi^{n}(\mathbb{x}))$.

Easier question: Let $f_{r}:\mathbb{N}\rightarrow\mathbb{N}$ be the function where $f_{r}(n)=\lfloor 1+n^{r}\rfloor$. Are the real numbers $r\in[0,1]$ such that $f_{r}\simeq G(\phi,\mathbb{x})$ for some conservative $\phi$ and $\mathbb{x}$ with $\Sigma(\mathbb{x})<\infty$ precisely the rational numbers? What if we required each $\phi$ to also be reversible.

Harder question: Is there a characterization of the set of all functions $f$ where $f\simeq G(\phi,\mathbb{x})$ for some $\phi$ which is conservative with respect to some system of weights and $\mathbb{x}$? What if each $\phi$ were also required to be reversible?

$\endgroup$
3
  • $\begingroup$ Do you have a construction in mind that realizes all the rational numbers? $\endgroup$
    – MTyson
    Oct 19, 2017 at 14:06
  • 1
    $\begingroup$ For square root expansion, simply take a moving blue particle trapped between two red particles. When the blue particle hits a red particle, the blue particle bounces in the other direction and the red particle is pushed one unit away. More complicated constructions can make $\sqrt[n]{x}$ growth and other fractional rational power growth rates. $\endgroup$ Oct 19, 2017 at 15:13
  • $\begingroup$ Have you (or someone else) solved this? I think it's extremely interesting and I am considering a bounty. $\endgroup$
    – Ville Salo
    Mar 16, 2021 at 9:18

0

Your Answer

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

Browse other questions tagged or ask your own question.