超图能表示不确定的图灵机吗？

Question

是否有人知道有任何文件、文本或其他文档讨论使用超图来实现或表示不确定的图灵机？它们实际上是等同的吗？

例如，我非常肯定超图能够正确和完整地表示非确定性图灵机的状态转换。但到目前为止，我还没有找到任何能证实这一点的印刷品。在我看来，这似乎是一种显而易见的关系，但事实上，我找不到以前的艺术，这让我觉得自己走错了轨道。(这也可能是因为我所发现的东西不足以让我理解它的意思。)

我问的原因:我正在开发一个开源包，它在对等网络中进行分布式数据存储和分布式计算。我正在寻找支持所需功能的最原始的数据结构。到目前为止，分布式超图看起来很有前途。我的推理是，如果超图能够支持像非确定性图灵机这样一般的东西，那么它应该能够支持更高级别的图灵-完全DSL。(还有其他原因-“非确定性”部分可能对我也有价值，因为它与分布式数据和/或计算结果的版本控制有关。尽量避免在这里写论文。)

部分答复：

开场白上的人们对超图如何适合不同的计算模型进行了分析讨论；这显然与HypergraphDB包的开发有关：http://markmail.org/message/5oiv3qmoexvo4v5j

• Over on MathOverflow，有一个问题讨论超图可以做什么--还没有提到图灵，但我要补充一点:超图可以表示一台不确定的图灵机器，然后我认为带有加权边的超图相当于概率式图灵机。http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

Answer 1

超图只是一个图G=(V,E)，其中V是顶点(节点)的集合，E是V的powerset的子集。这是一个数据结构。

所以一个公共图就是一个2级的超图。(也就是说，E中的每个集合都包含两个顶点)。有向超图使用对(X,Y)作为X和Y集的边。

如果你想建立图灵机的模型，那么你需要对‘磁带’建模。你想要把带子“嵌入”在图表中吗？我想你可能会更幸运地想到丘奇-图灵的论文(阿隆索·丘奇，兰达微积分)。Lambda微积分是重写系统的一种形式，当然还有一个分支使用图重写(和hypergrpahs)。

当然，转换可以被建模为一个图形(我不确定您的想法是什么，但是直接的方法并没有真正的帮助)，如果您正常地对它建模，您可能会创建一个字典/hashmap，其中元组作为键(State，符号)，值是(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)

正如我前面提到的，查找图表重写或术语重写。