functional-programming - lambda 演算等价于图灵机是什么意思

Question

我正在尝试围绕 lambda 演算，以及它与语言、编译器和二进制代码的关系。 lambda 演算等同于图灵机的实际含义是什么，它实际上在哪里表现出来？

我不明白 lambda 演算如何取代图灵机作为计算的理论模型。图灵机是关于改变状态的顺序指令，lambda 演算是关于对某些东西进行评估的表达式。它更抽象，就像它自己的编程语言，而不是如何实际计算某些东西、使事情发生的模型。或者让我们这样说:lambda 演算就像路线图，而图灵机就像汽车模型。这两个如何被认为是等价的？是否有可能在不实现图灵机的情况下在硬件上运行软件？

例如，lisp 编译器和语言如何与 lambda 演算相关？ lambda演算在哪一层实现？就 lambda 演算的定义而言，实现是否纯粹？ lambda 演算背后的理论在哪里以及如何将语法转换为正在运行的二进制文件？例如，在 lambda 演算中，数字被编码为应用于其他函数 n 次的特殊函数。然而在语法上，我们使用数字文字。所有这些公理在哪里使用？

Answer 1

所有这些基础语言都是在计算机出现之前的时代引入的。研究的重点在于描述一类(数值)函数，这些函数在算法意义上看起来“直观”可计算，而不必通过自动设备进行计算。现在，事实证明，lambda 演算和图灵机，以及许多其他计算模型，如组合逻辑、Post 系统、广义递归函数等，都精确地表达了同一类可计算函数。这激发了丘奇的论点。

我同意你的观点，图灵机(如随机访问机)有更多
相对于其他模型的建筑风格。
事实上，这就是让 Goedel 信服的原因，他起初有点
怀疑，丘奇论文的有效性。

我也同意你的观点，lambda 演算不能取代图灵机作为计算的理论模型:在这样的操作中没有任何明显的好处。

同时，lambda 演算很有趣，而图灵机是致命的
无聊的。很有趣，正是因为它与图灵处于极端相反的位置
机器。我认为可以合理地争辩说这是最高级别
曾经构想过的计算模型(并且可能永远
是)。这就是为什么它对每个人来说都是一种具有挑战性和指导性的语言。
程序员。