如何显示两种计算模型是等效的？

Question

我正在寻找有关如何证明两种计算模型等效的解释。我一直在阅读有关该主题的书籍，但省略了等价证明。我对两种计算模型等效的含义有一个基本想法（自动机视图：如果他们接受相同的语言）。还有其他思考等效性的方法吗？如果您可以帮助我了解如何证明图灵机模型等于lambda cyculus，那就足够了。

Answer 1

您表明任何一种模型都可以 模拟 另一个在模型A中给出的机器，表明B中有一台计算相同函数的计算机。请注意，此仿真不必计算（但通常为）。

例如，考虑使用两个堆栈（2-PDA）的下降自动机。 在另一个问题中, ，概述了两个方向的模拟。如果您正式这样做，您将采用一台通用的图灵机（元组），并明确构建相应的2-PDA是什么，反之亦然。

---

正式地，这样的模拟看起来像这样。让

$ qquad displaystyle m =（q， sigma_i， sigma_o， delta，q_0，q_f）$

做一台图灵机（用一根胶带）。然后，

美元

和 $ sigma_o'= sigma_o overset {。} { cup} { $ } $ 和 $ delta' $ 给出

$ quad displayStyle（q^*_ 1，a，h_l，h_r） to _ { delta'}（q^*_ 1，ah_l，h_r）$ 对所有人 $ a in sigma_i $ 和 $ h_r，h_l in sigma_o $ $,
$ quad displayStyle（q^*_ 1， varepsilon，h_l，h_r） to _ { delta'}（q^*_ 2，h_l，h_r）$ 对所有人 $ h_r，h_l in sigma_o $ $,
$ quad displayStyle（q^*_ 2， varepsilon，h_l，h_r） to _ { delta'}（q^*_ 2， varepsilon，h_lh_r）$ 对所有人 $ h_r，h_l in sigma_o $ $ 和 $ h_l neq $$,
$ quad displaystyle（q^*_ 2， varepsilon， $，h_r） to _ { delta'}（q_0， $，h_r）$ 对所有人 $ h_r in sigma_o $ $,
$ quad displayStyle（q， varepsilon，h_l，h_r） to _ { delta'}（q'，q'， varepsilon，h_la） iff（q，q，h_r） $ 对所有人 $ q in q $ 和 $ h_l in sigma_o $,
$ quad displayStyle（q， varepsilon， $，h_r） to _ { delta'}（q'， $， square a） iff（q，h_r） to_ to_ delta（ ，l）$ 对所有人 $ q in q $,
$ quad displayStyle（q， varepsilon，h_l，h_r） to _ { delta'}（q'，ah_l，ah_l， varepsilon） iff（q，h_r） $ 对所有人 $ q in q，h_l in sigma_o'$,
$ quad displayStyle（q， varepsilon，h_l， $） to _ { delta'}（q，h_l，h_l， square $）$ 对所有人 $ q in q $ 和 $ h_l in sigma_o'$, ， 和
$ quad displayStyle（q， varepsilon，h_l，h_r） to _ { delta'}（q'，h_l，a） iff（q，h_r） to_ to_ to_ delta（q' delta（q'，q'，a，n）$ 对所有人 $ q in q，h_l in sigma_o'$

是等效的2-PDA。在这里，我们假设图灵机使用 $ square in sigma_o $ $ 作为空白符号，两个堆栈都以标记开始 $ $ notin sigma_o $ $ （从未删除）和 $（q，a，h_l，h_r） to _ { delta'}（q'，l_1 dots l_i，r_1 dots r_j）$ 意思是 $ a_m $ 消耗输入 $ a $, ，开关状态 $ Q $ 至 $ Q'$ 并更新类似的堆栈：

^[资源]

仍然要表明 $ a_m $ 进入最终状态 $ x in sigma_i^*$ 当且只有 $ m $ 这样做。这是很明显的结构。正式，您必须翻译接受运行 $ m $ 接受接受 $ a_m $ 反之亦然。

Answer 2

在。。。之初 通信和移动系统：Pi-Calculus 罗宾·米尔纳（Robin Milner）撰写，关于自动机的介绍以及它们如何相互模拟，以使它们无法区分： 仿真. 。 （参见 仿真 在Wikipedia上）

我不记得很好，我应该重新阅读本章，但是模拟和仿真遇到了麻烦，这使得它们不足以实现计算等价。

因此，罗宾·米尔纳（Robin Milner）介绍了他的pi-calculus，并在本书的其余部分中公开了它。

最终，在他的最后一本书中 交流代理的空间和运动, ，您可以看一下Robin Milner的Bigraphs。它们可以对自动机，培养皿网，Pi-Calculus和其他计算方法进行建模。

Answer 3

据我所知，这样做的唯一（或至少最常见的）方法是比较机器/模型接受的语言。这就是自动机理论的全部要点：它采用了问题或算法的模糊概念，并将其变成了一个具体的数学集（即一种语言），我们可以推论。

最简单的方法是，从一个模型中给定任意机器/功能，可以从第二个模型中构造计算相同语言的机器。赔率是您的表达式长度，机器中的状态，语法中的规则，等等。

我还没有看到Lambda和TMS完成此操作（尽管我确定这是可能的99％），但是我肯定已经看到了证明NFA和正则表达式等效的这种事情。首先，您显示一个可以接受任何原子的NFA，然后使用诱导，使NFA接受任何较小NFA的联合/串联/Kleene-Star。

然后，您会做相反的事情，以找到任何NFA的RE。