<p>If you partition <span class="math-container">$\mathbb{Z}^d$</span> into the <span class="math-container">$(d-1)$</span>-dimensional slices <span class="math-container">$S(n) := \{ \vec v | \sum_{k=1}^d \vec v_k = n \}$</span>, then your model is essentially a spacetime diagram of the <span class="math-container">$(d-1)$</span>-dimensional cellular automaton that maps <span class="math-container">$x|_{S(n)}$</span> to <span class="math-container">$x|_{S(n+1)}$</span>. The initial configuration <span class="math-container">$x|_{S(0)}$</span> has a special quiescent state everywhere except at the origin. If the CA is linear over a field of characteristic <span class="math-container">$p$</span>, then these diagrams are <span class="math-container">$p$</span>-automatic; if not, they can be quite complex, since you don't restrict <span class="math-container">$f$</span> in any way. They are not necessarily semilinear in either case. For example, it's pretty easy to embed a computation history of an arbitrary Turing machine in the configuration.</p>

CC BY-SA 4.0
2021-04-15T17:02:53.910Z
I'm not so sure about the simulation of a TM. Observe for example that starting from a fixed cell, along every axis direction (e.g., along the $(1,0,0..0)$ direction, the behaviour is semilinear). This is also true for fixed-size blocks. If TMs could be simulated, I wouldn't expect this to hold.
Shaull
CC BY-SA 4.0
2021-04-15T17:58:39.627Z
@Shauli The TM can be simulated along the direction $\vec v = (1,1,\ldots,1)$, meaning that one end of its tape is at $n \vec v$ after $n$ simulated computation steps. You're right that each column along a basis vector will be eventually periodic, but other directions can exhibit complex behavior.
Ilkka Törmä
CC BY-SA 4.0
2021-04-15T18:10:48.617Z
I agree with the intuition, but I'm still not convinced. From what I know, we need at least 3-locality for a simulation (in 1D), and here we have only 2-locality. Perhaps in higher dimension this would cause problems, but I don't see how one could use the dimensions to store the tape in a way that would enable a simulation. At any rate, your answer did give me the term "spacetime diagram", which might lead me to a good path. Thanks!
Shaull
CC BY-SA 4.0
2021-04-15T18:38:28.437Z
@Shauli You can simulate a shifted version of a 3-local CA by a 2-local CA (usually called radius-1 and radius-1/2). In 1D, the alphabet becomes $\Sigma \cup \Sigma^2$. In two steps, the CA maps $\cdots x_0 x_1 x_2 x_3 \cdots \mapsto \cdots (x_0, x_1) (x_1,x_2) (x_2,x_3) \cdots \mapsto \cdots f(x_0, x_1,x_2) f(x_1,x_2,x_3) \cdots$.
Ilkka Törmä
CC BY-SA 4.0
2021-04-15T19:03:09.607Z
Thanks @Ilkka Törmä! I agree this encoding somewhat kills my hope for semilinearity :)
Shaull
CC BY-SA 4.0
2021-04-15T14:41:57.367Z
2021-04-15T14:41:57.367Z
Ilkka Törmä
<p>Consider the following model: we work in the <span class="math-container">$d$</span>-dimensional grid <span class="math-container">$\mathbb{N}^d$</span>, and we have an alphabet <span class="math-container">$\Sigma$</span>.
The initial cell <span class="math-container">$(0,\ldots,0)\in \mathbb{N}^d$</span> is marked with some letter <span class="math-container">$\Sigma$</span>, and from that we mark each cell with a letter from <span class="math-container">$\Sigma$</span> according to its immediate predecessors. That is, we have a function <span class="math-container">$f:\Sigma^d\to \Sigma$</span>, and for each cell <span class="math-container">$(a_1,\ldots,a_d)$</span>, we mark it with
<span class="math-container">$f(\sigma_1,\ldots,\sigma_d)$</span>, where <span class="math-container">$\sigma_i$</span> is the labeling of the neighbor <span class="math-container">$(a_1,\ldots,a_i-1,\ldots, a_d)$</span>.
This means that the marking is completely determined by <span class="math-container">$f$</span> and the initial symbol.</p>
<p>Note that at the edges, where there are fewer then <span class="math-container">$d$</span> neighbors, we ignore the missing values (technically, we can assume that anything outside <span class="math-container">$\mathbb{N}^d$</span> has some constant fixed marking).</p>
<p>I want to study certain properties of this model (specifically, I want to show that it is semilinear, in a sense). But I couldn't find any resources on it.
Specifically, I would like to know if this model is Presburger-definable.</p>
<p>However, it is a very natural restriction of several models:</p>
<ul>
<li>Cellular automata: it can be thought of a single-state cellular automaton, that can only change the value of a cell once (i.e., a cellular transducer).</li>
<li>Tile Self-assembly: where the glue relations allow only a deterministic assembly, but the model is not two-dimensional.</li>
<li>Multidimensional subshifts: it's not really a shift, but it does have the same flavour of finite rules.</li>
<li>Chemical-reaction networks: I'm actually not sure if this is a restriction, but it seems somewhat related.</li>
</ul>
<p>I'd appreciate any leads on this.</p>

