陳凱

伽利略認(rèn)為，上帝用來(lái)描述宇宙的文字是數(shù)學(xué)。這句話是否正確，還真是很難說(shuō)，但可以肯定的是，當(dāng)代人類用來(lái)構(gòu)造虛擬世界的文字正是數(shù)學(xué)。數(shù)學(xué)家喜歡用簡(jiǎn)潔、和諧、統(tǒng)一的文字來(lái)描繪他們心中的虛擬世界，只可惜，這種“簡(jiǎn)潔、和諧、統(tǒng)一”的數(shù)學(xué)之美，對(duì)于未經(jīng)受過(guò)數(shù)學(xué)和邏輯方面專業(yè)訓(xùn)練的普通人來(lái)說(shuō)，就像無(wú)法琢磨的抽象畫(huà)。然而，如果能把抽象的數(shù)學(xué)符號(hào)系統(tǒng)變成形象、直觀的游戲，那么數(shù)學(xué)家用一堆數(shù)字和符號(hào)所揭示的深刻道理，就能更清晰地展現(xiàn)在普通人，甚至是小朋友的面前。本文嘗試借助一個(gè)叫做“流水線”的文字游戲，帶領(lǐng)大家初窺可計(jì)算性理論大門中的景象。

● 奇妙流水線

想象有這么一座工廠，工廠中有多條生產(chǎn)流水線，這些流水線都是某個(gè)神奇博士設(shè)計(jì)的，人們并不知道神奇博士究竟是怎么設(shè)計(jì)出這些流水線的，不過(guò)好在不同流水線的面板上，都用標(biāo)識(shí)清楚地說(shuō)明了其用途，告訴人們應(yīng)當(dāng)在流水線的輸入口放進(jìn)什么，在流水線的輸出口獲得什么。

比如說(shuō)，有一條流水線的入口處，標(biāo)了土豆和番茄，看起來(lái)是一條食品加工流水線，假如輸入的是土豆和番茄，那么最后得到的是土豆（如下圖），番茄神秘地消失了。如果輸入的是番茄和土豆，那么最后得到的是番茄，總之，依次輸入兩樣?xùn)|西，總會(huì)得到先輸入的那樣。第一次使用這條流水線的人，無(wú)不詫異，這東西到底有什么實(shí)際作用？這條流水線不能依次輸入三樣?xùn)|西，非要嘗試的話，流水線會(huì)卡住。其實(shí)，輸入三樣、四樣乃至更多樣?xùn)|西的流水線都是能設(shè)計(jì)出來(lái)使用的，神奇博士只是擔(dān)心普通使用者的腦運(yùn)算量不足會(huì)導(dǎo)致情緒崩潰，所以暫且做出了這樣的限制。接下來(lái)是個(gè)關(guān)鍵：神奇博士給這條流水線起了個(gè)名字，叫做土豆，還給流水線貼上了如下標(biāo)識(shí)：

T：

ab->a（X，Y）

這段標(biāo)識(shí)很簡(jiǎn)潔（但比數(shù)學(xué)家實(shí)際用的那些符號(hào)稍微冗長(zhǎng)一些），其意思如下：

此流水線名為土豆：

依次輸入某物a和某物b，總會(huì)得到a，括號(hào)里表示可以輸入兩個(gè)物件，使用者究竟輸入什么，是無(wú)法預(yù)知的X和Y。換句話說(shuō)，即便使用者輸入的是白菜和胡蘿卜也是可以的，結(jié)果會(huì)得到先輸入的物件，就是白菜。

神奇博士的另一條流水線的標(biāo)識(shí)是這樣的：

F：

ab->b（X，Y）

相信大家能看明白，此流水線名為番茄，依次輸入某物a和某物b，總會(huì)得到b，使用者可自由決定輸入某兩個(gè)物件。心智正常的人肯定會(huì)覺(jué)得，除了按規(guī)則吐出后一個(gè)物件、吞噬前一個(gè)物件之外，此流水線并無(wú)實(shí)際作用。

