¿Puede un hipergraph representar una máquina de Turing no determinista?

Question

¿Alguien sabe de documentos, textos u otros documentos que discuten el uso de un hipergraph para implementar o representar una máquina de Turing no determinista? ¿Son de hecho equivalentes?

Estoy bastante seguro de que un hipergraph puede representar de manera correcta y completa las transiciones de estado de una máquina Turing no determinista, por ejemplo. Pero hasta ahora no he podido encontrar nada impreso que pueda verificar esto. Esto me parece una relación tan obvia, sin embargo, el hecho de que no encuentre el estado de la técnica me hace pensar que estoy en el camino equivocado. (También podría darse el caso de que lo que estoy buscando no sea lo suficientemente accesible para que entienda lo que dice.) ;-)

Por qué lo pregunto: estoy trabajando en un paquete de código abierto que no funciona almacenamiento de datos distribuidos y computación distribuida en una red punto a punto. Estoy buscando la estructura de datos más primitiva que pueda soportar la funcionalidad necesaria. Hasta ahora, un hipergrama distribuido parece prometedor. Mi razonamiento es que, si un hipergraph puede soportar algo tan general como una máquina de Turing no determinista, entonces debería ser capaz de soportar un DSL completo de Turing de nivel superior. (Hay otras razones por las que la pieza "no determinista" también puede ser valiosa para mí, teniendo que ver con el control de versión de los datos distribuidos y/o resultados de cálculo.)

Respuestas parciales:

• La gente de opencog tuvo una discusión apasionante sobre cómo los hipergramas encajan en diferentes modelos de computación; Al parecer, esto se relaciona con el desarrollo del paquete HypergraphDB: http://markmail.org/message/5oiv3qmoexvo4v5j
• Más en MathOverflow, hay una pregunta discutir lo hypergraphs puede hacer - ninguna mención de Turing todavía, pero estoy a punto de agregarlo: https://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs
• Si un hypergraph puede representar una máquina de Turing no determinista, entonces yo creo que un hypergraph con bordes ponderados sería equivalente a una máquina de Turing probabilística . http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

Answer 1

A hypergraph es sólo un gráfico G=(V,E) donde V es el conjunto de vértices (nodos) y E es un subconjunto de la powerset de V. Es una estructura de datos.

Así un gráfico común es sólo un hypergraph con la fila 2. (es decir, cada conjunto en E contiene exactamente dos vértices). Un hipergrafo dirigido utiliza los pares (X,Y) ya que los bordes donde X y Y son conjuntos.

Si se desea modelar una máquina de Turing, entonces usted necesita para modelar la 'cinta'. ¿Desea que la cinta esté "incrustada" en el gráfico? Creo que es posible que tengas más suerte pensando en la tesis de Church-Turing (Alonso Church, Lambda calculus). El cálculo Lambda es una forma de sistema de reescritura y, sin duda, hay una rama que utiliza reescritura de gráficos (e hipergrpahs).

Por supuesto, las transiciones se pueden modelar como un gráfico (no estoy seguro de lo que tenía en mente, pero el enfoque directo en realidad no ayuda) si lo estuviera modelando normalmente, probablemente crearía un diccionario/hashmap con tuplas como claves (estado, símbolo) y los valores son (estado, reescritura, izquierda | derecha).por ejemplo,

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

así que si quisiera un gráfico primero necesitaría V = estados U símbolos U mueve. Claramente necesitan ser conjuntos disjuntos. como {1, a} -> {1, b, R} es por definición igual a {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) 

Como he mencionado anteriormente, mira hasta la reescritura de gráficos o la reescritura de términos.