流水线上的神奇转换

陈凯

伽利略认为，上帝用来描述宇宙的文字是数学。这句话是否正确，还真是很难说，但可以肯定的是，当代人类用来构造虚拟世界的文字正是数学。数学家喜欢用简洁、和谐、统一的文字来描绘他们心中的虚拟世界，只可惜，这种“简洁、和谐、统一”的数学之美，对于未经受过数学和逻辑方面专业训练的普通人来说，就像无法琢磨的抽象画。然而，如果能把抽象的数学符号系统变成形象、直观的游戏，那么数学家用一堆数字和符号所揭示的深刻道理，就能更清晰地展现在普通人，甚至是小朋友的面前。本文尝试借助一个叫做“流水线”的文字游戏，带领大家初窥可计算性理论大门中的景象。

● 奇妙流水线

想象有这么一座工厂，工厂中有多条生产流水线，这些流水线都是某个神奇博士设计的，人们并不知道神奇博士究竟是怎么设计出这些流水线的，不过好在不同流水线的面板上，都用标识清楚地说明了其用途，告诉人们应当在流水线的输入口放进什么，在流水线的输出口获得什么。

比如说，有一条流水线的入口处，标了土豆和番茄，看起来是一条食品加工流水线，假如输入的是土豆和番茄，那么最后得到的是土豆（如下图），番茄神秘地消失了。如果输入的是番茄和土豆，那么最后得到的是番茄，总之，依次输入两样东西，总会得到先输入的那样。第一次使用这条流水线的人，无不诧异，这东西到底有什么实际作用？这条流水线不能依次输入三样东西，非要尝试的话，流水线会卡住。其实，输入三样、四样乃至更多样东西的流水线都是能设计出来使用的，神奇博士只是担心普通使用者的脑运算量不足会导致情绪崩溃，所以暂且做出了这样的限制。接下来是个关键：神奇博士给这条流水线起了个名字，叫做土豆，还给流水线贴上了如下标识：

T：

ab->a（X，Y）

这段标识很简洁（但比数学家实际用的那些符号稍微冗长一些），其意思如下：

此流水线名为土豆：

依次输入某物a和某物b，总会得到a，括号里表示可以输入两个物件，使用者究竟输入什么，是无法预知的X和Y。换句话说，即便使用者输入的是白菜和胡萝卜也是可以的，结果会得到先输入的物件，就是白菜。

神奇博士的另一条流水线的标识是这样的：

F：

ab->b（X，Y）

相信大家能看明白，此流水线名为番茄，依次输入某物a和某物b，总会得到b，使用者可自由决定输入某两个物件。心智正常的人肯定会觉得，除了按规则吐出后一个物件、吞噬前一个物件之外，此流水线并无实际作用。

想象一下，神奇博士的车间里有一位记录员，他会把每个使用者的动作记录下来，假如使用者在流水线入口依次输入土豆和番茄，他就记录为ab->b（X，Y）（t，f），后面的括号里是使用者实际输入的物件，他用小写t代表土豆，用小写f代表番茄，若是他观察完流水线的整个运行，那么可能就会记录为ab->b（X，Y）（t，f）=f。不过，后来他发现了一种偷懒的好办法，因为既然流水线被命名为“F”，那他只要记录下F（t，f）=f就可以了。

神奇博士的车间有许多参观者，大概因为好奇心使然，大家都将各种成对的物件放入流水线中（这莫非是神奇博士不可告人的敛财手段），直到某一天，有人忽然想到，其实可以把流水线输入流水线。

● 把流水线输入流水线

如果把一条流水线塞入某条流水线的入口，会发生什么呢？比如，把名为土豆和名为番茄的流水线，塞进那条名为番茄的流水线中，因为文字表达太麻烦，所以还是把以上过程用字母标出来：

用户输入过程可记录为：ab->b（X，Y）（T，F）

流水線对输入物件进行处理：ab->b（T，F） = F

结果是F，也就是说，将名为土豆和名为番茄的流水线输入名为番茄的流水线，结果能得到名为番茄的流水线。颇具好奇心的使用者把所有可能都试了下，他们发现：

ab->a（F，F） = F；

ab->a（F，T） = F；

ab->a（T，F） = T；

ab->a（T，T） = T；

ab->b（F，F） = F；

ab->b（F，T） = T；

ab->b（T，F） = F；

ab->b（T，T） = T。

可见，往流水线里输入流水线，可以得到其他流水线。

然而，忽然有人发现了某种新型号流水线，被标识为：

？：

ab->a（b，F）（X，Y）

虽然流水线的名字模糊到难以识别，但使用说明还能看清，这条流水线的作用是把输入的物件ab变成a（b，F），并在括号里说明可依次输入两个未知物件X和Y。比如，若输入的是白菜和胡萝卜，那么得到的结果就是“白菜（胡萝卜，F）”，可惜没有人知道“白菜（胡萝卜，F）”究竟是什么东西，或者说，该流水线输出了一件无法名状的东西。相对白菜和胡萝卜，若在这个流水线中输入名为土豆和名为番茄的流水线，结果就大不相同了：

用户输入过程可记录为：ab->a（b，F）（X，Y）（T，F）

流水线对输入物件进行处理：ab->a（b，F）（T，F） = T（F，F）

结果为T（F，F），但T（F，F）究竟是什么意思呢？因为最早的时候，曾经有过这样的说明：

T：

