lambda演算和图灵机

λ演算(lambda calculus)是一套用于研究函数定义、函数应用和递归的形式系统。它由阿隆佐·邱奇和他的学生斯蒂芬·科尔·克莱尼在20世纪30年代发明的。 λ演算可以被称为最小的通用程序设计语言。它包括一条变换规则(变量替换)和一条函数定义方式。 λ演算表达了两个计算机计算中最基本的概念“代入”和“置换”。“代入”我们一般理解为函数调用,或者是用实参代替函数中的形参;“置换”我们一般理解为变量换名规则。“代入”就是用lambda演算中的β-归约概念。而“替换”就是lambda演算中的α-变换。