theory - 超图可以表示非确定性图灵机吗？

Question

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

例如，我非常确定超图能够正确且完整地表示非确定性图灵机的状态转换。但到目前为止，我还找不到任何可以证实这一点的打印品。在我看来，这似乎是一种显而易见的关系，但事实上，我没有找到现有技术，这让我觉得我走错了路。 (也可能是我发现的内容不够容易理解，无法理解它的意思。);-)

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

部分答案:

• 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

Answer 1

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

因此，普通图只是等级为 2 的超图。(即 E 中的每个集合恰好包含两个顶点)。有向超图使用(X,Y)对作为边，其中X和Y是集合。

如果您想对图灵机进行建模，那么您需要对“磁带”进行建模。您想要将磁带“嵌入”图表中吗？我认为你可能会更幸运地思考丘奇-图灵论文(阿隆索丘奇，Lambda 演算)。 Lambda 演算是重写系统的一种形式，并且肯定有一个使用图重写(和 hypergrpahs)的分支。

当然，可以将转换建模为图表(我不确定您的想法，但直接的方法并没有真正的帮助)如果您正常建模，您可能会创建一个字典/ HashMap ，其中元组作为键(状态，符号)，值为(状态，重写，左|右)。例如

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)

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