Universality Frontier for Asynchronous Cellular Automata

We present a comprehensive overview of computational abilities of (a)synchronous cellular automata and propose a formal definition for the notion of simulation with ACAs, which, although often used implicitly, has been missing in the literature [25, 21, 38, 16]. We adopt the “adversarial” view on asynchrony, i.e. require the ACAs to be robust against any asynchronous updating (other notions such as randomized and “best-case” asynchrony have also been studied [7]). By combining various simulation techniques and known universality constructions, we assemble an explicit “universality frontier” for CAs and ACAs, i.e., the boundary between universal and non-universal computation, similarly to how it was already done for Turing machines [26] (see Figure 1). The dashed line represents the best-known upper bound on universality constructions, while the filled line represents the best-known lower bound for non-universality constructions. We further present our own contributions to both asynchronous simulation and the “universality frontier”:

• $\mathrm{■}$

  In Section 3, we introduce a simple asynchronous model of computation–the flip automata network (FAN), which have invariant computations under any asynchronous setting.

• $\mathrm{■}$

  In Section 4 we show that by using FANs as a middleman, ACAs can simulate their synchronous counterparts with just $4q$ states (and $3q$ in the $1$-dimensional case), improving on the previous constructions which had quadratic overhead.

• $\mathrm{■}$

  In Section 6 we extend the “universality frontier” by deriving a non-universality result for one-way asynchronous automata, demonstrating their computational equivalence to classical finite-state machines. This suggests that bidirectional communication is crucial to achieving universality in ACAs (which is not the case for classical CAs).

• $\mathrm{■}$

  In Section 7 we present smaller universal ACAs than previously known: a universal $3$-state von Neumann automaton and a universal $6$-state first neighbors automaton.

The classical approach to asynchronous simulation requires the “host” ACA to be of the same dimension $d$ and neighborhood $N$ as the “guest” CA–indeed, when synchronizing a distributed system, the general goal is to alter the latter as little as possible. The classical $3q^2$ real time construction by Nakamura [25, 18] (see Appendix of the full version) and $q^2+2q$ state $3$-linear time construction in [21, 38] achieve this by increasing the number of states in the “host” (given a $q$-state “guest” CA) and use one cell of the “host” to simulate one cell of the “guest”. Furthermore, these approaches require the neighborhood $N$ to be symmetric (this constraint will be investigated more in Section 5). Our new construction–based on embeddings of flip automata networks into ACAs–allows for simulations with both linear state and time overheads, which is achieved using spatial grouping of cells, as introduced in Definition 15. We also restrict the neighborhood $N$ to be either von Neumann or Moore, since these constitute the most crucial cases.

The high-level idea behind the construction of $𝔹$ is that we first construct a flip automata network $𝒜$ which simulates $A$, and then create an asynchronous cellular automaton embedding $𝒜$. To keep the construction elegant, we present it for the $2$-dimensional von Neumann neighborhood $N=((-1,0),(1,0),(0,0),(0,1),(0,-1))$ in detail, and give a sketch for Moore’s neighborhood. The generalization to any dimension $d$ is straightforward.

Consider a FAN $𝒜=(T={\mathbb{Z}}^2,S,\{f_{\text{E}},f_{\text{O}}\})$ with the same set of states as $A$, where we distinguish between two types of nodes E and O, and set $\oplus /\ominus$ to be addition and subtraction mod $|S|$. Then, for von Neumann neighborhood:

• $\mathrm{■}$

  E nodes are placed on coordinates $(2i,2j)\in {\mathbb{Z}}^2$ and we set

  $$f_{\text{E}}(s_{(1,0)},s_{(0,1)},s,s_{(-1,0)},s_{(0,-1)})=f(s_{(1,0)}\ominus s,s_{(0,1)}\ominus s,s,s_{(-1,0)}\ominus s,s_{(0,-1)}\ominus s)$$

  Intuitively, E nodes store the states of the cells in $A$ and simulate the local transition $f$

• $\mathrm{■}$

  O nodes are placed at all remaining coordinates and every $f_{\text{O}}$ computes the sum $\oplus$ of all of its E neighbors. On a high level, O nodes use addition mod $|S|$ to accumulate and pass on the information about (simulated) neighbors of E nodes

