Ответ 1
Гиперграфом является только граф G=(V,E), где V - множество вершин (узлов), а E - подмножество силового набора V. Это структура данных.
Таким образом, общий граф - это просто гиперграф с ранга 2. (каждый набор из E содержит ровно две вершины). Направленный гиперграф использует пары (X,Y) в качестве ребер, где X и Y - множества.
Если вы хотите смоделировать машину turing, вам нужно смоделировать "ленту". Вы хотите, чтобы лента "встроена" в график? Я думаю, вам, возможно, повезло больше о тесте Церкви-Тьюринга (церковь Алонсо, исчисление Лямбды). Исчисление лямбда - это форма системы перезаписи, и, безусловно, существует ветвь, которая использует переписывание графа (и гиперграфы).
Конечно, переходы можно смоделировать как график (я не уверен, что вы имели в виду, но прямой подход на самом деле не помогает) если вы обычно моделировали его, вы, вероятно, создавали бы словарь/хэш-карту с кортежами как ключи (State, Symbol) и значения (State, Rewrite, Left | Right). например,
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)
Как я уже упоминал ранее, просмотрите повторную запись графика или переименование термина.