ab->a（X，Y）

所以，可以把“T”替换回去。T（F，F）其实就是ab->a（X，Y）（F，F），这么一来就清楚了，如果把名为土豆和名为番茄的流水线输入到该未知名字的新型流水线中，就会得到另一条流水线，而这条流水线自动就携带了输入物件，这两个输入物件是两条番茄流水线，所以不需要用户多事，该流水线自动就把它们输入到了土豆流水线中。

输入过程为：ab->a（X，Y）（F，F）

流水线对输入物件进行处理：ab->a（F，F） = F

结果为F。现在可以知道，在这个未知名字的新型流水线中输入T和F会得到F，那么其他情况呢？推断如下：

ab->a（b，F）（T，T）结果为T（T，F），T（T，F）等同于ab->a（X，Y）（T，F），ab->a（X，Y）（T，F）结果为T；

ab->a（b，F）（F，F）结果为F（F，F），F（F，F）等同于ab->b（X，Y）（F，F），ab->b（X，Y）（F，F）结果为F；

ab->a（b，F）（F，T）结果为F（T，F），F（T，F）等同于ab->b（X，Y）（T，F），ab->b（X，Y）（T，F）结果为F。

其实，在笔者的心中，土豆指的是“True”，而番茄指的是“False”，不过在这个变换系统中，符号的意义可以由使用者自己来规定。归纳可知，当依次输入两个T时，结果才是T，而其他情况都得到F，这其实恰巧相当于逻辑中的“与运算”。人们自然会想到，是否可以用流水线实现各种逻辑运算。

● 用流水线实现各种逻辑运算

常见逻辑运算的流水线标识可能是如下样子的：

AND：

ab->a（b，F）（X，Y）

OR：

ab->a（T，b）（X，Y）

XOR：

ab->a（（b（F，T）），b）（X，Y）

NOT：

a->a（F，T）（X）

之所以说“可能”，是因为到目前为止，所有的替换规则及命名都是自由设计出来的，并没有一个顶层的设计师规定了规则的具体变化要求，以及流水线名称的命名规范。

其中，与、或、非三种逻辑运算的流水线工作流程相对容易理解，这里着重解释一下XOR，XOR是异或运算，当两个输入相同，即两者同时为T或同时为F时，结果为F，当两个输入不同，即一个为T另一个为F时，结果为T。下面来验证一下：

1.输入T和T

ab->a（（b（F，T）），b）（T，T）结果为T（（T（F，T）），T）； 注解：把T和T放入流水线中

T（（T（F，T）），T）等同于ab->a（X，Y）（（T（F，T）），T）； 注解：根据名字T转换回相应功能流水线

ab->a（X，Y）（（T（F，T）），T）结果为T（F，T）； 注解：在两个输入物件中选择前者

T（F，T）等同于ab->a（X，Y）（F，T）； 注解：根据名字T转换回相应功能的流水线

ab->a（X，Y）（F，T）结果为F。 注解：在两个输入物件中选择前者

2.输入T和F

ab->a（（b（F，T）），b）（T，F）结果为T（（F（F，T）），F）； 注解：把T和F放入流水线中

T（（F（F，T）），F）等同于ab->a（X，Y）（（F（F，T）），F）； 注解：根据名字T转换回相应功能流水线

ab->a（X，Y）（（F（F，T）），F）结果为F（F，T）； 注解：在两个输入物件中选择前者

F（F，T）等同于ab->b（X，Y）（F，T）； 注解：根據名字F转换回相应功能的流水线

ab->b（X，Y）（F，T）结果为T。 注解：在两个输入物件中选择后者

数学家阿隆佐·邱奇（Alonzo Church）为了描述此种转换，设计了一种称之为“Lambda演算”的极其简约的表达式，创造这种表达式的目的之一，就是精确、简洁地描述在可计算性理论中出现的各类问题。Lambda演算表达式中规定的符号非常少，比如用“λ”代表变换，用“.”来分割变换前后的情况。如前文中提到的：

T：

ab->a（X，Y）

若以Lambda演算的方式书写，则是这样的：

T=λx.λy.x

限于篇幅，Lambda演算的具体表达式语法，就不在本文中列出来了，有兴趣的朋友可通过关键字“Lambda calculator”或“Lambda calculus Interpreter”找到可进行Lambda演算的工具。

实际上，制作一台纯Lambda演算机器，是相当简单的，因为它只要能识别转换符号“λ”，并根据符号“.”前后的规定进行符号转换，就可以进行各种计算了，而类似于“T=”这个类似赋值语句的结构，完全是为了照顾普通人的思维习惯而存在的。当今绝大部分程序语言的结构，如分支、递归，或者程序语言中必须用到的元素，如数字、字符串等，都能以Lambda演算的方式搭建出来（在一个纯粹的Lambda演算系统中，逻辑真、逻辑假、自然数、四则运算等都必须由使用者自己逐层定义出来），假设世界上所有的程序开发语言都消失了，但只要还存在一台机器能按Lambda演算规则进行符号转换，那么人们还是能够在此基础上重新构造出各种程序设计语言来。

Lambda演算背后还有着更深刻的哲学内涵：无论是逻辑上的真假，还是数学中的数字或运算，都不是真实、客观存在着的，它们本身就是一种符号变换过程，而不是变换的结果，它们的意义是在一系列相互关联的符号变换的过程中显现出来的，至少在虚拟世界中是这样。