2

我正在寻求解释如何证明计算模型是等价的。我一直在阅读有关该主题的书籍，但省略了等价证明。我对两个计算模型等效意味着什么有一个基本概念（自动机视图：如果它们接受相同的语言）。是否有其他思考等价的方法？如果你能帮助我理解如何证明图灵机模型等价于 lambda 演算，那就足够了。

4

1 回答 1

1

要证明模型A等价于模型B，您需要证明：

  1. 模型A并不比模型强B
  2. 模型B并不比模型强A

要证明模型 X 并不比模型 Y 更强，必须证明：

对于来自 X 的每一台机器，存在来自 Y 的一台机器，使得 L(M_X) = L(M_Y)

[其中 M_X 和 M_Y 分别是每个型号的不同机器]

一个常见的众所周知的证明是：

  • DFA 等价于 NFA
  • NFA 等价于带有 epsilon 移动的 NFA
  • 多带图灵机相当于一台带图灵机

可以在图灵机等效项下阅读有关此主题的更多信息

另请注意，声明：the automata view: if they accept the same languages不正确。
您不需要在两个模型中显示相同的自动机接受相同的语言。
您需要证明，对于 A 中的每个自动机，B 中都有一个自动机，使得 L(M_A) = L(M_B) 反之亦然

于 2012-08-19T14:34:14.697 回答