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.


The construction is similar to that of Schönhage's Storage Modification Machine (SMM) model.


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.