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

Question

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

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

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

部分答案：

opencog 的人们对超图如何适应不同的计算模型进行了一次引人入胜的讨论。这显然与 HypergraphDB 包的开发有关：http: //markmail.org/message/5oiv3qmoexvo4v5j
在 MathOverflow 上，有一个问题讨论超图可以做什么——还没有提到图灵，但我要添加它： https ://mathoverflow.net/questions/13750/what-are-the-applications-of - 超图
如果超图可以表示非确定性图灵机，那么我认为具有加权边缘的超图将等效于概率图灵机。 http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

score 2 · Accepted Answer

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

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

如果要对图灵机建模，则需要对“磁带”进行建模。你想把磁带“嵌入”到图表中吗？我认为您可能会更幸运地考虑 Church-Turing 论文（Alonso Church，Lambda calculus）。Lambda 演算是重写系统的一种形式，并且肯定有一个使用 Graph 重写（和 hypergrpahs）的分支。

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

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

所以如果你想要一个图表，你首先需要 V = states 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)

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

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

1 回答 1

Related

Reference