Cantor's Diagonal Method on Computable Numbers
在翻 Matrix67 的思考的乐趣的时候, 看到集合论那里, 依次证明了有理数, 代数数, 可计算数, 可定义数的可数性, 甚舒畅. 然后用经典的 Cantor's Diagonal Argument 证了实数的不可数性, 并说明了此方法对有理数不可用, 因为对角线生成的新数未必是有理数.
然后我想, 对角线法用在可计算数上似乎也可以啊..
假设可计算数可数, 排成一列
这个论断有两个问题:
-
规定了取数时的对应法则并不能保证取出的数是可计算的.
因为一个可计算数的某一位是几并不是确定的, 别忘了 0.9999... = 1. 可计算数的定义也没有保证程序每次输出的结果的十进制表示不能改变. 所以这个可计算数列表作为十进制小数表示出来时, 可能有很多等价形式. 取出的新数并不能够唯一确定了.
这个 bug 在原本的对角线法则中已有所体现了. 详细介绍对角线法则的地方, 一定会强调一个细节, 就是像
这样的函数是不行的, 每一位都加一并不能保证新数与原数不同. -
可计算数列表是不可计算的
这应该是更严重的 bug. 我们在证明可计算数的可数性时, 用到的论据是 "可计算数必对应一个图灵机, 而图灵机是可数的". 也就是说, 由于图灵机可排成一列, 那么可计算数必然也可以排成一列, 但事实上, 我们不可能计算出这一列的内容, 因为我们不可能判断出哪些图灵机是对应可计算数的. 说不定有的图灵机不停机呢? .. 这可没法知道.
Matrix67 在他的对角线方法之后的故事一文中也指出过这一点.(话说这篇文章的最后一段写的激动人心啊)
其实两个 bug 本质都是 "排成的列表是不确定的". 一个说十进制表示的不唯一, 一个说列表本身的不可计算
那么接下来的问题就是, 对于可定义数的可数性, 对角线法则失败在哪里呢?
对于可定义数, 问题出在对 "可定义数" 的定义上. 一阶可定义数是可数的, 其列表是可定义的, 按照对角线法则的确可以定义出一个不在 "一阶可定义数列表" 中的数, 但这种方法定义出的数已经不是一阶可定义数了. 见 wiki
update: 这里有 Matrix67 在图灵生日会的一个科普讲座, 其中讲了不少可计算数可数性与图灵机计算能力相关的问题, 十分有趣.
update2: 在读了 The Annotated Turing 之后才发现我的确浅薄了, 可计算数与对角线法的关系, 早在可计算数被定义出来之时, 就已被 Turing 考虑到了, 并且正是由此引出了停机问题.