[拼音]：λ zhuanhuan yansuan

[外文]：calculus of λ-conversion

用以定義可計(jì)算函數(shù)的形式演算系統(tǒng)。其特點(diǎn)是把函數(shù)與函數(shù)值明顯區(qū)分，并把函數(shù)的演算歸結(jié)為按一定規(guī)則進(jìn)行一系列的轉(zhuǎn)換，最后得到函數(shù)值。它在遞歸函數(shù)論和程序設(shè)計(jì)語言方面有重要應(yīng)用。

研究概況

M.熊芬克爾、H.B.柯里和A.丘奇等分別于20年代開始研究組合邏輯和λ演算。丘奇從幾個(gè)基本函數(shù)出發(fā)，構(gòu)造λ可定義函數(shù)類。λ可定義函數(shù)與遞歸函數(shù)的等價(jià)性是丘奇為其論題直觀的可計(jì)算函數(shù)類等同于遞歸函數(shù)類辯護(hù)時(shí)使用的論證之一。歷史上第一個(gè)不可判定問題就是丘奇構(gòu)造的“任意給定的λ演算的表達(dá)式是否有歸約式”。圖靈機(jī)可計(jì)算函數(shù)與一般遞歸函數(shù)的等價(jià)性是通過λ演算證明的。在遞歸函數(shù)論的早期研究中，λ演算起了重要作用。

丘奇最初把λ演算設(shè)計(jì)為他的一般函數(shù)系統(tǒng)的一部分，并試圖使此函數(shù)系統(tǒng)成為數(shù)學(xué)的基礎(chǔ)。S.C.克林和J.B.羅塞證明了這個(gè)系統(tǒng)是不一致的。丘奇于1941年提出現(xiàn)有部分作為一致的子理論。1969年D.斯科特構(gòu)造了該理論的模型，進(jìn)一步完善了λ演算系統(tǒng)。

基本內(nèi)容

數(shù)學(xué)中的函數(shù)記法f(x)既可表示函數(shù)值，也可表示函數(shù)本身。為了避免這種含混，丘奇限定f(x)只表示函數(shù)值，而用λ_xf(x)表示函數(shù)。從研究變?cè)≈岛秃瘮?shù)施用于變?cè)母拍钊胧?，用λ表達(dá)式定義函數(shù)，用一些嚴(yán)格定義的關(guān)于λ表達(dá)式的轉(zhuǎn)換規(guī)則刻劃函數(shù)的計(jì)算過程。

λ 表達(dá)式

用于從幾個(gè)基本函數(shù)出發(fā)定義可計(jì)算函數(shù)類。λ表達(dá)式是從初始符號(hào)（λ，左、右括號(hào)，變量字母）開始?xì)w納地定義的：任何變量是λ表達(dá)式；如果M、N是λ表達(dá)式，則MN是λ表達(dá)式；如果M是λ表達(dá)式，x是自由出現(xiàn)于M中的變量，則λ_xM是λ表達(dá)式（如果變量x出現(xiàn)在M中某個(gè)形如λ_xM′的子表達(dá)式中，則稱x在M中是約束出現(xiàn)的;否則稱x在M中是自由出現(xiàn)的）。表達(dá)式λ_xM表示一個(gè)變?cè)暮瘮?shù)，λ_x稱為約束變量部分，M稱為體部分。以后繼函數(shù)f（x）=x+1為例，其λ表達(dá)式為λ_x(x+1)，f(x)施用于整數(shù)自變量3可用如下λ表達(dá)式表示

f(3)=λ_x(x+1)(3)

式中子表達(dá)式λ_x(x+1)稱為該λ表達(dá)式的算子部分;子表達(dá)式3稱為其操作數(shù)部分。于是表達(dá)式(MN)表示把算子部分M施用于操作數(shù)部分N，這對(duì)應(yīng)于函數(shù)的變量取值為N的情形。函數(shù)符號(hào)本身也可作為變量賦值。

正整數(shù)作為常函數(shù)可由λ表達(dá)式定義，加、減、乘和乘冪等初等函數(shù)也可由λ表達(dá)式定義?？捎搔吮磉_(dá)式定義的函數(shù)稱為λ可定義的。丘奇證明，每個(gè)部分遞歸函數(shù)是λ可定義的，而且每個(gè)λ可定義的函數(shù)是部分遞歸的，即λ可定義函數(shù)與部分遞歸函數(shù)是等價(jià)的。

轉(zhuǎn)換規(guī)則

λ演算的計(jì)算過程，是按照一些嚴(yán)格定義的轉(zhuǎn)換規(guī)則，進(jìn)行λ表達(dá)式的轉(zhuǎn)換。這些規(guī)則，保證把一個(gè)λ表達(dá)式轉(zhuǎn)換成另一個(gè)等價(jià)的λ表達(dá)式。如果用M[x/N]表示以N代換M中x的自由出現(xiàn)所得到的結(jié)果，則λ演算有如下規(guī)則：如果y不在M中自由出現(xiàn)，則λ_xM可用等價(jià)的λ_yM[x/y]代換；如果M的約束變量中既不含x，也不含自由出現(xiàn)于N中的變量，則可用M[x/N]代換λ表達(dá)式中任何(λ_xM)N，也可用(λ_xM)N代換λ表達(dá)式中任何的M[x/N]。按這些規(guī)則進(jìn)行的轉(zhuǎn)換稱為β轉(zhuǎn)換。通過修改或添加某些規(guī)則，可得到其他類型的轉(zhuǎn)換。

一個(gè)λ表達(dá)式如果不再含有λ_xMA形式的子表達(dá)式，則稱為歸約式，它對(duì)應(yīng)于函數(shù)值。例如λ表達(dá)式λ_x(x+1)(3)+λ_x(x+1)（4）經(jīng)上述規(guī)則轉(zhuǎn)換成(3+1)+(4+1)，這個(gè)歸約式對(duì)應(yīng)于函數(shù)值 9。任意給定的一個(gè)表達(dá)式是否有歸約式這個(gè)問題，是不可判定的。如果一個(gè)λ表達(dá)式含有一個(gè)以上的形如λ_xMA的子表達(dá)式，則計(jì)算的下一步是不確定的。但這種不確定性并不影響計(jì)算的最終結(jié)果。一般地，如果一個(gè)λ表達(dá)式的不同轉(zhuǎn)換序列均導(dǎo)致歸約式，則這些歸約式是等價(jià)的。

λ演算與程序設(shè)計(jì)語言

ALGOL、LISP等程序設(shè)計(jì)語言的結(jié)構(gòu)與丘奇的λ演算之間存在著一種本質(zhì)的對(duì)應(yīng)關(guān)系。例如，λ 演算中的函數(shù)λ(x₁x₂…x_n）M 與 ALGOL 過程之間存在明顯的對(duì)應(yīng)關(guān)系：前者的約束變量部分為λ(x₁x₂…x_n)對(duì)應(yīng)于后者的過程參數(shù)表；前者的體部分M對(duì)應(yīng)于后者的過程體。λ演算也能反映嵌套子程序和求值次序等結(jié)構(gòu)，可以用作研究某些程序語言的比較自然的模型，函數(shù)式語言LISP就是建立在λ演算的基礎(chǔ)上的。

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：λ轉(zhuǎn)換演算

版權(quán)聲明：本文采用知識(shí)共享 署名4.0國(guó)際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《λ轉(zhuǎn)換演算》

文章鏈接：http://www.kaputelugumatrimony.com/13602.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識(shí)整合。如若侵權(quán)請(qǐng)通過投訴通道提交信息，我們將按照規(guī)定及時(shí)處理。