<p>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.</p>

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

<p>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}$.</p>

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

<p>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:</p>

<p>Suppose that $s\in A^{*}$. Then let $x\in B^{G}$ be the string where
$x[g^{i}]=s[i]$ whenever $i&lt;|s|$ and $x[h]=0$ whenever $h\not\in\{e,...,g^{|s|-1}\}$. Then there is some natural number $n&lt;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$.</p>

<p>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$?</p>

CC BY-SA 4.0
2018-09-15T00:56:12.963Z
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.
Steven Stadnicki
CC BY-SA 4.0
2018-09-15T17:08:21.470Z
It's the product topology over the discrete topology. (A topological space, not a metric space). See https://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem for the characterization of cellular automata in terms of continuous equivariant functions.
David Eppstein
<gr.group-theory><cellular-automata>
When do cellular automata on non-abelian groups not offer a computational speed up?
Joseph Van Name
# When do cellular automata on non-abelian groups not offer a computational speed up?

(Asked by: username_0 on 2018-09-13)

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

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$?

**Tags:** gr.group-theory, cellular-automata
> **Comments:**
> **username_1**: 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.  
> **username_2**: It's the product topology over the discrete topology. (A topological space, not a metric space). See https://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem for the characterization of cellular automata in terms of continuous equivariant functions.  

---

## 0 answers

