元宵燈謎猜一物

筆行紙帶照章移，計數無遺信可期。
算盡人間無限事，何時停歇未能知。

嚴格來說是猜一個數學模型啦😝詩這種講究精煉且重視餘韻的語言，有辦法描述數學嗎？數學，似乎是種與詩完全對立的語言。數學重視的是嚴謹與精確。嚴謹，所以不太能預期在篇幅有限的精鍊文字中描述完整；精確，所以話要說完整，不能給讀者自行詮釋的想像空間。但，這只是種直觀的想法。是不是詩注定不可能描述數學呢？恐怕倒也未必。話說回來，我自己是做不到就是了啦😆我可不認為開頭四句詩精確嚴謹的描述了圖靈機。當成遊戲之作倒是挺有意思的。

雖然解釋自己的作品是件有點蠢的行為，但還是來看看這四句詩說了什麼吧：

1. 圖靈機是由以下這些東西構成：紙帶、讀寫頭、還有許多「狀態」、以及規定當圖靈機在某個狀態，且讀寫頭讀到某個符號時，下一步要變成什麼狀態，讀寫頭要往哪邊移動的「轉移函數」。於是，我們能想像到圖靈機的畫面，便是讀寫頭根據轉移函數在紙帶上移動的模樣。
2. 圖靈機是種理想的數學模型，一旦我們把他的描述，也就是剛才說的「紙帶、讀寫頭、狀態、轉移函數」，決定好，他就會完全依照這描述來運作不會出錯。只要我們能證明這樣的描述能計算出我們要的結果，那麼圖靈機就會給我們正確的計算結果。可說是「計數無遺信可期」了。
   「計數無遺」還可以這樣理解：圖靈機有能力「數數」。考慮這樣的問題：「請判斷一個由 0 與 1 形成的字串，是否為一串 1 後面接了一串相同長度的 0 。例如說，輸入 111000 或 11110000 時要回答是；輸入 111110 或 11100000 時要回答否。」要回答這個問題，可以想成是要數 1 的數量與 0 的數量是不是一樣多。圖靈機可以正確判斷這樣的問題，但更弱的計算模型，例如有限狀態自動機，則沒有辦法。
   此外，我們可以更進一步。如果我們相信邱奇–圖靈的猜想（ Church-Turing thesis ，中文通常翻譯成邱奇–圖靈論題，但我覺得聽起來文謅謅的。翻成猜想應該可以接受。），那麼任何一個可以被某種計算模型算出來的問題，圖靈機都算得出來。也就是說圖靈機確實是「計數無遺」。
3. 一台圖靈機是由「紙帶、讀寫頭、狀態、轉移函數」來描述。而「紙帶、讀寫頭、狀態、轉移函數」這樣的描述把他寫下來，總共有可數無限多種。也就是說總共有可數無限多種圖靈機。一台圖靈機可以回答一個計算問題，所以，可數無限多種圖靈機可以回答可數無限多種計算問題。真的是數學上嚴格意義的「算盡人間無限事」了。
4. 可是啊，計算問題總共有不可數無限多種。也就是說，存在計算問題是圖靈機無法回答的。例如說：鼎鼎大名的「停機問題」。我們無法設計出一台圖靈機，使得這台圖靈機能夠判斷任何一台圖靈機開始運作之後是否會停下來。

我自己覺得，「算盡人間無限事，何時停歇未能知。」有種算命師算不出自己命運的感覺。但這是個錯誤的類比。這就是詩中不精確的地方了。

停機問題的定理陳述並不是說，一台圖靈機無法回答自己是否會停下來。停機問題的問題本身是：「輸入一台圖靈機的描述，請回答這台圖靈機是否會停下來——要嘛回答是，要嘛回答否。我們並沒有對輸入的圖靈機做限制，不論輸入的是任何一台圖靈機的描述，都要回答正確。」而對於停機問題，我們能得到的結論是：不存在圖靈機可以正確回答這個問題。所以呀，算命師這個帶有些許寓意的類比，並沒有真正捕捉到停機問題的核心。

聊完數學，回到燈謎。我想到了紅樓夢中，主角群作的燈謎，都暗示了自身的命運。照著這個設定，看來作出這首圖靈機燈謎的人，是要一生勞碌命了！

主題標籤： 古典詩詞 計算理論 無限大 數學雜文