想象一下，神奇博士的車間里有一位記錄員，他會(huì)把每個(gè)使用者的動(dòng)作記錄下來(lái)，假如使用者在流水線入口依次輸入土豆和番茄，他就記錄為ab->b（X，Y）（t，f），后面的括號(hào)里是使用者實(shí)際輸入的物件，他用小寫t代表土豆，用小寫f代表番茄，若是他觀察完流水線的整個(gè)運(yùn)行，那么可能就會(huì)記錄為ab->b（X，Y）（t，f）=f。不過(guò)，后來(lái)他發(fā)現(xiàn)了一種偷懶的好辦法，因?yàn)榧热涣魉€被命名為“F”，那他只要記錄下F（t，f）=f就可以了。

神奇博士的車間有許多參觀者，大概因?yàn)楹闷嫘氖谷唬蠹叶紝⒏鞣N成對(duì)的物件放入流水線中（這莫非是神奇博士不可告人的斂財(cái)手段），直到某一天，有人忽然想到，其實(shí)可以把流水線輸入流水線。

● 把流水線輸入流水線

如果把一條流水線塞入某條流水線的入口，會(huì)發(fā)生什么呢？比如，把名為土豆和名為番茄的流水線，塞進(jìn)那條名為番茄的流水線中，因?yàn)槲淖直磉_(dá)太麻煩，所以還是把以上過(guò)程用字母標(biāo)出來(lái)：

用戶輸入過(guò)程可記錄為：ab->b（X，Y）（T，F(xiàn)）

流水線對(duì)輸入物件進(jìn)行處理：ab->b（T，F(xiàn)） = F

結(jié)果是F，也就是說(shuō)，將名為土豆和名為番茄的流水線輸入名為番茄的流水線，結(jié)果能得到名為番茄的流水線。頗具好奇心的使用者把所有可能都試了下，他們發(fā)現(xiàn)：

ab->a（F，F(xiàn)） = F；

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

ab->a（T，F(xiàn)） = T；

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

ab->b（F，F(xiàn)） = F；

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

ab->b（T，F(xiàn)） = F；

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

可見(jiàn)，往流水線里輸入流水線，可以得到其他流水線。

然而，忽然有人發(fā)現(xiàn)了某種新型號(hào)流水線，被標(biāo)識(shí)為：

？：

ab->a（b，F(xiàn)）（X，Y）

雖然流水線的名字模糊到難以識(shí)別，但使用說(shuō)明還能看清，這條流水線的作用是把輸入的物件ab變成a（b，F(xiàn)），并在括號(hào)里說(shuō)明可依次輸入兩個(gè)未知物件X和Y。比如，若輸入的是白菜和胡蘿卜，那么得到的結(jié)果就是“白菜（胡蘿卜，F(xiàn)）”，可惜沒(méi)有人知道“白菜（胡蘿卜，F(xiàn)）”究竟是什么東西，或者說(shuō)，該流水線輸出了一件無(wú)法名狀的東西。相對(duì)白菜和胡蘿卜，若在這個(gè)流水線中輸入名為土豆和名為番茄的流水線，結(jié)果就大不相同了：

用戶輸入過(guò)程可記錄為：ab->a（b，F(xiàn)）（X，Y）（T，F(xiàn)）

流水線對(duì)輸入物件進(jìn)行處理：ab->a（b，F(xiàn)）（T，F(xiàn)） = T（F，F(xiàn)）

結(jié)果為T（F，F(xiàn)），但T（F，F(xiàn)）究竟是什么意思呢？因?yàn)樽钤绲臅r(shí)候，曾經(jīng)有過(guò)這樣的說(shuō)明：

T：

ab->a（X，Y）

