<p>Following an earlier <a href="https://cstheory.stackexchange.com/questions/21785/turing-complete-computation-models-on-graphs/21794#21794">question</a>, I would like to suggest the following generic computation model. Let $\Gamma$ be a group, we say that a $\Gamma$-labeled digraph is a digraph $G$ whose arcs are labeled by $\Gamma$ and such that for each directed cycle $C$, the product of the labels equals $1_{\Gamma}$. Let $F,G$ be two $\Gamma$-labeled digraphs with two distinguished vertices $s_F,t_F$, resp. $s_G,t_G$. We say that an equivalence relation $R$ on $V(F) \cup V(G)$ is a <em>bisimulation</em> if:</p>

<p>(1) $s_F ~R~ s_G$ and $t_F ~R~ t_G$,</p>

<p>(2) whenever $u ~R~ v$ holds, if $F$ contains a path $u \rightarrow^*_a u'$ and $G$ contains a path $v \rightarrow^*_a v'$ then $u' ~R~ v'$ also holds (and conversely).</p>

<p>Let $O(G)$ denote the set of bisimulations of $G$. Fix two digraphs $F,G$ with $V(F) = \{v_1,\ldots,v_m\}$, $v_1 = s_F, v_m = t_F$, and $V(G) = \{w_1,\ldots,w_n\}$, $w_1 = s_G, w_n = t_G$. We may then define a relation $R$ on $O(F) \times O(G)$ as follows. Given $J \in O(F), K \in O(G)$, we say that $(J,K) ~R~ (J',K')$ holds if there is a $\Gamma$-labeled digraph $L$ and an arrangement of curves $\gamma_1,\ldots,\gamma_m, \delta_1,\ldots,\delta_n$ forming a grid-like shape such that:</p>

<p>(*) we can arrange the vertices of $L$ on the union of these curves, and if we let $H_i$ the part mapped to $\gamma_i$ and $V_j$ the part mapped to $\delta_j$, then we have: (a) $H_1 = J, H_n = J'$, $V_1 = K, V_m = K'$, (b) for every $1 \leq i &lt; m$, there is a bisimulation $R_i$ between $H_i$ and $H_{i+1}$ such that for each class $C$ of $R_i$ and $j \in \{i,i+1\}$, the elements of $V(H_j) \cap C$ are "consecutive" on $\gamma_j$, (c) the same condition holds for the pairs $V_j,V_{j+1}$.</p>

<p>Despite the apparent complexity of the formulation, the motivation is simple: first, we want to break the word/machine dichotomy of TMs by restoring some symmetry between the "computer" and the "data"; second, we try to abstract the geometric "grid-like" structure of a TM and the locality properties of the computation, which are here expressed by the nullity constraint on cycles.</p>

<p>As I come back to ground, I'm not sure if my model has any practicality though, but it may interest some researchers in machine models. Even though the target audience is probably narrow, I'd like to ask: (i) what is the computation power of the model depending on the group $\Gamma$, (ii) can we exploit the geometric definition to get some interesting properties (i.e. possibility of composition by grid juxtaposition)?</p>

