¿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?¿Puede un hipergraph representar una máquina de Turing no determinista?
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
¿Qué quiere representar exactamente con un hipergrafo? Es fácil describir la relación de transición del estado con tablas anidadas o con un gráfico etiquetado dirigido. Simplemente tome los pares '(State, Symbol)' como nodos y etiquete los arcos con 'Move Left' o' Move Right'. –
@max, sí, eso es más o menos lo que tenía en mente, ya sea tu versión de alguna otra variación de la regla normal de 5 tuplas de Turing. Aplicados a máquinas de Turing no deterministas, los arcos (bordes) tendrían múltiples cabezas, apuntando a múltiples posibles nodos siguientes. – stevegt
para representar el estado de ** full ** TM (es decir, para ejecutar de alguna manera la representación de su hipergraph) también necesita almacenar los estados de las celdas de cinta visitadas. –