所以，可以把“T”替換回去。T（F，F(xiàn)）其實(shí)就是ab->a（X，Y）（F，F(xiàn)），這么一來(lái)就清楚了，如果把名為土豆和名為番茄的流水線輸入到該未知名字的新型流水線中，就會(huì)得到另一條流水線，而這條流水線自動(dòng)就攜帶了輸入物件，這兩個(gè)輸入物件是兩條番茄流水線，所以不需要用戶多事，該流水線自動(dòng)就把它們輸入到了土豆流水線中。

輸入過(guò)程為：ab->a（X，Y）（F，F(xiàn)）

流水線對(duì)輸入物件進(jìn)行處理：ab->a（F，F(xiàn)） = F

結(jié)果為F。現(xiàn)在可以知道，在這個(gè)未知名字的新型流水線中輸入T和F會(huì)得到F，那么其他情況呢？推斷如下：

ab->a（b，F(xiàn)）（T，T）結(jié)果為T（T，F(xiàn)），T（T，F(xiàn)）等同于ab->a（X，Y）（T，F(xiàn)），ab->a（X，Y）（T，F(xiàn)）結(jié)果為T；

ab->a（b，F(xiàn)）（F，F(xiàn)）結(jié)果為F（F，F(xiàn)），F(xiàn)（F，F(xiàn)）等同于ab->b（X，Y）（F，F(xiàn)），ab->b（X，Y）（F，F(xiàn)）結(jié)果為F；

ab->a（b，F(xiàn)）（F，T）結(jié)果為F（T，F(xiàn)），F(xiàn)（T，F(xiàn)）等同于ab->b（X，Y）（T，F(xiàn)），ab->b（X，Y）（T，F(xiàn)）結(jié)果為F。

其實(shí)，在筆者的心中，土豆指的是“True”，而番茄指的是“False”，不過(guò)在這個(gè)變換系統(tǒng)中，符號(hào)的意義可以由使用者自己來(lái)規(guī)定。歸納可知，當(dāng)依次輸入兩個(gè)T時(shí)，結(jié)果才是T，而其他情況都得到F，這其實(shí)恰巧相當(dāng)于邏輯中的“與運(yùn)算”。人們自然會(huì)想到，是否可以用流水線實(shí)現(xiàn)各種邏輯運(yùn)算。

● 用流水線實(shí)現(xiàn)各種邏輯運(yùn)算

常見(jiàn)邏輯運(yùn)算的流水線標(biāo)識(shí)可能是如下樣子的：

AND：

ab->a（b，F(xiàn)）（X，Y）

OR：

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

XOR：

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

NOT：

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

之所以說(shuō)“可能”，是因?yàn)榈侥壳盀橹?，所有的替換規(guī)則及命名都是自由設(shè)計(jì)出來(lái)的，并沒(méi)有一個(gè)頂層的設(shè)計(jì)師規(guī)定了規(guī)則的具體變化要求，以及流水線名稱的命名規(guī)范。

其中，與、或、非三種邏輯運(yùn)算的流水線工作流程相對(duì)容易理解，這里著重解釋一下XOR，XOR是異或運(yùn)算，當(dāng)兩個(gè)輸入相同，即兩者同時(shí)為T或同時(shí)為F時(shí)，結(jié)果為F，當(dāng)兩個(gè)輸入不同，即一個(gè)為T另一個(gè)為F時(shí)，結(jié)果為T。下面來(lái)驗(yàn)證一下：

1.輸入T和T

ab->a（（b（F，T）），b）（T，T）結(jié)果為T（（T（F，T）），T）； 注解：把T和T放入流水線中

T（（T（F，T）），T）等同于ab->a（X，Y）（（T（F，T）），T）； 注解：根據(jù)名字T轉(zhuǎn)換回相應(yīng)功能流水線

ab->a（X，Y）（（T（F，T）），T）結(jié)果為T（F，T）； 注解：在兩個(gè)輸入物件中選擇前者

T（F，T）等同于ab->a（X，Y）（F，T）； 注解：根據(jù)名字T轉(zhuǎn)換回相應(yīng)功能的流水線

