陳凱

在基礎(chǔ)教育階段的信息技術(shù)教材中，如果是回顧計(jì)算機(jī)發(fā)展歷程的章節(jié)，常會(huì)提到圖靈和他的圖靈機(jī)，教材編寫者通常會(huì)強(qiáng)調(diào)圖靈機(jī)的重要意義，但對(duì)圖靈機(jī)本身的描述卻不多，涉及文字也很少，恐怕最多只能讓人知道一個(gè)人的名字再加上一種機(jī)器的名稱，更何況圖靈在論文中提到的圖靈機(jī)是一個(gè)理論上的模型，他沒(méi)有親自把圖靈機(jī)造出來(lái)（對(duì)于他的論文來(lái)說(shuō)，也沒(méi)有真正制作出來(lái)的必要）。而現(xiàn)在，人們也并不真正需要按圖靈構(gòu)想的原樣實(shí)現(xiàn)一臺(tái)圖靈機(jī)來(lái)當(dāng)作計(jì)算工具使用，一個(gè)沒(méi)有實(shí)物對(duì)應(yīng)的抽象模型，是比較難讓普通初學(xué)者產(chǎn)生深入探索的興趣的，也就更難讓初學(xué)者自發(fā)產(chǎn)生動(dòng)力，去思考為什么圖靈機(jī)對(duì)于后來(lái)通用的電子計(jì)算機(jī)發(fā)展有著非常重要的意義。

如果只有40分鐘的課時(shí)來(lái)介紹一下圖靈機(jī)，那么應(yīng)該怎樣充分利用好這短暫的時(shí)間呢？其實(shí)只要40分鐘，就可以將一臺(tái)圖靈機(jī)的搭建過(guò)程大致演示出來(lái)。這里講的并不是用程序來(lái)模擬圖靈機(jī)，而是怎樣用基礎(chǔ)的電子元件來(lái)搭建一臺(tái)圖靈機(jī)，因?yàn)椋?dāng)前絕大部分程序設(shè)計(jì)語(yǔ)言都與圖靈等價(jià)，用程序語(yǔ)言來(lái)模擬圖靈機(jī)，就體現(xiàn)不出“造”的過(guò)程。為了使圖靈機(jī)的工作過(guò)程更生動(dòng)直觀地展現(xiàn)出來(lái)，筆者“請(qǐng)”來(lái)一群變色龍來(lái)做游戲，游戲過(guò)程實(shí)際上就對(duì)應(yīng)著圖靈機(jī)的一般工作過(guò)程。

● 一只大變色龍和一只小變色龍的相遇（10分鐘）

想象一個(gè)有趣的場(chǎng)景，假設(shè)大變色龍A可變兩種顏色——綠色和黃色，小變色龍B也可變兩種顏色——綠色和黃色（如圖1）。當(dāng)變色龍A遇到變色龍B時(shí)，則總共可能出現(xiàn)四種情況：綠色—綠色；綠色—黃色；黃色—綠色；黃色—黃色。

現(xiàn)實(shí)中變色龍的變色能力很強(qiáng)，還能變出其他顏色來(lái)，不過(guò)這里為了簡(jiǎn)化問(wèn)題描述，就假設(shè)它們只能變兩種顏色。

既然變色龍具有變色的能力，那么，當(dāng)兩只變色龍相遇后，它們各自的顏色有可能會(huì)變，也有可能不變。假如有一個(gè)能力強(qiáng)大的變色龍馴獸師，能夠讓兩只變色龍相遇后，按馴獸師預(yù)先設(shè)置的規(guī)則來(lái)改變，或不改變顏色。例如，對(duì)于大變色龍A，它從馴獸師那里得到的命令是這樣的：如果自己（A）是綠色，對(duì)方B也是綠色，那么，下一時(shí)刻就仍然是綠色，考慮相遇后存在四種不同的情況，很容易理解表1中的規(guī)則。

