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

陳凱

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.改變顏色后發生位移的電路

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

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

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

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

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

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