λ-演算与图灵机是等价,这里简单说下我对图灵机的理解:
在一个不限时间、不限资源的前提下,图灵机通过前进、后退、跳转、输出1或0这四个简单的命令,在一条无限长的纸带上执行事先编好的程序。
根据目前的证明,图灵机是宇宙间最强大的机器(理想中的),我们现有的计算机都没有超过图灵机。
如果说一个语言是图灵完备的,就是说,世界上任何可计算性问题,它都能解决。
我们现有的命令式语言,如C、Java等就是以图灵机为基础的。如果说这些语言图灵完备,需要具有以下两个特征:
1,有if、goto语句(或while、for之类的循环语句)
2,能够进行赋值操作(也就是改变内存状态)
与图灵机对应,λ-演算的直接影响是函数式编程语言,如lisp、Haskell等,如果说这些函数式语言图灵完备,需要有以下两个特征:
1,能够进行函数抽象(也就是函数定义)
2,能够进行函数应用(也就是函数调用)
鉴别一个语言是不是函数式的标准是:这个语言能否在运行时创建函数,如果能,就是函数式语言。