图灵的秘密

图灵构造了虚拟的图灵机并且通过图灵机证明了：图灵机本质上会被限定在它能做的事情中。图灵在论文的引言中就指出了，虽然可计算数很多，并且在很多方面与实数相似，但是本质上它是可数的。（这里指的可数是指可数的无穷）。在图灵机的构造中，图灵首先是使用了一系列的符号来标志各种操作，然后将各种符号映射成单独的数字，从而将各种命令的组合转换成了一个整数，也就是描述数。图灵通过证明每个可计算序列都至少对应着一个描述数（至少一个是因为一个可计算序列可以通过不同的命令序列来计算），但并不存在着一个描述数对应着多个可计算序列。因此既然整数是可数的，而可计算序列又和描述数存在着一对多的关系，那么可计算序列也是可数的，即可计算数是可数的。另外，作为延伸，由于可计算数是可数的，但是实数是不可数的，所以我们可以说实数中存在着很多不可计算的实数，而这些不可计算的实数并不是我们在传统意义上所说的超越数。因为其实图灵机是可以计算某些非随机（数字排列上有着一定规律）的“超越数”。这里插一条与图灵论文无关的文字：图灵机并无法计算数位完全随机的“超越数”，因为计算机软件本身并无法实现完全的随机，而只能生成伪随机序列。那么如果要生成数位完全随机的超越数，只能通过RNG(硬件随机数生成器)，来通过环境噪声或者量子过程来产生随机数，如果我们定义一个图灵机来复制RNG，这时我们则需要定义不可数的状态格局，这也并不满足图灵机的意义。但是以上的可计算数有个小问题。先回顾下什么是可计算数？如果存在一个算法，能够给出小数点后任意位数的数字，我们就说这个数是可计算数。而之前我们基于的前提假设是可计算数的数位是非随机的，但是其实也许大多数实数的随机性只是一个幻想，比如，PI的数位看起来是随机的，但是PI本身却是可计算的（简单来说我们可以写出一段程序，来计算出PI的任意位数的值），也许表现出随机性的实数只是因为我们还并未发现其底层的数字结构，也就是说，存在着我们表面看起来“随机”的可计算数。（其实书中把这一段插进去太坑了，而且不知道是翻译的问题还是原书的问题，这段的文字表意是有很大的误导性的）图灵整篇Paper的终极意义并不在于证明可计算数是否可数，而在于证明可判定性是否成立。于是图灵其实只是把“可计算数可数”这一论段作为了证明可判定性的一个前提因素。接下来图灵从对角线方法切入这一命题，与康托尔证明实数不可数的方法一样，图灵用同样的方式来证明可计算数也是不可数的。但是？不可数么？图灵给出了反对的理由，这个证明的前提假设是错的。例如对角线方法在证明可计算数是否可数时，基于的前提假设是：<1> 我们要枚举出所有的可计算数加在Beta序列里。<2> 我们要保证Beta序列里的每一个“可计算数”都是可计算数。回头来看，因为图灵对可计算数的定义是可以通过有限方法计算出来的数，所以一定存在着一个计算序列来标识这个可计算数。所以为了计算Beta序列，需要存在着一种通用的方法来判断特定的整数是否是非循环机的描述数，换句话说，也就是来构造出一个机器，这个机器的作用是判断图灵机是否是非循环的图灵机，即用机器来判定机器。这样，图灵就把可计算数是否可数的问题转换成了判断是否存在机器来判定某个正整数是否为非循环机的描述数。这里我们再构造一个数字x，x的定义为从1开始枚举所有的数，对每一个数都判断这个数是否是一个合法的描述数，如果是再判断该描述数标识的图灵机是否是非循环的；如果是则计算这个数直到第n位（n的意思是到目前为止，有多少个非循环机的描述数 + 1，我们再次赋给其一个符号R(n)），把该位的值赋给x的第n位。举个例子：3 133 225 317是第一个非循环机的描述数，那么R(n)＝1+1＝2，然后计算该描述数的第二位，发现为1，所以此时x = ._1。我们通过上面的描述可以简单来说，如果机器B检测描述数N，如果N是合法的，那么R(N) = R(N-1) + 1，然后计算N的前R(N)位，否则R(N) = R(N-1)。图灵构造了三台图灵机，A负责生成描述数并且作为一个总的调度器，B负责判断该描述数是否合法（即是否是非循环及的描述数），C负责根据合法的描述数执行命令。那么A为了能够让B对其输出作出检查，则需要事先来得知并判断B的标准描述，以防止自己的输出不符合B的标准描述而让B宕机，而B的目的则是对A做出检查，然后交给C执行。由于我们对B的要求是能够对N做出判定，所以B一定是非循环的（即能在有限的步数内对N做出一个确定可终止的输出）。如果N是不合法的，那么第N步终止。否则，意味着描述数为N的图灵机是非循环的，因此第R(N)个数字是可以在有限的步数算出来的，于是当计算并将其写入到x的第R(N)位后，第N步终止。所以A是非循环的，因为A只是生成一个数字，并且调用B，然后执行C。所以A也是一台图灵机，也有着自己的描述数，那么在运行该程序计算x的时候，一定会有一个时刻，A在处理自己的描述数，也就是说A需要来判断自己是不是非循环的。 这是最重要的一步。我们来模拟下这个过程，在之前的步骤中，A生成并分析了从1到K-1的所有的正整数，并且得到了x的前R(K-1)位。现在用程序来模拟A做的事情是这样的：if check(k): x = execute(k) y = execute(R(k)) arr[y] = xreturn arr;这里的问题就在于A一直在执行自己，那么每一次都需要执行到计算R(k)的步骤上，而R(k) = R(k-1) + 1，所以就需要回头重新计算R(k-1)，所以这会是一个无限的循环。而之前我们又假设A是一个非循环机。所以这是矛盾的。由此我们证明没有一个通用的过程能判断一个机器是否是非循环的。同理，也没有这样的机器，当给定了一个机器A的标准描述时，来判断A是否打印过给定的符号。

尽管有人早就论证过计算机可以做什么，但在这种论证出现多年前，图灵就证明了计算机永远都做不到的事。

认识到不足需要更大的勇气。

历史 总是 试图 用 一系列 连贯 的 语句 和 段落 来 捕捉 生活， 然而 现实 生活 通常 杂乱 且 复杂 得 多。 历史 学家 必须 磨平 事实 的 粗糙 棱角， 忽略 次要 人物， 以 避免 离题。 这些 简化 有时候 会 扭曲 它 试图 阐述 的 事物， 导致 一系列 看上去 并不 自然 却 又不 可避免 的 事件 发生， 好像 任何 事情 都不能 改变 它们 的 发展， 甚至 暗示 着 这些 事件 就是 所有 可能 中最 好的 结果。 这些 扭曲 的 结果 有时候 会 称为 所谓 的” 历史 的 辉 格 解释”—— 19 世纪 的 那些 作家 把 大 英 帝国 的 历史 描绘 成 正在 逐步、 无情 地走 进 现代 议会 民 主制， 在此之后， 英国 的 历史学 家 赫 伯 特· 巴 特 菲 尔 德（ 1900— 1979） 称之为” 历史 的 辉 格 解释”。