# Is the following restriction of cellular automata / tile assembly / CRN a known model?

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.
• 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. Apr 15 at 17:02
• @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. Apr 15 at 17:58
• @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$. Apr 15 at 18:38