管中窺豹——計算中的局域信號傳遞

陳凱 上海市位育中學(xué)

《世說新語》中有這樣一個故事：王羲之的幾個門生在玩棋，王羲之只有幾歲的兒子王獻之在一旁觀看，說其中一方將要輸了。門生覺得那么小年齡的孩子，恐怕只是懂那么一點點就亂說話，于是有點嘲笑地評價說：“管中窺豹，時見一斑。”王獻之有沒有說準呢？大概是說準了吧，不過，故事里只是提到了王獻之頗為不高興地回應(yīng)：“遠慚荀奉倩，近愧劉真長?！薄肮苤懈Q豹”是一個常用的成語，不過其具體的運用別有一番奧妙：當人們只說“管中窺豹”的時候，通常是指難以從局部現(xiàn)象了解全局，而當人們說“管中窺豹，可見一斑”的時候，卻往往是想說，即便從局部現(xiàn)象中也能了解到全局的狀況。這種看似矛盾的用法體現(xiàn)了語言文化的復(fù)雜性。在一個復(fù)雜的計算系統(tǒng)中，也常能發(fā)現(xiàn)類似“管中窺豹”的現(xiàn)象，可以將“斑”視作局部的計算現(xiàn)象，而“豹”則是整體的計算現(xiàn)象，有時可由局部了解全局，有時卻不能。利用局部的計算現(xiàn)象達成全局的計算目標，是構(gòu)造計算模型的一種重要思維方式。

●管窺之斑或可見豹

假設(shè)一個列表中存儲有若干數(shù)字，要求找出其中最大的數(shù)字并將其移至列表最后，可以采用怎樣的方法呢？方法很多，不妨將這個列表想象成一個長條的存儲槽，而數(shù)字是槽上大小不一的盒子，有一只機械手臂可以同時觀察兩個盒子的狀況并針對這兩個盒子做出某種動作，那么，當某人觀察到這只機械手臂從槽左側(cè)開始向右移動，并同時實施將兩個盒子中更大的那個交換到另一個盒子右側(cè)這樣的行為時，就能判定，當機械手臂移至槽右側(cè)末端時，那里最終一定會擺放下槽中最大的盒子。擴展想象一下，如果機械手臂可以同時觀察三個盒子的情況，并能將其中最大的盒子交換到另兩個盒子的最右側(cè)，那么可以推斷，這個裝置整體的作用和剛才的裝置類似，也能夠在存儲槽中找出最大的盒子并放置到整個槽右側(cè)末端。一個使用列表的演示程序代碼及運行結(jié)果如圖1所示。在這個例子中，局部的功能和全局的功能是一致的，所以比較容易借助局部變化的現(xiàn)象推演出整體變化的情況，用管窺之豹來比喻的話，局部的最大數(shù)的交換是斑，整體的最大數(shù)的交換是豹。

圖1 一種將最大數(shù)交換到最右側(cè)的方法

在簡單的邏輯運算中，也能發(fā)現(xiàn)“管中窺豹，可見一斑”的例子，如三個人投票，規(guī)則是一票否決，這時候可以用與的邏輯運算來獲知投票結(jié)果。如果擴展到十個人或更多人投票，那么全局的與運算的結(jié)果還是很容易判斷出來的：只要有一張否決票，那么整個表決都不會通過，在與的邏輯運算中，局部與整體的計算現(xiàn)象是一致的。

●管窺之斑或難見豹

接下來看一個稍微復(fù)雜一些的例子，某存儲槽中有很多黑色盒子和白色盒子隨機相間排列。但在存儲槽的左側(cè)最前端放著一個特殊的盒子，它向前正面是黑色的，向后反面是白色的。機械手臂總是實施將此兩色盒子和其右側(cè)盒子交換的動作，如果其右側(cè)盒子是黑色的，則交換的同時還要將此兩色盒子正反顛倒，如果其右側(cè)盒子是白色的，則只是交換位置而不對兩色盒子實施正反顛倒的動作。那么，當這只機械手臂順槽移動到最右側(cè)末端時，這個兩色盒子到底是黑色還是白色，則提示著存儲槽中的黑色盒子數(shù)量是奇數(shù)還是偶數(shù)。一個演示程序代碼及運行結(jié)果如圖2所示。代碼中用“b”和“w”代表黑色和白色的盒子，用“-1”和“1”代表兩色盒子的黑色正面和白色反面。在這個例子中，局部的行為是交換盒子并判斷及實施兩色盒正反顛倒的動作，但在系統(tǒng)運行的整體上，卻實現(xiàn)了奇偶判斷的任務(wù)。局部動作雖然和整體任務(wù)有密切的關(guān)系，但在行為表現(xiàn)上是不一致的。