ab->a（X，Y）（F，T）結(jié)果為F。 注解：在兩個(gè)輸入物件中選擇前者

2.輸入T和F

ab->a（（b（F，T）），b）（T，F(xiàn)）結(jié)果為T（（F（F，T）），F(xiàn)）； 注解：把T和F放入流水線中

T（（F（F，T）），F(xiàn)）等同于ab->a（X，Y）（（F（F，T）），F(xiàn)）； 注解：根據(jù)名字T轉(zhuǎn)換回相應(yīng)功能流水線

ab->a（X，Y）（（F（F，T）），F(xiàn)）結(jié)果為F（F，T）； 注解：在兩個(gè)輸入物件中選擇前者

F（F，T）等同于ab->b（X，Y）（F，T）； 注解：根據(jù)名字F轉(zhuǎn)換回相應(yīng)功能的流水線

ab->b（X，Y）（F，T）結(jié)果為T。 注解：在兩個(gè)輸入物件中選擇后者

數(shù)學(xué)家阿隆佐·邱奇（Alonzo Church）為了描述此種轉(zhuǎn)換，設(shè)計(jì)了一種稱之為“Lambda演算”的極其簡(jiǎn)約的表達(dá)式，創(chuàng)造這種表達(dá)式的目的之一，就是精確、簡(jiǎn)潔地描述在可計(jì)算性理論中出現(xiàn)的各類問(wèn)題。Lambda演算表達(dá)式中規(guī)定的符號(hào)非常少，比如用“λ”代表變換，用“.”來(lái)分割變換前后的情況。如前文中提到的：

T：

ab->a（X，Y）

若以Lambda演算的方式書(shū)寫，則是這樣的：

T=λx.λy.x

限于篇幅，Lambda演算的具體表達(dá)式語(yǔ)法，就不在本文中列出來(lái)了，有興趣的朋友可通過(guò)關(guān)鍵字“Lambda calculator”或“Lambda calculus Interpreter”找到可進(jìn)行Lambda演算的工具。

實(shí)際上，制作一臺(tái)純Lambda演算機(jī)器，是相當(dāng)簡(jiǎn)單的，因?yàn)樗灰茏R(shí)別轉(zhuǎn)換符號(hào)“λ”，并根據(jù)符號(hào)“.”前后的規(guī)定進(jìn)行符號(hào)轉(zhuǎn)換，就可以進(jìn)行各種計(jì)算了，而類似于“T=”這個(gè)類似賦值語(yǔ)句的結(jié)構(gòu)，完全是為了照顧普通人的思維習(xí)慣而存在的。當(dāng)今絕大部分程序語(yǔ)言的結(jié)構(gòu)，如分支、遞歸，或者程序語(yǔ)言中必須用到的元素，如數(shù)字、字符串等，都能以Lambda演算的方式搭建出來(lái)（在一個(gè)純粹的Lambda演算系統(tǒng)中，邏輯真、邏輯假、自然數(shù)、四則運(yùn)算等都必須由使用者自己逐層定義出來(lái)），假設(shè)世界上所有的程序開(kāi)發(fā)語(yǔ)言都消失了，但只要還存在一臺(tái)機(jī)器能按Lambda演算規(guī)則進(jìn)行符號(hào)轉(zhuǎn)換，那么人們還是能夠在此基礎(chǔ)上重新構(gòu)造出各種程序設(shè)計(jì)語(yǔ)言來(lái)。

Lambda演算背后還有著更深刻的哲學(xué)內(nèi)涵：無(wú)論是邏輯上的真假，還是數(shù)學(xué)中的數(shù)字或運(yùn)算，都不是真實(shí)、客觀存在著的，它們本身就是一種符號(hào)變換過(guò)程，而不是變換的結(jié)果，它們的意義是在一系列相互關(guān)聯(lián)的符號(hào)變換的過(guò)程中顯現(xiàn)出來(lái)的，至少在虛擬世界中是這樣。