可计算数是可枚举的
不止被包含一次，而是至少两次。 这种方法带来的好处很有意思。想想一台计算π的图灵机。正常情况下，我们用一个无穷序列来表示π的数位： 3.1415926535897932384626433832795...现在，我们可以使用一个有限的整数来表示π，这个整数就是计算π的数位的图灵机的描述数。哪种π的表示更好呢？是前32个数位再跟上省略号？还是有多长耐心就能生成多少位数字的图灵机描述数？在某种意义上，描述数是π的一种更基本的数字表示方式，因为它描述了计算这个数的算法。 事实上，把每台机器归纳为一个数，图灵已经使仅通过枚举正整数便产生机器变为可能了。不是每一个正整数都是一个有效的图灵机描述数，而且很多有效的描述数也不能描述非循环机，但这种枚举必然包含了所有的非循环图灵机，其中每台这样的机器都对应着一个可计算数。因此，可计算数是可枚举的。 这是一个很重要的发现，尽管它也可能是令人不安的，因为它意味着，大部分的——或者根据我们已有的关于实数范围的知识，几乎全部的——实数都不是可计算的。 这个出乎意料的发现，连同一些数学悖论和量子引力的研究，促使数学家格雷戈里·蔡廷提出疑问：“实数究竟有多真实？”能证明实数确实存在的证据的确很少。
分享到:
閱讀更多 江南綠水青山 的文章
