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](http://arxiv.org/abs/1204.3372).



Universality of blind graph rewriting
The construction is similar to that of [Schönhage's Storage Modification Machine (SMM) model](http://en.wikipedia.org/wiki/Pointer_machine#Sch.C3.B6nhage.27s_Storage_Modification_Machine_.28SMM.29_model).