Observe the topology of $𝒜$ as presented in Figure 4–the directional indicators are only added between neighboring E and O nodes. For von Neumann neighborhood (left), the O nodes with odd coordinates will be isolated in $𝒜$ since they do not have any E neighbors. On the other hand, in the case of Moore’s neighborhood (right), the topology of $𝒜$ becomes non-uniform with different O nodes having different neighborhoods. We initialize $𝒜$ with all directional indicators pointing from E nodes to O nodes, and on every local transition, we flip all edges. Furthermore, the initial configuration $c_0$ of $A$ is encoded on the E nodes, where $T(2i)=c_0(i)$, and O nodes are initialized arbitrarily. If we first update all O nodes, flip the arrows, and update all E nodes, the state of the network will be an encoding of $G^A(c_0)$.

Finally, let us construct an asynchronous cellular automaton $𝔹=(S\times \{0,1,2,3\},N,f^{\prime },{\mathbb{Z}}^2)$ corresponding to FAN $𝒜$. First, let us define the initial configuration $c_0^{\prime }$ on $𝔹$. For each E node at $(i,j)$ we set $c_0^{\prime }(2i,2j)=c_0(i,j)2$ (tuple notation), and each O node is initialized with $s1$ where $s\in S$ arbitrary (see Figure 4). We encode directional indicators of $𝒜$ in $𝔹$ by defining a mapping $\psi$ that relies on neighboring timers $t\in \{0,1,2,3\}$ for each edge:

There are no arrows if $t$s differ by $0$ or by $2$, i.e., the node simply “ignores” such neighbors. We define the local rule function $f^{\prime }$ to be active on cell $i$ if and only if all (implicit) arrows are pointing to $i$. More formally, if a cell in state $st$ has an even timer $t$ it mimics $f_{\text{E}}$ and updates $t$ by $2$, and if it has an odd timer it mimics $f_{\text{O}}$ and again, updates $t$ by $2$ (the extension to Moore’s neighborhood is analogous):

Observe that simulated E cells will always have an even timer and O cells will always have an odd timer. Furthermore, every transition flips all local arrows by increasing the timer, thus ensuring that $𝒜$ is simulated correctly. Notice that all configurations in $𝔹$ which correspond to valid encodings of configurations of $A$ embed a FAN, hence will trivially have invariant histories. Let us confirm that our simulation satisfies Definition 15. We can define a bijective unpacking map $o$ with

which splits a cell of $c_0$ into $4$ different cells in $c_0^{\prime }$ (one E cell and three O cells). Since $𝒜$ simulates $A$ using alternations between E and O we get $G^A\prec o^{-1}\circ H^B\circ o$. We conclude that $𝔹$ (asynchronously) simulates $A$ in real time. $◀$

We can interpret the mountain-valley encoding as a $d$-dimensional mountain-valley landscape from Example 10, which slowly travels through space-time, but now, each “mountain” and each “valley” stores the state information too. The results from Proposition 16 can be improved from $4q$ to $3q$ for $1$-dimensional automata by introducing a translation inside the simulation. Notice that Moore and von Neumann neighborhood coincide for $1$-dimensional automata and are both simply first neighbors $N=(-1,0,1)$.

The high-level idea is to improve the construction from Proposition 16 by allowing E and O nodes to shift in space, which allows us to eliminate one step of our timer (at the cost of slowing down the simulation). Let us consider the mountain-valley landscape as in Example 10, which we visualized as a zigzag line in space-time. Instead of using $2$ states, we will now use a tertiary timer to encode “mountains” and “valleys”, and disallow nodes with equal values to be neighbors in our initial configuration:

$(2,1,2)\mapsto 3(3,2,3)\mapsto 1(1,3,1)\mapsto 2$

The resulting cellular automaton will still have a mountain-valley structure if launched on periodic configuration $212121212$ (see Figure 5). Now let $𝔹=(S\times \{1,2,3\},N,f^{\prime },\mathbb{Z})$ be an asynchronous cellular automaton with a timer as described above, and where each state additionally carries simulated state $s\in S$. We encode the transitions of $A$ into $𝔹$ using the following update function $f^{\prime }$ ($\oplus /\ominus$ denotes addition and subtraction mod $|S|$):

This execution paradigm can be seen as a mountain-valley landscape where each node has additionally a stage indicator. The stages (coinciding with timer values!) operate as follows:

