λ转换演算
[拼音]：λ zhuanhuan yansuan
[外文]：calculus of λ-conversion
用以定义可计算函数的形式演算系统。其特点是把函数与函数值明显区分，并把函数的演算归结为按一定规则进行一系列的转换，最后得到函数值。它在递归函数论和程序设计语言方面有重要应用。
研究概况
M.熊芬克尔、H.B.柯里和A.丘奇等分别于20年代开始研究组合逻辑和λ演算。丘奇从几个基本函数出发，构造λ可定义函数类。λ可定义函数与递归函数的等价性是丘奇为其论题直观的可计算函数类等同于递归函数类辩护时使用的论证之一。历史上第一个不可判定问题就是丘奇构造的“任意给定的λ演算的表达式是否有归约式”。图灵机可计算函数与一般递归函数的等价性是通过λ演算证明的。在递归函数论的早期研究中，λ演算起了重要作用。
丘奇最初把λ演算设计为他的一般函数系统的一部分，并试图使此函数系统成为数学的基础。S.C.克林和J.B.罗塞证明了这个系统是不一致的。丘奇于1941年提出现有部分作为一致的子理论。1969年D.斯科特构造了该理论的模型，进一步完善了λ演算系统。
基本内容
数学中的函数记法f(x)既可表示函数值，也可表示函数本身。为了避免这种含混，丘奇限定f(x)只表示函数值，而用λxf(x)表示函数。从研究变元取值和函数施用于变元的概念入手，用λ表达式定义函数，用一些严格定义的关于λ表达式的转换规则刻划函数的计算过程。
λ 表达式
用于从几个基本函数出发定义可计算函数类。λ表达式是从初始符号（λ，左、右括号，变量字母）开始归纳地定义的：任何变量是λ表达式；如果M、N是λ表达式，则MN是λ表达式；如果M是λ表达式，x是自由出现于M中的变量，则λxM是λ表达式（如果变量x出现在M中某个形如λxM′的子表达式中，则称x在M中是约束出现的;否则称x在M中是自由出现的）。表达式λxM表示一个变元的函数，λx称为约束变量部分，M称为体部分。以后继函数f（x）=x+1为例，其λ表达式为λx(x+1)，f(x)施用于整数自变量3可用如下λ表达式表示
f(3)=λx(x+1)(3)
式中子表达式λx(x+1)称为该λ表达式的算子部分;子表达式3称为其操作数部分。于是表达式(MN)表示把算子部分M施用于操作数部分N，这对应于函数的变量取值为N的情形。函数符号本身也可作为变量赋值。
正整数作为常函数可由λ表达式定义，加、减、乘和乘幂等初等函数也可由λ表达式定义。可由λ表达式定义的函数称为λ可定义的。丘奇证明，每个部分递归函数是λ可定义的，而且每个λ可定义的函数是部分递归的，即λ可定义函数与部分递归函数是等价的。
转换规则
λ演算的计算过程，是按照一些严格定义的转换规则，进行λ表达式的转换。这些规则，保证把一个λ表达式转换成另一个等价的λ表达式。如果用M[x/N]表示以N代换M中x的自由出现所得到的结果，则λ演算有如下规则：如果y不在M中自由出现，则λxM可用等价的λyM[x/y]代换；如果M的约束变量中既不含x，也不含自由出现于N中的变量，则可用M[x/N]代换λ表达式中任何(λxM)N，也可用(λxM)N代换λ表达式中任何的M[x/N]。按这些规则进行的转换称为β转换。通过修改或添加某些规则，可得到其他类型的转换。
一个λ表达式如果不再含有λxMA形式的子表达式，则称为归约式，它对应于函数值。例如λ表达式λx(x+1)(3)+λx(x+1)（4）经上述规则转换成(3+1)+(4+1)，这个归约式对应于函数值 9。任意给定的一个表达式是否有归约式这个问题，是不可判定的。如果一个λ表达式含有一个以上的形如λxMA的子表达式，则计算的下一步是不确定的。但这种不确定性并不影响计算的最终结果。一般地，如果一个λ表达式的不同转换序列均导致归约式，则这些归约式是等价的。
λ演算与程序设计语言
ALGOL、LISP等程序设计语言的结构与丘奇的λ演算之间存在着一种本质的对应关系。例如，λ 演算中的函数λ(x1x2…xn）M 与 ALGOL 过程之间存在明显的对应关系：前者的约束变量部分为λ(x1x2…xn)对应于后者的过程参数表；前者的体部分M对应于后者的过程体。λ演算也能反映嵌套子程序和求值次序等结构，可以用作研究某些程序语言的比较自然的模型，函数式语言LISP就是建立在λ演算的基础上的。
建筑资质代办咨询热线：13198516101
标签：λ转换演算
版权声明：本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称：《λ转换演算》
文章链接：https://www.scworui.com/13602.html
该作品系作者结合建筑标准规范、政府官网及互联网相关知识整合。如若侵权请通过投诉通道提交信息，我们将按照规定及时处理。
咨询热线：13198516101 
