當前位置: 華文問答 > 數位

電腦能不能真正意義上儲存一個無理數?

2020-01-17數位

我們先定義一下儲存。以下我們認為,成功儲存一個數意味著,可以在有限時間內計算出這個數的任何一位。

為什麽這樣定義呢?因為單就儲存而言,方式太多了。我儲存一張畫著π的像素畫,也是一種儲存。但這沒有意義,不是我們想要的。因為π的像素畫是不能進行計算的。我們希望儲存的數能夠參與運算,那至少我該知道它的每一位是什麽。

但不要局限在儲存每一位,那樣顯然是無法儲存無理數的,在現實條件下甚至一些很大的數都無法儲存,比如葛立恒數、tree(3)之類的。

而如果我們儲存「計算這個數的方法」,就可以表達出很多數。比如對於π和e,我們儲存一個逼近它的公式即可。

但我們仍然不能儲存所有實數。

顯然 不可計算數 是不能儲存的,因為不可計算數的定義就是「不能透過一個圖靈機在 有限 的通用演算法來得到這個實數的任意想要的一位數位」。也就是說即便我儲存了計算這個數的方法,我也算不出來它,不滿足我上面提到的儲存的要求。我想問題中提到的電腦應當確實是圖靈機。

關於不可計算數, 蔡廷常數 是一個很經典的例子。粗略地解釋一下就是:指定一種圖靈完備的程式語言,隨機輸入一段程式碼,這段程式碼可執行且會在有限時間裏終止的機率。這個機率值就是蔡廷常數(Chaitin's constant)。

Let P_F be the domain of a prefix-free universal computable function F . The constant \Omega_F is then defined as {\display style \Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}} ,where {\display style \left|p\right|} denotes the length of a string p . —— Wikipedia

已證明蔡廷常數是不可計算的。這是由圖靈停機問題不可解所得出的。

另外很有意思的是,存在「 不可定義數 」。如果我們把定義看成「有限長度的語言描述」,那麽能描述出的數總是可數無窮多個(因為長度有限的文字是可以列舉的),而實數有不可數無窮多個,所以實際上,大多數都是不可定義數。但是我沒法告訴你任何一個不可定義數,因為我說出來的一瞬間它不再是不可定義數了。

而對於可計算數,它總能在有限的通用演算法裏求解任意位,也就滿足的問題中的「儲存」。

換個角度考慮,如果我們不局限於圖靈機呢?不可計算數僅僅在圖靈機下不可計算,那麽如果我們擁有比圖靈機更強的模型,是不是有可能突破這層限制?

但這已經遠遠超出我的學識範圍……或授權以看看下面的這一篇。