Stage 1.

Compute the $\oplus$ sum of both of your neighbors and move to Stage 3

Stage 2.

Compute transition $f$ based on accumulated information and move to Stage 1

Stage 3.

Copy state from your right neighbor and move to Stage 2

Now consider some initial configuration $c_0=\mathrm{\dots }0100110\mathrm{\dots }$ of $A$ which we encode in $𝔹$ as $c_0^{\prime }$ where $c_0^{\prime }(2i)=c_0(i)2$ and $c_0^{\prime }(2i+1)=c_0(i)1$. Observe that after two updates of all cells with odd coordinates and a single update of all cells with even coordinates, we obtain the encoded configuration $G^A(c_0)$ where the updated states are now placed at positions $2i$ and $2i-1$. Notice, $𝔹$ cannot have two neighboring transitions active at the same time, hence by Lemma 11, it has invariant histories. By taking the unpacking map $o$ with $o(c_0)(i)=(c_0^{\prime }(2i),c_0^{\prime }(2i+1))$ and translation $\tau$ with $\tau (c)(i)=c(i-1)$ we observe:

which corresponds to $1.5$-linear time simulation. $◀$

Determining the “computation boundary” between universality and non-universality was originally considered by Shannon [34], who initiated the search for the smallest universal Turing machine [26]. These questions also made their way to cellular automata, with the first $2$-dimensional universal cellular automaton being constructed by von Neumann [33]. Banks [3] has improved the number of states to just $2$ by showing that embedding infinite circuits inside a cellular space ${\mathbb{Z}}^2$ is sufficient for universality. Later, Minsky showed that Conway’s Game of Life cellular automaton is universal [12], and Cook [4] has constructed a universality proof for Rule 110, confirming the existence of a $2$-state first neighbors automaton. On the other hand, Wolfram [37] extensively studied elementary cellular automata and concluded that no one-way $2$-state universal automata exist (similarly, none exist with just one state or empty neighborhood). He also proposed a candidate $3$-state one-way cellular automaton; however, its universality is yet to be proven. The current “universality frontier” for synchronous CAs is given in Figure 1 (left).

Although an explicit definition of asynchronous universality is rarely presented in the literature, all important constructions of universal ACAs essentially assume the slight adjustment of the synchronous definition to the asynchronous scenario [1, 32, 19, 20]. This is consistent with our expectations–by using any simulation technique following Definition 14 on any universal CA, we obtain a universal ACA. Below we present our formalization attempt but, like any other such attempt, it should be taken with a grain of salt.

We call a configuration $c\in S^{{\mathbb{Z}}^d}$ computable if the function $c:{\mathbb{Z}}^d⟶S$ is computable, and denote with $\lceil c\rceil$ the description of some Turing machine computing $c$ by returning an element of $S$ for every $d$-dimensional input vector. Similarly, for any description $r$ we denote with $\tilde{r}$ the underlying configuration. We set $\lceil S^{{\mathbb{Z}}^d}\rceil$ as the space of all computable descriptions of $S^{{\mathbb{Z}}^d}$, and observe that it is closed under finite (a)synchronous evolution with any $G^{\zeta }$.

Lee [20] kicked off the search for universal asynchronous automata by constructing a $5$-state universal von Neumann cellular automaton, which was later improved to $4$ states by Lee [19] and to $3$ states for Moore’s neighborhood by Schneider [32]. By allowing the neighborhood $N$ to be of radius $2$ (non-standard case), a $2$-state universal automaton was constructed by Adachi [1]. On the other hand, by simulating Rule 110 using improved marching soldiers [38, 21], an $8$-state first neighbors universal automaton can be inferred. We improve the frontier by constructing a $3$-state von Neumann and a $6$-state first neighbors universal automata (presented in Section 7). The updated asynchronous universality frontier is given in Figure 1 (right).

Observe that all simulations mentioned in Section 4 require the neighborhood $N$ to be symmetric, and in fact, no general simulation technique which is applicable to one-way neighborhoods is known. In Section 6 we give an explanation for this by proving that one-way ACAs are, in a sense “equivalent” to finite-state machines. This stands in sharp contrast to the synchronous case, where a simple procedure is known to embed any first neighbors automata into one-way automata (see Appendix of the full version). Thus, we can make the following–somewhat unexpected–observation: the choice of asynchronous setting directly affects the computational capabilities of one-way ACAs. We summarize updated results on the computational power of ACAs under various asynchronous settings in Figure 6.

