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

Yale

What exactly you want to represent with a hypergraph? It's easy to describe state transition relation with nested tables or with directed labeled graph. Just take pairs (State,Symbol) as nodes and label arcs with Move Left or Move Right. – Masjid

@max, yep, that's pretty much what I had in mind -- either your version of some other variation of the normal Turing 5-tuple rule. Applied to nondeterministic Turing machines, the arcs (edges) would of course have multiple heads, pointing at multiple possible next nodes. – Yale

to represent full TM state (i.e. to somehow execute your hypergraph representation) you also need to store states of visited tape cells. – Masjid

@max, I think you may be on the right track; the problem I'm having may the difference between the meaning of "represents" and "implements". The hypergraph is equivalent to the tape of a univeral nondeterministic turing machine, because it contains the rules plus the program of a subsidiary nondeterministic turing machine. But then you still need a machine to execute that -- storing state as it does so. If true, then the hypergraph can represent, but not implement, the machine. – Yale

Representation seems to be straightforward, because if you have a Turing machine defined by a set of tuples, then it can be considered a hypergraph: the tuple components are the nodes, the tuples themselves are the edges. – Feinleib

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.

Satan