怎樣動手“造”一臺圖靈機

陳凱

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

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

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

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

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

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

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

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

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

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

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

可以將大變色龍A的變化、小變色龍B的變化以及大變色龍A變色完成后的移動用一張表格來表示（如下頁表4）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

● “造”出一臺圖靈機（10分鐘）

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

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