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.


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.

  • $\begingroup$ 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. $\endgroup$ – Shaull Apr 15 at 17:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Ilkka Törmä Apr 15 at 17:58
  • $\begingroup$ 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! $\endgroup$ – Shaull Apr 15 at 18:10
  • $\begingroup$ @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$. $\endgroup$ – Ilkka Törmä Apr 15 at 18:38
  • $\begingroup$ Thanks @Ilkka Törmä! I agree this encoding somewhat kills my hope for semilinearity :) $\endgroup$ – Shaull Apr 15 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.