为什么要逐个评估策略未完成？

Question

我正在阅读有关不同的文章 评估策略 （我链接了Wiki中的文章，但我正在阅读另一本书，而不是英语）。它说与 call-by-name 和 call-by-need 策略， call-by-value 策略是 不是 图灵完成.

有人可以解释一下，为什么这样做？如果可能，请添加一个示例。

Answer 1

我对索赔提出异议 在您正在阅读的文章中。 （我没有为此获得报酬，所以我将提供一个暗示的论点，而不是证明。）

众所周知，至少在正常订购降低（又称名称）下，纯lambda cyculus是图灵完整的。但是，如果我们看约翰·雷诺兹的开创性论文 高阶编程语言的定义口译员, ，我们可以看到，雷诺兹详细讨论按名称和呼叫按值呼叫之间的差异。论点的关键部分是，为了做出适当的区别，我们可以将程序转换为 延续通过的风格. 。 CPS变换符合需要和值的呼叫而不同，但是可以以任何一种样式评估所得的转换术语。

因此，参数是：编写一个lambda-calculus程序，该程序模拟图灵机，然后使用CBN变换进行CPS转换，您可以使用CBV减少策略评估结果代码。砰!图灵完整。

在实践中，我敢打赌，您可以编写CBV程序来模仿图灵机。可能足以选择合适的定点组合器，例如θ。 （更著名的Y组合器仅在逐个名称的降低策略下工作，即减少正常订单。）

免责声明： 我已经很久没有学习过Lambda演算了，而且我敢肯定上面的论点中有几个细节。但是我对这种物质充满信心。这不是我第一次在在线资源中发现有关编程理论的事情。

Answer 2

没有参考某些特定语言的情况，您的问题并没有多大意义，但是我会尽力回答关于未型的Lambda演算。

未型lambda cyculus的逐个呼叫固定点组合器（即“ Y组合”）的存在似乎反驳了基本主张（请参阅： 固定点组合器）。这种组合者的存在破坏了强大的规范化，这表明至少有一种使用逐个评估策略的图灵完整的语言。

更有可能影响语言的图灵完整性是一种类型系统的存在（或缺乏）。例如，简单型的lambda演算无法编码固定点组合器，并且正在强烈正常化（即所有良好的术语降低到一个价值），但是，无论采用评估策略如何，这都是正确的。相反，这是类型系统的结果。