可計算數是可枚舉的
不止被包含一次，而是至少兩次。 這種方法帶來的好處很有意思。想想一臺計算π的圖靈機。正常情況下，我們用一個無窮序列來表示π的數位： 3.1415926535897932384626433832795...現在，我們可以使用一個有限的整數來表示π，這個整數就是計算π的數位的圖靈機的描述數。哪種π的表示更好呢？是前32個數位再跟上省略號？還是有多長耐心就能生成多少位數字的圖靈機描述數？在某種意義上，描述數是π的一種更基本的數字表示方式，因為它描述了計算這個數的算法。 事實上，把每臺機器歸納為一個數，圖靈已經使僅通過枚舉正整數便產生機器變為可能了。不是每一個正整數都是一個有效的圖靈機描述數，而且很多有效的描述數也不能描述非循環機，但這種枚舉必然包含了所有的非循環圖靈機，其中每臺這樣的機器都對應著一個可計算數。因此，可計算數是可枚舉的。 這是一個很重要的發現，儘管它也可能是令人不安的，因為它意味著，大部分的——或者根據我們已有的關於實數範圍的知識，幾乎全部的——實數都不是可計算的。 這個出乎意料的發現，連同一些數學悖論和量子引力的研究，促使數學家格雷戈裡·蔡廷提出疑問：“實數究竟有多真實？”能證明實數確實存在的證據的確很少。
分享到:
閱讀更多 江南綠水青山 的文章