圖2 一種奇偶判斷的方法

將以上任務(wù)再做修改，假設(shè)機械手臂總是處于存儲槽左側(cè)開端處，而存儲槽的傳送帶會將其余右側(cè)的若干盒子向左移動靠攏，當機械手臂觀察到兩色盒與黑盒左右排列的狀態(tài)時，就扔掉黑盒，同時將兩色盒翻面，當機械臂觀察到白色反面向前的兩色盒與白盒左右排列的狀態(tài)時，就扔掉白盒，否則就不做任何事。這樣一個局部的規(guī)則，到底可以用來實現(xiàn)怎樣的整體功能呢？這個問題的推理要比剛才的例子費勁得多，雖然管窺見斑，但豹的整體的樣子就更難想象了。大家不妨直接看如圖3所示的程序代碼的演示。跟蹤運行過程可知，在程序初始列表中，“b”的數(shù)量代表將要被判斷奇偶的數(shù)字，“w”是標志符，如程序運行最后所有的“w”都消失了，則說明被判斷的所有數(shù)字都是奇數(shù)，否則，就說明連續(xù)擺放的“b”盒子用來表示的數(shù)量中，至少有一個偶數(shù)。在這個例子中，局部發(fā)生變化的位置只有一處，想象一下，若列表中多處位置都在按規(guī)則發(fā)生局部的變化，那么整體的變化現(xiàn)象就更難以揣摩了。

在邏輯運算中也有類似的例子，如果對多個數(shù)字做一種叫做與非的運算（對兩個邏輯值的與運算的結(jié)果取反），哪怕這個局部變化規(guī)則非常簡單，也還是不能根據(jù)這個局部變化現(xiàn)象直觀地推演出全局的變化現(xiàn)象，下頁圖4所示的是對8個邏輯值進行邏輯運算的程序代碼。如果是進行與的邏輯運算，那么很容易推測出整體的結(jié)果，如果是與非的邏輯運算，那就只有一步一步地計算才能得出全局的結(jié)果。所以說，有時通過管窺之斑是很難見到豹的。

圖4 對多個數(shù)值進行邏輯運算，對全局的與非運算結(jié)果的判斷遠遠難于與運算

●斑豹之變

在一個計算模型中，斑和豹的地位是會發(fā)生變化的，以冒泡排序算法為例，對于長度為x的數(shù)列，數(shù)列中兩兩數(shù)字比對交換是斑，數(shù)列中最大數(shù)放置到最右側(cè)的現(xiàn)象是豹。同時，也可以將第n次在長度x-n+1的數(shù)列中實現(xiàn)最大數(shù)放置到最右側(cè)的這一現(xiàn)象視作斑，而長度為x的數(shù)列最終實現(xiàn)排序的這一現(xiàn)象視作豹。

哪怕局部的規(guī)則很簡單，若一個系統(tǒng)中多個局部都并發(fā)地應(yīng)用規(guī)則，整體上就有可能產(chǎn)生出混沌的現(xiàn)象，單憑人腦的能力，是難以把握局部規(guī)則運用于全局后的變化狀態(tài)的，但對于某些特定的數(shù)據(jù)集合，局部規(guī)則的并發(fā)應(yīng)用，也能呈現(xiàn)出全局層面在混沌變化的同時涌現(xiàn)出部分有規(guī)則變化的現(xiàn)象。用語言描述這種現(xiàn)象是十分困難的，借助元胞自動機的例子更容易說明這種現(xiàn)象。WireWorld是一種正方形網(wǎng)格元胞自動機，它的運行規(guī)則是：每個格子允許有四種顏色，在每個變化的時刻，黑色總是保持黑色，紅色總是變成藍色，藍色總是變成黃色，黃色保持黃色的狀態(tài)，但只要黃色的格子周圍的八個格子里有一個或兩個紅色，黃色就變成紅色。雖然局部規(guī)律不難理解，但對于稍微復(fù)雜一些的Wireworld圖樣，絕大部分人如果只用頭腦推理和想象是很難判斷出運行結(jié)果的。這種針對全局狀態(tài)預(yù)測的困難，也是復(fù)雜系統(tǒng)的一個特征。例如，下頁圖5所示的圖案A在若干步變化后陸續(xù)出現(xiàn)B、C、D等圖案變化的現(xiàn)象，不得不用計算機才能逐步模擬出全局的圖樣變化狀況。

