当前位置: 华文问答 > 数码

计算机能不能真正意义上存储一个无理数?

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

已证明蔡廷常数是不可计算的。这是由图灵停机问题不可解所得出的。

另外很有意思的是,存在「 不可定义数 」。如果我们把定义看成「有限长度的语言描述」,那么能描述出的数总是可数无穷多个(因为长度有限的文字是可以枚举的),而实数有不可数无穷多个,所以实际上,大多数都是不可定义数。但是我没法告诉你任何一个不可定义数,因为我说出来的一瞬间它不再是不可定义数了。

而对于可计算数,它总能在有限的通用算法里求解任意位,也就满足的问题中的「存储」。

换个角度考虑,如果我们不局限于图灵机呢?不可计算数仅仅在图灵机下不可计算,那么如果我们拥有比图灵机更强的模型,是不是有可能突破这层限制?

但这已经远远超出我的学识范围……或许可以看看下面的这一篇。