流水線上的神奇轉換

陳凱

伽利略認為，上帝用來描述宇宙的文字是數學。這句話是否正確，還真是很難說，但可以肯定的是，當代人類用來構造虛擬世界的文字正是數學。數學家喜歡用簡潔、和諧、統一的文字來描繪他們心中的虛擬世界，只可惜，這種“簡潔、和諧、統一”的數學之美，對于未經受過數學和邏輯方面專業訓練的普通人來說，就像無法琢磨的抽象畫。然而，如果能把抽象的數學符號系統變成形象、直觀的游戲，那么數學家用一堆數字和符號所揭示的深刻道理，就能更清晰地展現在普通人，甚至是小朋友的面前。本文嘗試借助一個叫做“流水線”的文字游戲，帶領大家初窺可計算性理論大門中的景象。

● 奇妙流水線

想象有這么一座工廠，工廠中有多條生產流水線，這些流水線都是某個神奇博士設計的，人們并不知道神奇博士究竟是怎么設計出這些流水線的，不過好在不同流水線的面板上，都用標識清楚地說明了其用途，告訴人們應當在流水線的輸入口放進什么，在流水線的輸出口獲得什么。

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

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?，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演算背后還有著更深刻的哲學內涵：無論是邏輯上的真假，還是數學中的數字或運算，都不是真實、客觀存在著的，它們本身就是一種符號變換過程，而不是變換的結果，它們的意義是在一系列相互關聯的符號變換的過程中顯現出來的，至少在虛擬世界中是這樣。