至于小變色龍B，它從馴獸師那里得到的命令如表2所示。

至于為什么要按這樣的規(guī)律來(lái)變色，先暫且看成是馴獸師的個(gè)人喜好，實(shí)際上，馴獸師制訂其他規(guī)則也是可以的。

想象一下，綠色A遇見(jiàn)綠色B，變化之后，下一時(shí)刻A自己不變，而B變了，于是就變成了綠色A和黃色B，如果這兩只變色龍還要繼續(xù)玩“瞪一眼再變色”的游戲，那再下一時(shí)刻就變成了黃A和黃B，再下一時(shí)刻變成黃A和綠B，再下一時(shí)刻變?yōu)辄SA和黃B，之后它們就總在最后兩種狀態(tài)中來(lái)回切換，似乎可以用來(lái)當(dāng)作開(kāi)派對(duì)時(shí)的絢彩LED了（如圖2）。

● 一只大變色龍和一群小變色龍的相遇（10分鐘）

假設(shè)大變色龍A遭遇的是一大群小變色龍B1、B2、B3等，除了相互瞪眼、變色之外，大變色龍還會(huì)在變色后改變自己瞪眼的對(duì)象，考慮到變色龍通常行動(dòng)緩慢，大變色龍A只是移動(dòng)了一個(gè)身位，要么向左移，要么向右移，假設(shè)移動(dòng)的方向也受到了馴獸師的控制，規(guī)則如表3所示。

可以將大變色龍A的變化、小變色龍B的變化以及大變色龍A變色完成后的移動(dòng)用一張表格來(lái)表示（如下頁(yè)表4）。

可以看到，兩只變色龍相遇后，就按順序發(fā)生這三個(gè)事件，并且整套動(dòng)作完成后，又開(kāi)始新的瞪眼、變色、移位的過(guò)程。下面舉例說(shuō)明變色龍相互間變化的四個(gè)時(shí)刻的狀態(tài)，就好像是四格漫畫（如圖3）。

變化過(guò)程當(dāng)然沒(méi)有結(jié)束，如果小變色龍B的數(shù)量足夠多的話，那么大變色龍A就會(huì)在小變色龍的序列中來(lái)回穿梭，忙著改變自己和對(duì)方的顏色，狀態(tài)變化是相當(dāng)復(fù)雜的。其實(shí)，如果世界上真的有這種被馴化的變色龍，人們就可以拿這些變色龍的復(fù)雜變化當(dāng)成某種計(jì)算工具來(lái)使用，這些變色龍展現(xiàn)出來(lái)的，正是某種簡(jiǎn)單的圖靈機(jī)的工作過(guò)程。

● 瞪眼、變色和位移的邏輯電路（10分鐘）

1.從瞪眼到改變大變色龍顏色的電路

通過(guò)以下方法，就可以把變色龍的變化用電子元件制造出來(lái)。將大變色龍的變色規(guī)則即“A的下一時(shí)刻”這一列轉(zhuǎn)化成二進(jìn)制，綠是0，黃是1，得到“0111”，然后輸入網(wǎng)址http：//www.32x8.com/var2.html，這個(gè)網(wǎng)頁(yè)提供了便捷的功能，可以把二進(jìn)制真值表轉(zhuǎn)化成邏輯電路圖，只需要在交互表單中，由上至下選中“0111”，按“Submit”，則自動(dòng)得到邏輯電路圖（如下頁(yè)圖4）。

這簡(jiǎn)直太方便了，圖4表示取A和B的或運(yùn)算的值，按本文的例子，就是將大變色龍和小變色龍的狀態(tài)進(jìn)行或運(yùn)算?？紤]到大變色龍的顏色非黃即綠，所以可使用一位寄存器來(lái)存儲(chǔ)大變色龍A的狀態(tài)，在Logisim軟件中，圖5表示的就是一位寄存器。

