函数构成的世界

【作者：孔教员,编号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)

的严谨记法，表明了我们要替换的变量。而β

规约实际上就是根据定义计算函数的一个过程。最后，还有一个η

变换。它的实质是所谓的外延性，也就是说，如果两个项对所有函数的作用都是相同的话，那么就认为这两个项是相同的。这么几条简单的法则，就是丘奇的λ演算的全部内容。那么简单的法则，很难想象λ演算能表达什么复杂的数学概念，这看起来不过是符号的简单推演而已。但既然同样简单的图灵机中也暗藏玄机，那说不定λ演算也有它自己的复杂内涵。