We assume that we are given an ultimately periodic initial configuration $c_0$ with the input $w$ encoded into it. Since $𝔸$ is $1$-dimensional we have

for some $p_L$ and $p_R$ independent of $w$, and $\widehat{w}$, an encoding of $w$. Now we construct an update schedule $\zeta$ and a finite-state machine $B$ based on $p_L$ and $p_R$ and $𝔸$ such that $B$ simulates $𝔸$. Let $c$ be a configuration, $G$ (asynchronous) global transition function, $D\subseteq \mathbb{Z}$ be an update set, then we say that the state $s$ is a pseudo-fixed-point of cell $i$ under $D$ if $s$ reappears infinitely often in the range of $G_D$, i.e., $|\{k\in \mathbb{N}|G_D^k(c)(i)=s\}|=\mathrm{\infty }$.

We claim that for any cell $i$, configuration $c$ and update set $D$ there exists a pseudo-fixed-point $s$. Indeed, since $|S|$ is finite but the orbit of $i$ is infinite, at least one element $s\in S$ has to occur infinitely often. Now, consider the scenario where the update set $D=\{i\}$. We can determine the pseudo-fixed-point of $i$ on $c$ by considering the sequence

It is easy to see that if some state $s^{\prime }$ appears twice in this sequence, it will appear infinitely often; hence it will be a pseudo-fixed-point. Since this simple pseudo-fixed-point only depends on the states $c(i-1)$ and $c(i)$ we will denote it by $\text{pf}(c(i-1),c(i))$. Using this notion, we define the transition function $\delta$ for automaton $B$ and $q,s\in S$ as $\delta (q,s)=\text{pf}(q,s)$.

Let $l+1$ be the first cell that contains an element of $\widehat{w}$ in $c_0$ and let $r-1$ be the last cell containing an element from $\widehat{w}$ (see Figure 7). Now set $x_l$ to be a pseudo-fixed-point of $l$ on configuration $c_0$ and update set $D=\{-\mathrm{\infty },\mathrm{\dots },l\}$ and for $j\in \{l+1,\mathrm{\dots },r-1\}$ let $x_j=\text{pf}(x_{j-1},c_0(j))$. Observe that if we choose the initial state $x_l$ for $B$ and execute it on the first $j-l$ letters of $\widehat{w}$, then $B$ will be in the state $x_j$! We construct the update schedule $\zeta$ by repeating steps 1–3 shown in Figure 7 indefinitely (every cell is updated infinitely often):

1. 1.

   Repeatedly update the set $\{-\mathrm{\infty },\mathrm{\dots },l\}$ until cell $l$ is in state $x_l$

2. 2.

   Repeatedly update $\{l+1\}$ until cell $l+1$ is in state $x_{l+1}$, then repeatedly update $\{l+2\}$ until cell $l+2$ is in state $x_{l+2}$, and so on until you reach $x_r$

3. 3.

   Update the set $\{r,\mathrm{\dots },\mathrm{\infty }\}$ once

We make the following observations about the space-time evolution of $c_0$ under $\zeta$:

• $\mathrm{■}$

  After each iteration of steps 1–3 in $\zeta$ the states at positions $l,\mathrm{\dots },r-1$ do not change and correspond to values $x_l,\mathrm{\dots },x_{r-1}$

• $\mathrm{■}$

  Evolution of $p_L$ region is independent of $\widehat{w}$ and $p_R$ region accesses $\widehat{w}$ only through $x_{r-1}$