考慮到小變色龍有很多，為調(diào)試方便，可使用含有16個(gè)存儲(chǔ)空間的一位存儲(chǔ)器，Logisim中，圖6表示的就是存儲(chǔ)器。存儲(chǔ)器的使用方法在往期文章里有過(guò)解釋，這里就略過(guò)了。綜合以后，就可以在Logisim中畫出邏輯電路圖，這一步?jīng)]有那么自動(dòng)化，不過(guò)繪制線路還是非常簡(jiǎn)單的（如圖7）。

2.從瞪眼到改變小變色龍顏色的電路

將小變色龍的變色規(guī)則即“B的下一時(shí)刻”這一列轉(zhuǎn)化成二進(jìn)制，綠是0，黃是1，得到“1110”，輸入網(wǎng)址“http：//www.32x8.com/var2.html”，在交互表單中由上至下選中“1110”，按“Submit”，自動(dòng)得到邏輯電路圖8。

此圖表示取A反和B反的或運(yùn)算值，所以要在進(jìn)行或運(yùn)算前先各自做非運(yùn)算，由于這次改變的是小變色龍B的值，所以改變的是存儲(chǔ)器的值而不是寄存器的值，在Logisim中畫出小變色龍變色的電路圖（如第29頁(yè)圖9）。

3.改變顏色后發(fā)生位移的電路

將“A變色后的動(dòng)作”這一列轉(zhuǎn)化成二進(jìn)制，左是0，右是1，得到“1101”，輸入網(wǎng)址“http：//www.32x8.com/var2.html”，在交互表單中由上至下選中“1101”，按“Submit”，自動(dòng)得到邏輯電路圖（如第29頁(yè)圖10）。

此圖表示取A反和B的或運(yùn)算值。由于這次改變的是位移方向，所以邏輯門的輸出結(jié)果影響的是控制存儲(chǔ)器讀寫方向的計(jì)數(shù)器，第29頁(yè)圖11表示的就是計(jì)數(shù)器，在Logisim軟件中畫出電路圖（如第29頁(yè)圖12）。

計(jì)數(shù)器前端加上一個(gè)非門，是為了照顧人們從左到右讀取數(shù)字的習(xí)慣，如不加，則存儲(chǔ)器中的數(shù)據(jù)需要從右往左讀。

● “造”出一臺(tái)圖靈機(jī)（10分鐘）

有了上面三張邏輯電路圖，就可以“造”出一臺(tái)圖靈機(jī)了，可是怎么使用這三張圖呢？在畫圖軟件里設(shè)置好“透明選擇”，然后把三張圖重疊在一起就可以得到完整的圖靈機(jī)的邏輯電路圖了。接下來(lái)，使用邏輯電路模擬軟件Logisim把元件按電路圖的樣子連接好，就可以運(yùn)行這臺(tái)圖靈機(jī)了！真正運(yùn)行后可以發(fā)現(xiàn)，數(shù)據(jù)的變化規(guī)律有點(diǎn)讓人意想不到。注意寄存器里的數(shù)值代表的是大變色龍A的顏色，而存儲(chǔ)器里的數(shù)值代表的是小變色龍B的顏色。當(dāng)然也可以用電子元件將電路實(shí)際搭出來(lái)，可以當(dāng)作創(chuàng)客的項(xiàng)目。

本文所實(shí)現(xiàn)的還只是一臺(tái)專用圖靈機(jī)，若要實(shí)現(xiàn)通用圖靈機(jī)，就需要擴(kuò)展寄存器的數(shù)量或存儲(chǔ)器的存儲(chǔ)數(shù)據(jù)位數(shù)，還要改變進(jìn)行顏色變化的邏輯電路，實(shí)現(xiàn)起來(lái)要復(fù)雜多了，這個(gè)難題就留給有興趣的朋友自行探索吧——雖然說(shuō)筆者并沒(méi)有抱太大期望，不過(guò)或許哪天就能得到一份意外的驚喜喲！