Может ли гиперграф представлять недетерминированную машину Тьюринга?
Кто-нибудь знает какие-либо статьи, тексты или другие документы, в которых обсуждается использование гиперграфа для реализации или представления недетерминированной машины Тьюринга? Действительно ли они эквивалентны?
Я почти уверен, что гиперграф способен правильно и полностью представить переходы состояний, например, недетерминированной машины Тьюринга. Но я до сих пор не смог найти в печати ничего, что могло бы подтвердить это. Это кажется мне такой очевидной связью, однако тот факт, что я не нахожу предшествующий уровень техники, заставляет меня думать, что я на неправильном пути. (Возможно также, что то, что я нахожу, просто недостаточно доступно для меня, чтобы понять, о чем оно говорит.) ;-)
Почему я спрашиваю: я работаю над пакетом с открытым исходным кодом, который действительно распространяется. хранение данных и распределенные вычисления в одноранговой сети. Я ищу самую примитивную структуру данных, которая могла бы поддерживать необходимую функциональность. Пока что распределенный гиперграф выглядит многообещающе. Я полагаю, что если гиперграф может поддерживать что-то столь же общее, как недетерминированная машина Тьюринга, то он должен быть в состоянии поддерживать полный по Тьюрингу DSL более высокого уровня. (Есть и другие причины, по которым «недетерминированная» часть может быть ценна и для меня, связанная с контролем версий распределенных данных и/или результатов вычислений. Однако здесь я пытаюсь избежать диссертации.)
Частичные ответы:
- Ребята из opencog провели мучительную дискуссию о том, как гиперграфы вписываются в различные вычислительные модели; очевидно, это было связано с разработкой пакета HypergraphDB: http://markmail.org/message/5oiv3qmoexvo4v5j
- В MathOverflow есть вопрос, обсуждающий, на что способны гиперграфы — пока нет упоминания о Тьюринге, но я собираюсь добавить его: https:// mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs
- Если гиперграф может представлять недетерминированную машину Тьюринга, то я думаю, что гиперграф со взвешенными ребрами будет эквивалентен вероятностнаямашина Тьюринга. http://en.wikipedia.org/wiki/Probabilistic_Turing_machine