他的思想代表了逻辑和语言 |《走进计算机文化史》之六
本文经「原理」（微信公众号：principia1687）授权转载，禁止二次转载
上期文章（详见：《一个无法证明的逻辑问题》）中我们讲到了图灵在哥德尔证明了不完备理论之后用图灵机的概念完整地证明了希尔伯特判定性问题，并因此从数学理论中开辟出了计算机科学的分支。但即便是这样，图灵的理论撑起的也仅是计算机领域的半边天。如果把日益兴起的计算机科学比作一个成长的巨人，那么图灵也只是支撑巨人的其中一只脚。而这一期我们介绍的便是和图灵共同为计算机科学奠基的人——阿隆佐·丘奇（Alonzo Church）。
△ 阿隆佐·丘奇。 （图片来源：Wikipedia）
可以说丘奇和图灵是两位对计算机科学影响最大的人。而世人却是知道图灵的多，但了解丘奇的少。因为美国计算机学会（ACM）每年都会颁发计算机界的诺贝尔奖 ——“图灵奖”，而丘奇的名字却鲜有人提起。而且现绝大多计算理论教科书中在提到可计算理论（computability）和复杂度理论（complexity）的时候也都是用图灵机的概念来叙述的。但如果我们去看图灵1938年在普林斯顿大学递交的博士论文 （Systems of Logic Based On Ordinals），我们会发现其大量的篇幅都用到了一个概念作为该论文的基础：λ 算子（λ-calculus）。而 λ算子的发明人，便是图灵博士时期的导师——阿隆佐·丘奇。
什么是 λ 算子？
简单来说，λ 算子是丘奇用来定义函数的一个媒介。如图1所示，丘奇将函数看作一个接收输入并产生输出的黑箱，并将黑箱定义为 λ 算子。λ 算子可以接受任意数量的输入并最终产生一个输出。如图1的函数定义便是。其中 λ 算子表示函数（黑箱），小数点前面的 x 和 y 表示函数的输入，而小数点后面的 x + y 表示函数的输出。
△ 图1：λ算子函数 示意图。
这样的函数定义有两个特点：
函数的定义是一个黑箱，我们对黑箱内部的一切计算或设计一无所知也毫不在乎；
从输入到输出一蹴而就，没有中间状态。
这就和上期文章中提到的图灵机概念有了截然不同的区别。图灵机是在接收输入之后，在程序的影响下经过一系列的读写头位置的变化（或机器状态的变化）最终停止运行并得到一个输出。而 λ 算子在收到输入后直接产生输出。从另外一个角度来看，我们也可以把图灵机看作一个黑箱并把它定义成为一个 λ 算子。而唯一不同的是我们并不在乎图灵机内部的运作（即读写头如何受程序和输入影响变化），相反，我们只在乎这个图灵机的功能（从现有的输入能够得到什么样的输出）。从这个视角我们至少可以看出两点：
图灵机和λ算子之间是有联系的；
图灵机强调的是过程，而λ算子强调的是结果。
那么这两点分别意味着什么呢？我们先来看图灵机和λ算子的联系。
△图2：图灵机的结构。（图片来源：Wikipedia）
从上期的文章中我们总结了图灵机概念里构成现代计算机体系的三个因素：
输入和输出由图灵机中用纸带上每个格子里的数字或字母表示。
从程序运行开始至结束读写头经历的不同的机器状态（包括当下读写头的位置，当下位置上的输入，以及在当下输入和程序的控制下读写头的移动方向及移动之后的输出），由图灵机中的状态寄存器记录。
对读写头移动位置的决策过程，有图灵机中的规则表（即我们所说熟知的的程序或算法）控制。
图灵用机器的概念构造出了这三个因素，而丘奇则用一个更为简洁的数学方式 —— λ 算子构造出了相同的因素。
我们首先来看输入输出。在图灵机中输入输出就是纸带上的一串数字或字母。而从 λ 算子来看，函数输入便是小数点左边的字母，输出便是小数点右边的表述。其次我们再看机器状态的变化。在图灵机中机器状态即是正整数，用于表示从程序开始到结束读写头经历了多少次机器状态的变化。从数学的角度来看，我们只需要定义两个函数，零（zero）和后继元素（successor）便可以表示所有正整数。因为通过一个数字 a 的后继元素我们能得到 a + 1，我们可以用递归的方式通过我们定义的零（zero）得到任何另一个正整数。于是丘奇用 λ 算子定义了这两个函数：
零的定义很好理解，无论多少输入，函数输出都为0。后继元素的定义需要用到alpha-变换规则和beta-规约规则，在这里笔者不做赘述，有兴趣的读者可以阅读有关计算理论的教科书。总而言之，丘奇用两个很简单的 λ 算子定义了图灵机的机器状态。最后我们来看决策过程。在图灵机中的决策过程是由程序或算法决定，而在数学定义中任何决策是由布尔运算来决定。于是丘奇定义了三个布尔运算函数，分别是真（true），假（false）及如果（if）:
从上面的定义我们可以看出，在 λ 算子中，真的定义为一个两个输入的函数取其中一个作为输出，而假的定义为一个两个输入的函数取另一个作为输出。而所有的布尔运算如与、非、或等都可以从这三个定义中推导出来。至此丘奇用极其简单的数学模型（λ算子）构建了所有组成图灵机的重要因素。从而我们得出结论，一切图灵机能做到的，我们通过λ算子也能做到，而且是以一种更为简洁和抽象的数学方式。也就是说，如果图灵的思想代表了算法和机器，那么丘奇的思想便代表了逻辑和语言。这也就是为什么迄今为止几乎所有编程语言的根本都是基于 λ 算子之上的。
回到我们之前得出的另一个结论，图灵机强调的是过程，而 λ 算子强调的是结果。无独有偶的是，迄今为止的编程语言大体都可以被分成两大类——命令式编程（Imperative Programming）和函数式编程（functional Programming）。命令式编程强调告诉机器通过什么样机器状态的变化来达到结果，如 Fortran，C/C++等。而函数式编程只强调告诉机器做什么，并没有机器状态变化的概念，如Haskell， OCaml等。也就是说，命令式编程的思想以及后来对算法的研究均来自于图灵机的概念（虽然其本质的语言构建还是基于lambda算子）而函数式编程的思想则完全基于 λ 算子。正是这两种本质相同却有着不同侧重点的思想造就了如今计算机领域里的语言设计学，算法学，体系结构学等不同的分支。也正因如此，丘奇和图灵的思想被誉为计算机科学最重要的两大基石。
下回预告：图灵机和 λ 算子具体是如何做计算的呢？这两个不同的思想又是怎样影响语言设计和体系结构的发展呢？
往下拉可在留言处发表你的见解