<machine-models><cellular-automata>
Is the following restriction of cellular automata / tile assembly / CRN a known model?
Shaull
# Is the following restriction of cellular automata / tile assembly / CRN a known model?

(Asked by: username_0 on 2021-04-13)

Consider the following model: we work in the $d$-dimensional grid $\mathbb{N}^d$, and we have an alphabet $\Sigma$.
The initial cell $(0,\ldots,0)\in \mathbb{N}^d$ is marked with some letter $\Sigma$, and from that we mark each cell with a letter from $\Sigma$ according to its immediate predecessors. That is, we have a function $f:\Sigma^d\to \Sigma$, and for each cell $(a\_1,\ldots,a\_d)$, we mark it with
$f(\sigma\_1,\ldots,\sigma\_d)$, where $\sigma\_i$ is the labeling of the neighbor $(a\_1,\ldots,a\_i-1,\ldots, a\_d)$.
This means that the marking is completely determined by $f$ and the initial symbol.

Note that at the edges, where there are fewer then $d$ neighbors, we ignore the missing values (technically, we can assume that anything outside $\mathbb{N}^d$ has some constant fixed marking).

I want to study certain properties of this model (specifically, I want to show that it is semilinear, in a sense). But I couldn't find any resources on it.
Specifically, I would like to know if this model is Presburger-definable.

However, it is a very natural restriction of several models:

* Cellular automata: it can be thought of a single-state cellular automaton, that can only change the value of a cell once (i.e., a cellular transducer).
* Tile Self-assembly: where the glue relations allow only a deterministic assembly, but the model is not two-dimensional.
* Multidimensional subshifts: it's not really a shift, but it does have the same flavour of finite rules.
* Chemical-reaction networks: I'm actually not sure if this is a restriction, but it seems somewhat related.

I'd appreciate any leads on this.

**Tags:** machine-models, cellular-automata


---

## 1 answers

### Answer by username_1 on 2021-04-15. Score: 3 | Accepted answer

If you partition $\mathbb{Z}^d$ into the $(d-1)$-dimensional slices $S(n) := \{ \vec v | \sum\_{k=1}^d \vec v\_k = n \}$, then your model is essentially a spacetime diagram of the $(d-1)$-dimensional cellular automaton that maps $x|\_{S(n)}$ to $x|\_{S(n+1)}$. The initial configuration $x|\_{S(0)}$ has a special quiescent state everywhere except at the origin. If the CA is linear over a field of characteristic $p$, then these diagrams are $p$-automatic; if not, they can be quite complex, since you don't restrict $f$ in any way. They are not necessarily semilinear in either case. For example, it's pretty easy to embed a computation history of an arbitrary Turing machine in the configuration.

> **Comments:**
> **username_0**: I'm not so sure about the simulation of a TM. Observe for example that starting from a fixed cell, along every axis direction (e.g., along the $(1,0,0..0)$ direction, the behaviour is semilinear). This is also true for fixed-size blocks. If TMs could be simulated, I wouldn't expect this to hold.  
> **username_1**: @Shauli The TM can be simulated along the direction $\vec v = (1,1,\ldots,1)$, meaning that one end of its tape is at $n \vec v$ after $n$ simulated computation steps. You're right that each column along a basis vector will be eventually periodic, but other directions can exhibit complex behavior.  
> **username_0**: I agree with the intuition, but I'm still not convinced. From what I know, we need at least 3-locality for a simulation (in 1D), and here we have only 2-locality. Perhaps in higher dimension this would cause problems, but I don't see how one could use the dimensions to store the tape in a way that would enable a simulation. At any rate, your answer did give me the term "spacetime diagram", which might lead me to a good path. Thanks!  
> **username_1**: @Shauli You can simulate a shifted version of a 3-local CA by a 2-local CA (usually called radius-1 and radius-1/2). In 1D, the alphabet becomes $\Sigma \cup \Sigma^2$. In two steps, the CA maps $\cdots x_0 x_1 x_2 x_3 \cdots \mapsto \cdots (x_0, x_1) (x_1,x_2) (x_2,x_3) \cdots \mapsto \cdots f(x_0, x_1,x_2) f(x_1,x_2,x_3) \cdots$.  
> **username_0**: Thanks @username_1! I agree this encoding somewhat kills my hope for semilinearity :)  

---

