<p>Only an extended comment: I only heard about it (and I know almost nothing about it :), but there is a computational model based on <a href="http://en.wikipedia.org/wiki/Graph_rewriting" rel="nofollow">Graph Rewriting</a></p>

<p>From Wikipedia: "... The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph. ..."</p>

<p>You can take a look at: D. L. McBurney and M. R. Sleep. 1991. <a href="http://dl.acm.org/citation.cfm?id=111305" rel="nofollow">Graph Rewriting as a computational model</a>. In Proceedings of the UK/Japan workshop on Concurrency : theory, language, and architecture: theory, language, and architecture, A. Yonezawa and T. Lto (Eds.). Springer-Verlag New York, Inc., New York, NY, USA, 235-256. </p>

<p>or this thesis for an introduction: König, Barbara (December 2004). <a href="http://www.fmi.uni-stuttgart.de/szs/publications/koenigba/habilschrift.pdf" rel="nofollow">Analysis and Verification of Systems with Dynamically Evolving Structure</a>. Habilitation thesis, Universität Stuttgart, pp. 65–180.</p>

<p>But I don't know if it is still an active field of research.</p>

CC BY-SA 3.0
2017-01-13T17:57:18.667Z
I always knew the graph isomorphism problem had a practical application!
num1
CC BY-SA 3.0
2014-03-28T18:44:55.157Z
2014-03-28T21:09:16.277Z
2014-03-28T21:09:16.277Z
Marzio De Biasi
<p>As in my comment, the configuration graph (Chapter 4.1.1. of <a href="http://www.cs.princeton.edu/theory/index.php/Compbook/Draft" rel="nofollow">Arora-Barak</a>) is a simple way to view a Nondeterministic Turing Machine (NTM) as a graph. The vertices of the graph are labeled by configurations: the internal state of the NTM, the contents of the tape, and head positions. There is a  directed edge from vertex $c_1$ to vertex $c_2$ if the NTM can move from $c_1$ to $c_2$ in one step. </p>

<p>This is especially useful for arguing about space-bounded computation. If the space used by the NTM is bounded by $s(n)$, then on input size $n$ you only need to consider a configuration graph with $O(2^{s(n)})$ vertices. Then a lot of complexity results follow from algorithms for directed $s$-$t$ connectivity: Savitch's theorem (NPSPACE = PSPACE) follows from an algorithm that uses $O(\log^2 |V|)$ space, PSPACE in EXP (or, scaling down, L in P) follows from DFS,  etc. Similarly, you can show that directed connectivity is complete for NL under L reductions, so NL is equal to L if and only if there is a logspace algorithm for directed $s$-$t$ connectivity.</p>

CC BY-SA 3.0
2014-03-28T17:09:41.090Z
2014-03-28T20:27:50.370Z
2014-03-28T20:27:50.370Z
Sasho Nikolov
<p>You can perform universal computation using <em>zero forcing</em>: a simple, repeated transformation of (improper) 2-colourings of vertices. Starting from an initial configuration in which most vertices are coloured white, except for some black "input" vertices, you repeatedly change the colour of any vertex with exactly one white neighbour to black. Logic gates are represented by specific gadgets which are subgraphs.</p>

<blockquote>
  <p>D.&nbsp;Burgarth, V.&nbsp;Giovannetti, L.&nbsp;Hogben, S.&nbsp;Severini, M.&nbsp;Young.<br>
  <em>Logic circuits from zero forcing</em>.<br>
  [<a href="http://arxiv.org/abs/1106.4403" rel="nofollow">arXiv:1106.4403</a>]</p>
</blockquote>

CC BY-SA 3.0
2014-04-03T16:41:25.183Z
2014-04-03T20:52:15.867Z
2014-04-03T20:52:15.867Z
Niel de Beaudrap
<p>Following vzn's comment, you can define a straightforward extension of TMs using graph products. Define a "graph machine" as a tuple $M = (S,T)$ where $S$ is a sets of states, and $T$ is a binary relation over $S \times S$. Fix a graph family $\cal{G}$, and consider the following problem: given a graph $G \in \cal{G}$ and two $S$-labelings $L_1,L_2$ of $G$, does there exist a graph $H \in \cal{G}$ with two distinguished vertices $s,t$ and a $S$-labeling $M$ of $G \times H$ such that:</p>

<p>(i) the restriction of $M$ to $G \times \{s\}$ and $G \times \{t\}$ coincides with $L_1$ and $L_2$ respectively;</p>

<p>(ii) for each "square" of $G \times H$ of the form</p>

