超图能代表一种不确定的图灵机吗？

Question

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

例如,我非常确定超图能够正确且完整地表示非确定性图灵机的状态转换.但到目前为止,我还没有找到任何可以验证这一点的印刷品.在我看来,这似乎是一种如此明显的关系,但事实上,我没有找到现有的艺术,这让我觉得我走错了路.(也可能是我发现的东西不足以让我理解它在说什么.);-)

为什么我要问:我正在开发一个开源软件包,它在对等网络中进行分布式数据存储和分布式计算.我正在寻找可能支持所需功能的最原始的数据结构.到目前为止,分布式超图看起来很有希望.我的理由是,如果超图可以支持像非确定性图灵机一样通用的东西,那么它应该能够支持更高级别的图灵完整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

Answer 1

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

所以一个普通图只是一个秩为 2 的超图。（即 E 中的每个集合恰好包含两个顶点）。有向超图使用对(X,Y)作为边，其中X和Y是集合。

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

当然，转换可以建模为图形（我不确定你在想什么，但直接的方法并没有真正帮助）如果你正常建模，你可能会创建一个带有元组的字典/哈希图键（状态、符号）和值为（状态、重写、左|右）。例如

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)

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