# Universality of blind graph rewriting

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed graph with the set of nodes $M$, which has exactly two arrows from each node, the arrows being labeled $0$ and $1$.

Then, the simplest operations on those graphs are

$e[b_0b_1 \dots b_n := a_1 \dots a_m]: S(M) \rightarrow S(M)$,

where $e \in M$, $\forall i: a_i, b_i \in \{0, 1\}$, and for every mapping

$e[b_0b_1 \dots b_n := a_1 \dots a_m](f_0, f_1) = (g_0, g_1)$

node $b = f_{b_1}(\dots f_{b_n}(e) \dots)$ must be the only point where ${(g_0, g_1)}$ differs from $(f_0, f_1)$, and $a = f_{a_1}(\dots f_{a_m}(e) \dots)$ must be equal to ${g_{b_0}(b)}$, that is

• $a = g_{b_0}(b)$;
• $i \not= b_0 \Rightarrow \forall x \in M: g_i(x) = f_i(x)$;
• $\forall x \in M: x \not= b \Rightarrow g_{b_0}(x) = f_{b_0}(x)$.

Assuming $M$ to be unbounded, is there a composition

$T = e[b_0b_1\dots b_n := a_1\dots a_m] \circ \dots \circ e[y_0y_1\dots y_q := x_1\dots x_p]$

which as the only graph rewriting rule for the set of graphs $S(M)$ results in a universal graph rewriting system (a graph rewriting system able to simulate any other graph rewriting system)?

In somewhat more details, the above constructions are described in arXiv:1204.3372.

-