Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.