函數構成的世界

【作者：孔教員,編號59417 更新時間：2013-07-14】 數學家眼中的函數，比你想像的要廣泛得多。在中學數學中，說到函數，自然會聯想起它在平面直角坐標系的圖像。這是因為中學數學中的函數，大部分情況下不過是從實數到實數的映射而已。而數學家眼中的函數，可能與程序員眼中的函數更相似：它們更像是一個黑箱，從一邊扔進去某個東西，另一邊就會吐出來另一個東西。
我們并沒有限定能扔進黑箱的東西。事實上，將黑箱本身扔進黑箱也是可以的。對這種把戲，數學家們再熟悉不過了，在泛函分析這一數學分支中，數學家們就經常研究一種叫“算子”的數學概念，在某些特殊情況下，就是那些將一個函數變成另一個函數的函數。所以，不去限定能扔進黑箱的東西，似乎也沒什么問題.
而言之，函數就是將一個函數變成另一個函數的東西。那么，要用符號表達這么普遍的函數概念，我們需要什么呢？首先，就像在方程中我們用x, y, z等等符號表示未知數，我們也希望能用符號表示未知函數。我們將這些表示未知函數的符號稱為變量。其次，如果我們手上有兩個函數M

和N

，那么我們自然希望研究函數N

被函數M

“處理”之后會變成什么。也就是說，既然M

是一個函數，能將一個函數變成另一個函數，那么M

會將N

這個函數變成什么呢？即使不知道具體的過程，我們也希望能表達最后的結果。所以，我們將N

被M

處理后得到的結果記為(MN)

。這被稱為函數的應用（application）。最后，也是最抽象的概念，就是函數的抽象（abstraction）。我們可以用變量x來表示未知的函數，自然也可以用x來構造更多的函數。比如(xx)

就表示函數x應用到自己身上的結果，而((xx)y)

就表示將剛才得到的結果應用到另一個未知函數y上得到的結果，如此等等，不一而足。如果我們將變量x替換成一個具體的函數f，那么這些包含變量x的表達式就會變成包含具體函數f的表達式。也就是說，如果我們有一個包含變量x的表達式M

，對于任意一個函數f，我們可以將它對應到一個新的表達式，記作M(f)

，而這個新的表達式是將M中的所有x替換成f所得到的。比如說，如果M=(xx)

，那么M(f)=(ff)

，M((yy))=((yy)(yy))

，等等。一個表達式也是一個函數。我們從表達式M出發，可以得到把一個函數f對應到另一個函數M(f)

的方法，而這正是一個函數。也就是說，我們能從一個表達式“抽象”出一個函數。我們將這個函數記作λx.M

，x是我們所要考慮的自由變量。【注：在這里，我們只能替換那些所謂的“自由變量”。粗略地說，自由變量是那些之前沒有被抽象過的變量。詳細的技術細節略顯繁復，而且也有辦法繞過，所以于此略過。】從這三點基本要求出發，丘奇開始定義他的λ演算。他將他考慮的這些函數稱為“λ項”，而所有的λ項都可以從以下三種途徑構造而成：1. （變量）所有變量x,y,z,…

都是λ項。
2. （應用）如果M

和N

都是λ項，那么(MN)

也是λ項。
3. （抽象）如果M

是一個λ項而x是一個變元，那么λx.M

也是一個λ項。接下來，丘奇定義了一些λ項之間的轉換法則。首先是α

重命名，這項轉換可以使我們在遵循一定的規則下，任意變換λ項中的變量名稱，而不改變λ項本身的意義。也就是說，λ項中變量的名稱無關緊要，無論是x, y, z還是蘋果、香蕉、榴蓮，又或者是小莊、游游、李清晨，項的本質是不變的。然后是最重要的β

規約：(λx.M)f→βM[x←f]
在這里，M[x←f]

實際上是M(f)

的嚴謹記法，表明了我們要替換的變量。而β

規約實際上就是根據定義計算函數的一個過程。最后，還有一個η

變換。它的實質是所謂的外延性，也就是說，如果兩個項對所有函數的作用都是相同的話，那么就認為這兩個項是相同的。這么幾條簡單的法則，就是丘奇的λ演算的全部內容。那么簡單的法則，很難想象λ演算能表達什么復雜的數學概念，這看起來不過是符號的簡單推演而已。但既然同樣簡單的圖靈機中也暗藏玄機，那說不定λ演算也有它自己的復雜內涵。