CC BY-SA 3.0
2014-04-03T16:11:55.100Z
Could you give a simple example of this? I'm not sure I see how this formalism computes. An: what do you mean by "arrangement of curves"?
Martin Berger
CC BY-SA 3.0
2014-04-03T16:21:47.443Z
Could you clarify what you mean by an "equivalence relation", given that it seems to relate elements of two distinct sets? Neither reflexivity, symmetry, nor transitivity seem to apply here...
Niel de Beaudrap
CC BY-SA 3.0
2014-04-03T16:26:49.257Z
@NieldeBeaudrap: I meant a relation defined on the union, not the product, this is now fixed.
NisaiVloot
CC BY-SA 3.0
2014-04-03T17:23:11.800Z
a std group-theoretic computation mechanism seems to be the [word problem for groups](http://cs.stackexchange.com/a/14413/699) (cs.se) which has been proven Turing-complete, but havent found a nice survey/overview of it yet for the TCS audience... RJLipton has a few blogs on it... also [wikipedia](https://en.wikipedia.org/wiki/Word_problem_for_groups) has some intro... would like to start study group in eg [chat]
vzn
CC BY-SA 3.0
2014-04-04T00:11:05.940Z
Thanks for the hints. Personally I find these 'word problems' a little far-fetched as the undecidability results involve quite exotic groups. I'm more interested in concrete groups which admit an efficient membership/canonization oracle, which is the case most of the time. So in a nutshell I don't consider these word problems as a 'natural' Turing-complete model.
NisaiVloot
<machine-models>
Machine models based on group-labeled digraphs?
NisaiVloot
# Machine models based on group-labeled digraphs?

(Asked by: username_0 on 2014-04-03)

Following an earlier [question](https://cstheory.stackexchange.com/questions/21785/turing-complete-computation-models-on-graphs/21794#21794), I would like to suggest the following generic computation model. Let $\Gamma$ be a group, we say that a $\Gamma$-labeled digraph is a digraph $G$ whose arcs are labeled by $\Gamma$ and such that for each directed cycle $C$, the product of the labels equals $1\_{\Gamma}$. Let $F,G$ be two $\Gamma$-labeled digraphs with two distinguished vertices $s\_F,t\_F$, resp. $s\_G,t\_G$. We say that an equivalence relation $R$ on $V(F) \cup V(G)$ is a *bisimulation* if:

(1) $s\_F ~R~ s\_G$ and $t\_F ~R~ t\_G$,

(2) whenever $u ~R~ v$ holds, if $F$ contains a path $u \rightarrow^\*\_a u'$ and $G$ contains a path $v \rightarrow^\*\_a v'$ then $u' ~R~ v'$ also holds (and conversely).

Let $O(G)$ denote the set of bisimulations of $G$. Fix two digraphs $F,G$ with $V(F) = \{v\_1,\ldots,v\_m\}$, $v\_1 = s\_F, v\_m = t\_F$, and $V(G) = \{w\_1,\ldots,w\_n\}$, $w\_1 = s\_G, w\_n = t\_G$. We may then define a relation $R$ on $O(F) \times O(G)$ as follows. Given $J \in O(F), K \in O(G)$, we say that $(J,K) ~R~ (J',K')$ holds if there is a $\Gamma$-labeled digraph $L$ and an arrangement of curves $\gamma\_1,\ldots,\gamma\_m, \delta\_1,\ldots,\delta\_n$ forming a grid-like shape such that:

(\*) we can arrange the vertices of $L$ on the union of these curves, and if we let $H\_i$ the part mapped to $\gamma\_i$ and $V\_j$ the part mapped to $\delta\_j$, then we have: (a) $H\_1 = J, H\_n = J'$, $V\_1 = K, V\_m = K'$, (b) for every $1 \leq i < m$, there is a bisimulation $R\_i$ between $H\_i$ and $H\_{i+1}$ such that for each class $C$ of $R\_i$ and $j \in \{i,i+1\}$, the elements of $V(H\_j) \cap C$ are "consecutive" on $\gamma\_j$, (c) the same condition holds for the pairs $V\_j,V\_{j+1}$.

Despite the apparent complexity of the formulation, the motivation is simple: first, we want to break the word/machine dichotomy of TMs by restoring some symmetry between the "computer" and the "data"; second, we try to abstract the geometric "grid-like" structure of a TM and the locality properties of the computation, which are here expressed by the nullity constraint on cycles.

As I come back to ground, I'm not sure if my model has any practicality though, but it may interest some researchers in machine models. Even though the target audience is probably narrow, I'd like to ask: (i) what is the computation power of the model depending on the group $\Gamma$, (ii) can we exploit the geometric definition to get some interesting properties (i.e. possibility of composition by grid juxtaposition)?

**Tags:** machine-models
> **Comments:**
> **username_1**: Could you give a simple example of this? I'm not sure I see how this formalism computes. An: what do you mean by "arrangement of curves"?  
> **username_2**: Could you clarify what you mean by an "equivalence relation", given that it seems to relate elements of two distinct sets? Neither reflexivity, symmetry, nor transitivity seem to apply here...  
> **username_0**: @NieldeBeaudrap: I meant a relation defined on the union, not the product, this is now fixed.  
> **username_3**: a std group-theoretic computation mechanism seems to be the [word problem for groups](http://cs.stackexchange.com/a/14413/699) (cs.se) which has been proven Turing-complete, but havent found a nice survey/overview of it yet for the TCS audience... RJLipton has a few blogs on it... also [wikipedia](https://en.wikipedia.org/wiki/Word_problem_for_groups) has some intro... would like to start study group in eg [chat]  
> **username_0**: Thanks for the hints. Personally I find these 'word problems' a little far-fetched as the undecidability results involve quite exotic groups. I'm more interested in concrete groups which admit an efficient membership/canonization oracle, which is the case most of the time. So in a nutshell I don't consider these word problems as a 'natural' Turing-complete model.  

---

## 0 answers

