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)?
