Может ли гиперграф представлять недетерминированную машину Тьюринга? - PullRequest
Новая
       55

Может ли гиперграф представлять недетерминированную машину Тьюринга?

11 голосов
/ 31 марта 2012

Кто-нибудь знает какие-либо документы, тексты или другие документы, в которых обсуждается использование гиперграфа для реализации или представления недетерминированной машины Тьюринга? Они на самом деле эквивалентны?

Я почти уверен, что гиперграф способен правильно и полностью представлять переходы состояний недетерминированной машины Тьюринга, например. Но до сих пор я не смог найти в печати ничего, что могло бы это подтвердить. Это кажется таким очевидным отношением, однако тот факт, что я не нахожу предшествующий уровень техники, заставляет меня думать, что я на неправильном пути. (Может также оказаться, что то, что я нахожу, просто недостаточно доступно для меня, чтобы понять, о чем оно говорит.); -)

Почему я спрашиваю: я работаю над пакетом с открытым исходным кодом, который выполняет распределенное хранение данных и распределенные вычисления в одноранговой сети. Я ищу самую примитивную структуру данных, которая могла бы поддерживать необходимую функциональность. Пока что распределенный гиперграф выглядит многообещающе. Я рассуждаю так: если гиперграф может поддерживать что-то такое общее, как недетерминированная машина Тьюринга, то он должен поддерживать высокоуровневую 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

1 Ответ

1 голос
/ 15 июля 2017

Гиперграф - это просто график G=(V,E), где V - это набор вершин (узлов), а E - это подмножество набора мощности V.Это структура данных.

Таким образом, общий граф - это просто гиперграф с рангом 2. (т. Е. Каждый набор в E содержит ровно две вершины).Направленный гиперграф использует пары (X,Y) в качестве ребер, где X и Y - множества.

Если вы хотите смоделировать машину Тьюринга, вам нужно смоделировать «ленту».Вы хотите, чтобы лента «встроена» в график?Думаю, вам больше повезет, если подумать о тезисе Черча-Тьюринга (церковь Алонсо, лямбда-исчисление).Лямбда-исчисление является формой переписывающей системы, и, безусловно, есть ветвь, которая использует переписывание графа (и гиперграфы).

Конечно, переходы можно смоделировать как граф (я неконечно, что вы имели в виду, но прямой подход не очень помогает), если бы вы моделировали его нормально, вы, вероятно, создали бы словарь / хэш-карту с кортежами в качестве ключей (State, Symbol) и значениями (State, Rewrite,слева | справа).например, 

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

, поэтому, если вы хотите получить график, вам сначала понадобится V = состояния U символов U перемещений.Ясно, что они должны быть непересекающимися множествами.поскольку {1, a} -> {1, b, R} по определению равен {a, 1} -> {b, R, 1} и т. д. 

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)

Как я упоминал ранее,ищите переписывание графа или переписывание термина.

...