Since all states $x_{l+1},\mathrm{\dots },x_{r-1}$ are computed by $B$ on $\widehat{w}$ and the update history $h$ of cells $\{r,\mathrm{\dots },\mathrm{\infty }\}$ only depends on $x_{r-1}\in S$ and $p_R$ (fixed), the right side of any configuration is only aware of bounded amount of information about $\widehat{w}$. Thus, for any possible state of $x_{r-1}$, we can add a single transition $\delta (x_{r-1},\mathrm{\#})$ to $B$, which represents the “outcome” of the joint evolution of $p_R$ and $x_{r-1}$. We conclude that the $\zeta$ evolution of $c_0$ based on the choice of $\widehat{w}$ is at most as complex as the application of $B$ to $\widehat{w}\mathrm{\#}$, hence it cannot be universal. $◀$

It is sufficient to apply our improved mountain-valley simulation from Proposition 17 to Rule 110. Since the corresponding invariant history will contain the synchronous space-time of Rule 110, by extension, the resulting automaton is universal. $◀$

To prove Theorem 25 we use the second approach and design a $3$-state universal ACA using infinitely periodic delay-insensitive Boolean circuits. This kind of universality proof is known as circuit universality and is commonly used to construct some of the smallest universal cellular automata. Due to the classification of Boolean functions by Post [30], we know that any Boolean function $f$ can be implemented as a feed-forward circuit consisting solely of NAND gates (and the fan-out operation). This result can be further strengthened for planar circuits (i.e., circuits without wire crossings).

It turns out that the ability to embed arbitrary circuits into $2$-dimensional cellular automata is already sufficient for universality and was used to prove universality of several CAs, most notably of Life without Death [17].

The proof for Proposition 27 is given in Appendix of the full version, and it naturally generalizes to an asynchronous setting, as long as the ACA allows for reliable asynchronous implementation of Boolean functions. Universality proofs in [20, 19, 1, 32] accomplished this by constructing custom delay-insensitive gates, i.e. gates that do not require simultaneity of inputs and operate under arbitrary delays [22]. For asynchronous inputs, a common tactic is to use dual-rail encoding, i.e., encode each variable I using two “sub-wires” I and $\neg \text{I}$ (one for “true” signals, and the other for “false” signals). We take a similar approach and present a simple set of delay-insensitive gates MERGE, FORK, DUAL, and CROSS, as defined in Figure 8.

Due to Proposition 26 it is sufficient to show that we can construct a NAND gate and fan-out operation using a planar circuit. We employ dual-rail encoding and for fan-out FORK both inputs I and $\neg \text{I}$ individually and then CROSS them using the fact that at most one of them contains the signal. The circuit for the dual rail NAND is given in Figure 9. $◀$

As a direct consequence it follows that it is sufficient to find a $3$-state ACA $𝕏=(\{0,1,2\},N,f,{\mathbb{Z}}^2)$ with von Neumann neighborhood capable of reliably simulating all delay insensitive gates from Figure 8. We start by describing a “helper” ACA ${𝕏}^{\prime }=(\{0,1,2\},N,f^{\prime },{\mathbb{Z}}^2)$ embedding a FAN and capable of implementing wires, FORK and DUAL. We assume $0$ as a “background” cell, i.e., a cell that never changes its state and defines no directional indicators. For the remaining nodes we define a mapping $\psi$ similarly to Proposition 16, but now the directional indicator between adjacent non-zero cells points left (or down) if the states are equal, and right (or up) if they are distinct:

We use the following principle (similarly to Example 10) to describe the transition function $f^{\prime }$ of ${𝕏}^{\prime }$: as soon as all directional indicators point to some cell $i\in {\mathbb{Z}}^2$ it becomes active and can “flip” its state from $1$ to $2$ or from $2$ to $1$ respectively. Observe that this state change also causes all adjacent directional indicators to flip. To visualize the underlying circuit, we interpret any active cell of ${𝕏}^{\prime }$ as containing the “signal”, and in this way the signal is always transmitted reciprocally to directional indicators, which provides us with a simple way of encoding wires into configurations of ${𝕏}^{\prime }$.

A possible wire construction is shown in Figure 10 (first), and it is not unique–by swapping all $2$s with $1$s, we get the same wire carrying the same signal, hence there are multiple equally valid ways of transporting signals (this is crucial for implementing crossings). We can easily construct wires into arbitrary directions, for example:

describe the left-right wire and the right-left wire, respectively. In a similar fashion, we can implement DUAL by combining two signals into one and FORK by splitting a signal into two, as shown in Figure 10 (second and third). However, ACA ${𝕏}^{\prime }$ can not yet be considered universal because the implementation for MERGE and CROSS seems to be impossible. Hence we augment the transition function $f^{\prime }$ by adding four additional transitions to obtain the final ACA $𝕏$ (we use for $0$, for $1$ and for $2$).

$$\text{<foreignobject height="15.9pt" overflow="visible" style="--fo\_width :1.59em;--fo\_height:1.59em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 22)" width="15.9pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x9.png" id="S7.Ex30.m1.g1nest" class="ltx\_graphics ltx\_img\_square" width="31" height="31" alt="[Uncaptioned image]" style="width: 31px; height: unset; max-width: 100\%"></span></span></foreignobject>}\mapsto \text{<foreignobject height="8.7pt" overflow="visible" style="--fo\_width :0.87em;--fo\_height:0.87em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 12)" width="8.7pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x10.png" id="S7.Ex30.m1.g2nest" class="ltx\_graphics ltx\_img\_square" width="17" height="17" alt="[Uncaptioned image]" style="width: 17px; height: unset; max-width: 100\%"></span></span></foreignobject>}\text{<foreignobject height="15.9pt" overflow="visible" style="--fo\_width :1.59em;--fo\_height:1.59em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 22)" width="15.9pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x11.png" id="S7.Ex30.m1.g3nest" class="ltx\_graphics ltx\_img\_square" width="31" height="31" alt="[Uncaptioned image]" style="width: 31px; height: unset; max-width: 100\%"></span></span></foreignobject>}\mapsto \text{<foreignobject height="8.7pt" overflow="visible" style="--fo\_width :0.87em;--fo\_height:0.87em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 12)" width="8.7pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x12.png" id="S7.Ex30.m1.g4nest" class="ltx\_graphics ltx\_img\_square" width="17" height="17" alt="[Uncaptioned image]" style="width: 17px; height: unset; max-width: 100\%"></span></span></foreignobject>}\text{ for }\text{MERGE}\text{<foreignobject height="15.9pt" overflow="visible" style="--fo\_width :1.59em;--fo\_height:1.59em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 22)" width="15.9pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x13.png" id="S7.Ex30.m1.g5nest" class="ltx\_graphics ltx\_img\_square" width="31" height="31" alt="[Uncaptioned image]" style="width: 31px; height: unset; max-width: 100\%"></span></span></foreignobject>}\mapsto \text{<foreignobject height="8.7pt" overflow="visible" style="--fo\_width :0.87em;--fo\_height:0.87em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 12)" width="8.7pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x14.png" id="S7.Ex30.m1.g6nest" class="ltx\_graphics ltx\_img\_square" width="17" height="17" alt="[Uncaptioned image]" style="width: 17px; height: unset; max-width: 100\%"></span></span></foreignobject>}\text{<foreignobject height="15.9pt" overflow="visible" style="--fo\_width :1.59em;--fo\_height:1.59em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 22)" width="15.9pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x15.png" id="S7.Ex30.m1.g7nest" class="ltx\_graphics ltx\_img\_square" width="31" height="31" alt="[Uncaptioned image]" style="width: 31px; height: unset; max-width: 100\%"></span></span></foreignobject>}\mapsto \text{<foreignobject height="8.7pt" overflow="visible" style="--fo\_width :0.87em;--fo\_height:0.87em;--fo\_depth :0em;" transform="matrix(1 0 0 -1 0 12)" width="8.7pt"><span class="ltx\_foreignobject\_container"><span class="ltx\_foreignobject\_content"><img src="x16.png" id="S7.Ex30.m1.g8nest" class="ltx\_graphics ltx\_img\_square" width="17" height="17" alt="[Uncaptioned image]" style="width: 17px; height: unset; max-width: 100\%"></span></span></foreignobject>}\text{ for }\text{CROSS}$$

Notice that the new active transitions do not affect wires, FORK or DUAL from Figure 10. The new MERGE functions like a DUAL, but it is sufficient to flip just one directional indicator to transmit a signal, see Figure 10 (fifth). Similarly, for CROSS, as soon as one signal arrives at the crossing, it gets immediately transmitted by “flipping” the $0$ cell and without creating any interference, as shown in Figure 10 (forth). Multiple signals arriving simultaneously can cause potential problems, but this is forbidden by definitions of MERGE and CROSS.

We note that this implementation of gates “breaks” them as soon as they have processed a signal, but this will not have any effect on feed-forward circuits, since those do not contain loops. It is clear that as long as wires have a spacing of at least two $0$ cells in between, any feed-forward circuit embedded in $𝕏$ operates correctly, hence is universal. We verified our construction using the Golly [35] simulator (implementation provided in Appendix of the full version).