問題總比辦法多——淺說不可解性

圖靈曾構造自指的辦法證明有圖靈機無力判定的問題，但這個結果常被誤解成是嚴格遵循邏輯的圖靈機固有的缺陷。實際上，這既不是純粹事關邏輯或自指悖論的問題，也不是只針對圖靈機的事。

很容易用完全不涉及自指的方法證明：存在著無窮多除都是圖靈機不可解外，幾無共通點的問題——根據「有效輸出的圖靈機只有可數無窮多個」，只要利用像（0,1）上的全體實數這樣不可數無窮的集合來生成遠多於圖靈機的不同問題，那麼其中絕大多數必然是不可解的。比如，判定問題可以這樣搞：輸入整數N，判斷某實數P的二進位小數第N位是否為1.

類似的，把圖靈機換成是由有限符號組成的其他對象也是成立的。例如，有不能用解析式表達的實函數。例如，三體運動方程沒有解析解存在，這可能令人懊惱，但絕不該是一件令人震驚不已的事。進一步地，就算它連精度充分的數值解都不存在，也是完全可能發生的事情。因為給定精度下的數值計算程序，和「圖靈機」或「解析式」其實是同類。

由此可見，邏輯自指只是構造範例的一種方法，它不是產生不可解現象的前提，所以也不能認為人腦可以用繞開自指悖論的辦法來迴避該現象。賦予圖靈機猜測的功能/提供隨機源甚至連自指性都克服不了，這隻需將停機定理原證明中的「唱反調」環節改成「重複模擬原判定機5次，執行出現次數最少的判定結果」就行了，這導致構造出的圖靈機無法被以大於1/2的正確率判定是否會停機。注意純粹地讓隨機源（如投硬幣）瞎猜也能提供1/2正確率，可見計算機和隨機性在停機問題上的合作毫無建樹。人具有靈感和直覺，可能不循規蹈矩而自由行動，但沒有證據表明我們比機器更擅長利用隨機性。

而且，這個現象甚至不關「停機」這個行為的事，停機問題這個命名容易讓人誤以為「停機」操作有什麼特別的，但其實幾乎所有的圖靈機行為都可以被替換到停機定理的原證明中，故自指悖論表示的實是圖靈機不能判斷同類的一般行為特徵（你甚至可以覺得：產生了人工智慧的圖靈機會認為彼此是有自由意志的），準確完整體現它的是Rice定理。

一切只依賴於功能的圖靈機性質都是不可判定的，除非該性質對全體圖靈機都成立或都不成立。

例如，「程序是否輸出偶數」就在與停機問題相同的意義上是不可判定的。你也許會問：我將它運行完不就知道了嗎？但這個程序如果以一種微妙的方式不會停呢？例如，此程序不斷搜索哥德巴赫猜想的反例（此功能容易實現），找到時停機並輸出2，否則一直運行。任何想要正確判定的人就必須推出原猜想的正誤了。

正因如此，如果Rice定理被更多人認識到，停機問題和演算法不可解性就不會被高估到具有用於探討自由意志問題的潛力了。「一個程序是不是計算機病毒」都有相當於停機問題的不可判定性，但不可判定的問題可以具有易解常見的特例，沒有自由意志的殺毒軟體在運用這點上得心應手。

至於具有自由意志的人類，在不可判定的問題上的經驗表現是因情況而異的。例如，主張人腦強於計算機的一派會舉例人善於看出程序的死循環。相比之下，「兩個程序輸出是否相同」也是一個不可判定問題，但人腦可不見得善於解決該問題。不然的話，程序員用過別人的軟體，按自己思路就能不出BUG地寫出實現相同功能的代碼，無需調試，這有人信么？