但令人驚訝的是，雖然圖5所示的系統(tǒng)在運作過程中是混沌的，可它的初始時刻（如圖A所示的時刻）的信號狀態(tài)和若干時刻后（如圖D所示的時刻）的信號狀態(tài)，這兩者間是存在明確的規(guī)律的。這里勉強比喻一下，在局部范圍內(nèi)可以看出有規(guī)律的“斑”，但很多“斑”組合在一起，大多數(shù)情況下是一片混沌，只有某些特別的“斑”偶爾以某種特別的方式組合起來后，能顯現(xiàn)出某種“豹”的樣子。如圖5所示的圖樣，它的行為很像一個能進行與邏輯運算的裝置。一旦有了這樣的領(lǐng)悟，就能夠?qū)⑦@個特殊組合的“豹”當作為了組合出更大規(guī)模的“豹”的“斑”來使用了。下頁圖6是利用Wireworld元胞自動機實現(xiàn)奇偶校驗的例子，如果說整體的奇偶校驗任務(wù)是豹，那么這個系統(tǒng)中重要的組成部分就是如圖5所示的圖樣的變化狀態(tài)，就成為整體的豹的斑（注意，這里的斑不是圖樣而是圖樣的變化）。本文在這里只是試圖說明這種現(xiàn)象的存在，但除非讀者親自運行并觀察這個系統(tǒng)的運作過程，只依靠閱讀這里的文字描述，是很難明白這些圖樣變化是如何實現(xiàn)奇偶校驗的功能的。

圖5 難以從局部變化推演全局變化的Wireworld元胞自動機圖樣

圖6 可實現(xiàn)奇偶校驗的Wireworld元胞自動機圖樣

系統(tǒng)科學(xué)對此現(xiàn)象是這樣描述的：局域耦合可以產(chǎn)生出信號傳遞的現(xiàn)象，使得整體系統(tǒng)在不具備中心控制能力的情況下，在宏觀的尺度涌現(xiàn)出動力學(xué)行為。不過對于復(fù)雜系統(tǒng)，系統(tǒng)科學(xué)的研究目標主要是結(jié)構(gòu)和功能的關(guān)系以及系統(tǒng)演化的規(guī)律，而計算機科學(xué)在于如何利用這種演化規(guī)律，或者是如何為創(chuàng)設(shè)出一種具有實用價值的演化規(guī)律來設(shè)計特定的結(jié)構(gòu)。

●“用斑繪豹”的教學(xué)設(shè)計

從上述較為艱深和抽象的討論回歸到日常教學(xué)，這里介紹一個可以在教學(xué)中引發(fā)討論的有趣問題：假設(shè)有一個長長的存儲槽，槽內(nèi)排列大小不一的盒子，槽的左側(cè)末端是某A，槽的右側(cè)末端是某B。某只機械手臂在槽的側(cè)面左右來回隨機游走，機械手臂會觀察槽內(nèi)盒子，它每次檢查三個盒子，然后將最大的盒子取出，放置在另兩個盒子的右面，假如遇見的三個盒子都是一樣的，則不做任何事繼續(xù)隨機游走。例如，機械手臂看到的是“635”，就將“6”交換到另兩個數(shù)最右側(cè)，成為“356”?？梢詫⑦@個情況以某種編碼展現(xiàn)出來：

容易猜出，編碼中數(shù)字代表不同大小的盒子，數(shù)字越大盒子越大，R是機械手臂?，F(xiàn)在，某A要和某B通過在紙盒子上寫字的方式來傳輸信息，但某A和某B不能離開自己的位置，為了實現(xiàn)通信的需求，某A和某B使用了一種充氣變?yōu)?、放氣變?yōu)?的變化盒，在通信時可將變化盒放置在自己身邊的槽末端（為避免復(fù)雜性，變化盒傳達到對方閱后即毀），這里要問的是：為了實現(xiàn)相互通信，在A和B的身邊，需要準備多少變化盒？

①A和B各需要1個變化盒給對方發(fā)消息；

②A和B各需要2個變化盒給對方發(fā)消息；

③A需要2個變化盒能發(fā)出消息給B，B需要1個變化盒能發(fā)出消息；

④A需要1個變化盒能發(fā)出消息給B，B需要2個變化盒能發(fā)出消息。

問題描述的盒子位置在變化過程中，很清晰地體現(xiàn)出局域耦合所產(chǎn)生的信號傳遞現(xiàn)象，而且，系統(tǒng)整體的功能依賴于規(guī)則引發(fā)的局部變化，但整體的功能又和局部行為不相一致，希望讀者在領(lǐng)悟到這一點后，能進一步嘗試用局部的“斑”來建構(gòu)出整體的“豹”，解決更復(fù)雜一些的問題。