# Turing-complete computation models on graphs

There are many Turing complete computation models and new ones are devised all the time.

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

• 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 Mar 28 '14 at 15:16
• 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 Mar 28 '14 at 15:25
• I meant diagrams such as the one in this CS Stack Exchange question. 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 Mar 28 '14 at 15:29
• 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 Mar 28 '14 at 15:30
• 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 Mar 28 '14 at 16:25

## 4 Answers

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

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. 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. Habilitation thesis, Universität Stuttgart, pp. 65–180.

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

• I always knew the graph isomorphism problem had a practical application! – num1 Jan 13 '17 at 17:57

As in my comment, the configuration graph (Chapter 4.1.1. of Arora-Barak) 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.

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]

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:

(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.