Can a hypergraph represent a nondeterministic Turing machine?

Question

Does anyone know of any papers, texts, or other documents that discuss using a hypergraph to implement or represent a nondeterministic Turing machine? Are they in fact equivalent?

I'm pretty sure that a hypergraph is able to properly and completely represent the state transitions of a nondeterministic Turing machine, for instance. But I've so far been unable to find anything in print that can verify this. This seems to me like such an obvious relationship, however the fact that I'm not finding prior art makes me think I'm on the wrong track. (It could also be the case that what I'm finding is just not accessible enough for me to understand what it's saying.) ;-)

Why I ask: I'm working on an open-source package that does distributed data storage and distributed computation in a peer-to-peer network. I'm looking for the most primitive data structure that might support the functionality needed. So far, a distributed hypergraph looks promising. My reasoning is that, if a hypergraph can support something as general as a nondeterministic Turing machine, then it should be able to support a higher-level Turing-complete DSL. (There are other reasons the "nondeterministic" piece might be valuable to me as well, having to do with version control of the distributed data and/or computation results. Trying to avoid a dissertation here though.)

Partial answers:

• The opencog folks had a tantalyzing discussion of how hypergraphs fit into different computing models; this apparently was related to the development of the HypergraphDB package: http://markmail.org/message/5oiv3qmoexvo4v5j
• Over on MathOverflow, there's a question discussing what hypergraphs can do -- no mention of turing yet, but I'm about to add it: https://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs
• If a hypergraph can represent a nondeterministic Turing machine, then I'd think a hypergraph with weighted edges would be equivalent to a probabalistic Turing machine. http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

Answer 1

A hypergraph is just a graph G=(V,E) where V is the set of vertices (nodes) and E is a subset of the powerset of V. It is a data structure.

So a common graph is just a hypergraph with rank 2. (i.e each set in E contains exactly two vertices). A directed hypergraph uses pairs (X,Y) as the edges where X and Y are sets.

If you want to model a turing machine then you need to model the 'tape'. Do you want the tape 'embedded' in the graph? I think you might have more luck thinking about the Church-Turing thesis (Alonso Church, Lambda calculus). The Lambda calculus is a form of re-writing system and there is most certainly a branch that uses Graph re-writing (and hypergrpahs).

Of course the transitions can be modelled as a graph (I'm not sure what you had in mind, but the straight forward approach doesn't really help) if you were modelling it normally you would probably create a dictionary/hashmap with tuples as keys (State, Symbol) and the values being (State, Rewrite, Left|Right). eg

states = {1,2,3}
symbols = {a,b,c}
moves = L, R
delta = { (1,a) -> (1,b,R)
          (1,b) -> (2,c,L)
          ...
}

so if you wanted a graph you would first need V = states U symbols U moves. Clearly they need to be disjoint sets. as {1,a} -> {1,b,R} is by definition equal to {a,1} -> {b,R,1} etc.

states = {1,2,3}
symbols = {a,b,c}
moves = L, R
V = {1,2,3,a,b,c,L,R}
E = { ({1,a},{1,b,R})
      ({b,1},{L,2,c})
      ...
}
turing-hypergraph = (V,E)

As I mentioned earlier, look up graph re-writing or term re-writing.