Suppose that $G$ is a finitely generated group and $A$ is a finite set. Then we shall give $A$ the discrete topology and $A^{G}$ the product topology; in particular $A^{G}$ is compact and totally disconnected.

If $x\in A^{G}$ and $g\in G$, then define $gx\in A^{G}$ by letting $gx(h)=x(g^{-1}h)$.

We say that $F:A^{G}\rightarrow A^{G}$ is $G$-equivariant if $F(gx)=g F(x)$ for each $g\in G$ and $x\in A^{G}$.

Then a cellular automaton is a function $F:A^{G}\rightarrow A^{G}$ which is both continuous and $G$-invariant.

We say that a language $L\subseteq A^{*}$ is accepted in polynomial time by a cellular automaton over the group $G$ if there exists some $B$ with $A\subseteq B$ along with some special elements $0,u,v\in B\setminus A$, a cellular automaton $F:B^{G}\rightarrow B^{G}$, an element $g\in G$ of infinite order, and a polynomial $p$ that satisfies the following property:

Suppose that $s\in A^{*}$. Then let $x\in B^{G}$ be the string where $x[g^{i}]=s[i]$ whenever $i<|s|$ and $x[h]=0$ whenever $h\not\in\{e,...,g^{|s|-1}\}$. Then there is some natural number $n<p(|x|)$ such that $F^{n}(x)(e)\in\{u,v\}$. Furthermore, if $n$ is the least natural number such that $F^{n}(x)(e)\in\{u,v\}$, then $s\in L$ if and only if $F^{n}(x)(e)=v$.

Is there a characterization of the groups which are computable in polynomial time such that a language $L$ is accepted in polynomial time if and only if it is accepted in polynomial time by a cellular automaton over the group $G$?

  • $\begingroup$ What does 'continuous' mean in this context? I don't see any metric specified on $A^G$ and it's not immediately clear to me what sort of plausible candidate for one you're assuming. $\endgroup$ – Steven Stadnicki Sep 15 '18 at 0:56
  • 1
    $\begingroup$ It's the product topology over the discrete topology. (A topological space, not a metric space). See en.wikipedia.org/wiki/… for the characterization of cellular automata in terms of continuous equivariant functions. $\endgroup$ – David Eppstein Sep 15 '18 at 17:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.