证明：过程式语言 > 图灵机 = 纯函数型语言

instemast

首先我们应当清楚，"能够实现" 和 "易用" 是两个不同的概念。
用电路元件可以实现任何家电，而电视机却不能洗衣服。
但是前者的“易用”性显然低于后者。

--------------------------------------------------------------------

1) 目前已被证明，拉姆达计算（函数型语言）和图灵机是相互等价的。

2) 过程式语言，可以做到纯函数型语言所做不到的事情，举例如下：

   y(t) = f(x(t))
   其中 x(t) 可以被用户自由set，也可以get当前的x值。
   这个代码没有办法用纯函数型语言去实现，因为不能保存x的上一时刻的值。
   并且也没有办法递归解决，除精度问题外，还有个根本原因是：
       没有办法重现上一时刻用户的输入了。
   
   换言之，纯函数型语言无法保存系统状态。

   3) 故，过程式语言可以实现的东西，大于纯函数型语言。

由 1) 3) ， 过程式语言可以实现的东西，大于图灵机。

--------------------------------------------------------------------

PS. 话虽如此，F#是混合型语言，即在必要时可以用过程式。
此外，仿真语言中（也是函数风格的），不存在上述所谓"实现不了"的问题。

CLOD

我还不知道图灵机是啥呢……

bskk

操，到这种论坛上来装B

bskk

大于图灵机有怎样，在这有实际意义吗

instemast

bskk: Re:证明：过程式语言 > 图灵机 = 纯函数型语言

大于图灵机有怎样，在这有实际意义吗

这导致 LISP 等函数型语言，历史上输给了C++,Java,VB等过程式语言。