<blockquote>
<pre><code>(u_1,v_1) - (u_1,v_2)
    |           |
(u_2,v_1) - (u_2,v_2)
</code></pre>
</blockquote>

<p>with $s_i = M(u_1,v_i)$ and $s'_i = M(u_2,v_i)$, it holds that $(s_1,s_2) T (s'_1,s'_2)$.</p>

<p>It shouldn't be difficult to show that this problem is Turing-complete when $\cal{G}$ is the class of paths, intuitively you can encode the computation by a grid with "local" rules applied to each square.</p>

CC BY-SA 3.0
2014-03-28T18:44:54.817Z
2014-03-28T18:44:54.817Z
Super0
<p>There are <em>many</em> <a href="http://en.wikipedia.org/wiki/Turing_complete" rel="nofollow">Turing complete</a> computation models and new ones are devised all the time.</p>

<blockquote>
  <p>I am looking for Turing-complete computation models based on <em>graphs</em>?</p>
</blockquote>

CC BY-SA 3.0
2014-03-28T15:16:11.330Z
Can you be more precise about "based on graphs"? Turing machines are often presented as labelled graphs, for example. (By the way, it shouldn't be necessary to define the term "Turing-complete" to research-level theoretical computer scientists!)
David Richerby
CC BY-SA 3.0
2014-03-28T15:25:28.867Z
there is a fairly obvious interpretation of NDTMs computational tableaus as graphs/trees, is that what youre referring to? (looking for others in the literature.) (btw, there is no "definition" of Turing completeness written out, its just a link to wikipedia as a convention/courtesy)
vzn
CC BY-SA 3.0
2014-03-28T15:29:16.573Z
I meant diagrams such as the one in [this CS Stack Exchange question](http://cs.stackexchange.com/questions/23113/do-all-turing-machine-have-to-reach-the-blank-state-to-end-up-in-an-accepting-st). I'm pretty sure that's *not* what you mean but I do think it would be helpful to say a bit more about what you do mean.
David Richerby
CC BY-SA 3.0
2014-03-28T15:30:57.593Z
the TM state table (alone) is trivially a labelled graph. looking more for constructions that model the _computational tableau_ as a (infinite?) graph or other notable variants considered by researchers.
vzn
CC BY-SA 3.0
2014-03-28T16:25:30.653Z
As in the configuration graph (Chapter 4.1.1. of Arora-Barak), which is used to prove that e.g. directed connectivity is complete for NL, and that PSPACE is a subset of EXP?
Sasho Nikolov
CC BY-SA 3.0
2014-03-28T16:29:34.640Z
@Sasho havent seen that might be an answer
vzn
CC BY-SA 3.0
2014-08-27T15:07:32.570Z
ran across this, Kolmorogov defined a graph based model. see [Algorithms: A Quest for Absolute Definitions](http://research.microsoft.com/en-us/um/people/gurevich/opera/164.pdf) by Gurevich p9
vzn
<reference-request><graph-theory><graph-algorithms><computability>
Turing-complete computation models on graphs
vzn
# Turing-complete computation models on graphs

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

There are *many* [Turing complete](http://en.wikipedia.org/wiki/Turing_complete) computation models and new ones are devised all the time.

> I am looking for Turing-complete computation models based on *graphs*?

**Tags:** reference-request, graph-theory, graph-algorithms, computability

> **Comments:**
> **username_1**: Can you be more precise about "based on graphs"? Turing machines are often presented as labelled graphs, for example. (By the way, it shouldn't be necessary to define the term "Turing-complete" to research-level theoretical computer scientists!)  
> **username_0**: there is a fairly obvious interpretation of NDTMs computational tableaus as graphs/trees, is that what youre referring to? (looking for others in the literature.) (btw, there is no "definition" of Turing completeness written out, its just a link to wikipedia as a convention/courtesy)  
> **username_1**: I meant diagrams such as the one in [this CS Stack Exchange question](http://cs.stackexchange.com/questions/23113/do-all-turing-machine-have-to-reach-the-blank-state-to-end-up-in-an-accepting-st). I'm pretty sure that's *not* what you mean but I do think it would be helpful to say a bit more about what you do mean.  
> **username_0**: the TM state table (alone) is trivially a labelled graph. looking more for constructions that model the _computational tableau_ as a (infinite?) graph or other notable variants considered by researchers.  
> **username_2**: As in the configuration graph (Chapter 4.1.1. of Arora-Barak), which is used to prove that e.g. directed connectivity is complete for NL, and that PSPACE is a subset of EXP?  
> **username_0**: @Sasho havent seen that might be an answer  
> **username_0**: ran across this, Kolmorogov defined a graph based model. see [Algorithms: A Quest for Absolute Definitions](http://research.microsoft.com/en-us/um/people/gurevich/opera/164.pdf) by Gurevich p9  

---

## 4 answers

### Answer by username_3 on 2014-03-28. Score: 6 | Accepted answer

Only an extended comment: I only heard about it (and I know almost nothing about it :), but there is a computational model based on [Graph Rewriting](http://en.wikipedia.org/wiki/Graph_rewriting)

From Wikipedia: "... The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph. ..."

You can take a look at: D. L. McBurney and M. R. Sleep. 1991. [Graph Rewriting as a computational model](http://dl.acm.org/citation.cfm?id=111305). In Proceedings of the UK/Japan workshop on Concurrency : theory, language, and architecture: theory, language, and architecture, A. Yonezawa and T. Lto (Eds.). Springer-Verlag New York, Inc., New York, NY, USA, 235-256.

or this thesis for an introduction: König, Barbara (December 2004). [Analysis and Verification of Systems with Dynamically Evolving Structure](http://www.fmi.uni-stuttgart.de/szs/publications/koenigba/habilschrift.pdf). Habilitation thesis, Universität Stuttgart, pp. 65–180.

But I don't know if it is still an active field of research.

> **Comments:**
> **username_4**: I always knew the graph isomorphism problem had a practical application!  

---

### Answer by username_2 on 2014-03-28. Score: 6

As in my comment, the configuration graph (Chapter 4.1.1. of [Arora-Barak](http://www.cs.princeton.edu/theory/index.php/Compbook/Draft)) is a simple way to view a Nondeterministic Turing Machine (NTM) as a graph. The vertices of the graph are labeled by configurations: the internal state of the NTM, the contents of the tape, and head positions. There is a directed edge from vertex $c\_1$ to vertex $c\_2$ if the NTM can move from $c\_1$ to $c\_2$ in one step.

This is especially useful for arguing about space-bounded computation. If the space used by the NTM is bounded by $s(n)$, then on input size $n$ you only need to consider a configuration graph with $O(2^{s(n)})$ vertices. Then a lot of complexity results follow from algorithms for directed $s$-$t$ connectivity: Savitch's theorem (NPSPACE = PSPACE) follows from an algorithm that uses $O(\log^2 |V|)$ space, PSPACE in EXP (or, scaling down, L in P) follows from DFS, etc. Similarly, you can show that directed connectivity is complete for NL under L reductions, so NL is equal to L if and only if there is a logspace algorithm for directed $s$-$t$ connectivity.


---

### Answer by username_5 on 2014-04-03. Score: 4

You can perform universal computation using *zero forcing*: a simple, repeated transformation of (improper) 2-colourings of vertices. Starting from an initial configuration in which most vertices are coloured white, except for some black "input" vertices, you repeatedly change the colour of any vertex with exactly one white neighbour to black. Logic gates are represented by specific gadgets which are subgraphs.

> D. Burgarth, V. Giovannetti, L. Hogben, S. Severini, M. Young.  
> *Logic circuits from zero forcing*.  
> [[arXiv:1106.4403](http://arxiv.org/abs/1106.4403)]


---

### Answer by username_6 on 2014-03-28. Score: 1

Following username_0's comment, you can define a straightforward extension of TMs using graph products. Define a "graph machine" as a tuple $M = (S,T)$ where $S$ is a sets of states, and $T$ is a binary relation over $S \times S$. Fix a graph family $\cal{G}$, and consider the following problem: given a graph $G \in \cal{G}$ and two $S$-labelings $L_1,L_2$ of $G$, does there exist a graph $H \in \cal{G}$ with two distinguished vertices $s,t$ and a $S$-labeling $M$ of $G \times H$ such that:
(i) the restriction of $M$ to $G \times \{s\}$ and $G \times \{t\}$ coincides with $L_1$ and $L_2$ respectively;
(ii) for each "square" of $G \times H$ of the form

(u_1,v_1) - (u_1,v_2)
    |           |
(u_2,v_1) - (u_2,v_2)


with $s_i = M(u_1,v_i)$ and $s'_i = M(u_2,v_i)$, it holds that $(s_1,s_2) T (s'_1,s'_2)$.
It shouldn't be difficult to show that this problem is Turing-complete when $\cal{G}$ is the class of paths, intuitively you can encode the computation by a grid with "local" rules applied to each square.


---

