0
$\begingroup$

Following an earlier question, 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)?

$\endgroup$
  • 1
    $\begingroup$ 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"? $\endgroup$ – Martin Berger Apr 3 '14 at 16:11
  • $\begingroup$ 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... $\endgroup$ – Niel de Beaudrap Apr 3 '14 at 16:21
  • $\begingroup$ @NieldeBeaudrap: I meant a relation defined on the union, not the product, this is now fixed. $\endgroup$ – NisaiVloot Apr 3 '14 at 16:26
  • $\begingroup$ a std group-theoretic computation mechanism seems to be the word problem for groups (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 has some intro... would like to start study group in eg Theoretical Computer Science Chat $\endgroup$ – vzn Apr 3 '14 at 17:23
  • $\begingroup$ 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. $\endgroup$ – NisaiVloot Apr 4 '14 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.