什么意思是lambda演算等同于图灵机

Question

我试图理解λ演算及其与语言、编译器和二进制代码的关系。λ演算等价于图灵机，它到底意味着什么，它在哪里体现出来？

我不明白λ演算如何取代图灵机成为计算理论模型。图灵机是关于按顺序执行指令以改变状态，而λ演算则是关于表达式求值得到某些东西。它更抽象，像是一种编程语言，而不是如何实际地计算某些东西，让事情发生的模型。或者这样说： λ演算就像路线图，图灵机就像汽车模型。这两个模型怎样等价？是否可能在不实现图灵机的情况下在硬件上运行软件？

比如，Lisp编译器和语言与λ演算有何关系？λ演算在哪一层中实现？实现是否符合λ演算的定义？λ演算背后的理论如何将语法转换成运行的二进制代码？例如，在λ演算中，数字被编码为应用到某个其他函数n次的特殊函数。然而，在语法中，我们使用数字字面量。所有这些公理在哪里使用？

- Tuomas Toivonen

---

“Church-Turing论文”是一个很好的起点。 - eush77

Answer 1

所有这些基础语言都是在计算机出现之前的时代引入的。整个研究的重点在于表征一类（数字）函数，这些函数在算法意义上“直观”可计算，而不一定是通过自动化设备进行计算。现在，λ演算和图灵机以及许多其他计算模型，如组合逻辑、Post系统、广义递归函数等，精确地表达了相同的可计算函数类。这激发了教堂论题。

我同意你的观点，即与其他模型相比，图灵机（例如随机存取机）具有更明显的架构风格。 实际上，这正是说服起初有些怀疑的哥德尔接受教堂论题有效性的原因。

我也同意你的观点，即λ演算不能超越图灵机成为计算的理论模型：在这样的操作中，没有明显的收益。

同时，λ演算很有趣，而图灵机非常无聊。它很有趣，恰恰因为它处于图灵机的极端相反位置。我认为人们可以合理地争论，它是迄今为止构思的最高级别计算模型（可能永远不会被超越）。这就是为什么它对每个程序员都是具有挑战性和教育意义的语言。

- Andrea Asperti

Answer 2

在可计算性理论中，两个计算的理论模型等价意味着它们可以解决相同的问题集。任何你能在图灵机上计算的东西，你也可以使用λ演算来计算，反之亦然。

我们如何证明这一点？只需说如果我们可以在λ演算中建模一个图灵机，那么显然λ演算可以计算图灵机可以计算的所有东西。如果我们可以在图灵机上解决λ演算，那么反过来也成立。

这两种方法都是可能的，因此这些模型被认为是等价的。

当然，在实际应用中，一个模型可能更适合某些用例。今天的计算机基于RAM状态模型，而这个模型又借鉴了图灵机的思想。λ演算确实非常抽象，不容易在物理硬件中实现。然而，这两个模型都存在于同一计算类中，它们可以解决相同的问题，因此被称为等价的。

- rp.beltran