图灵的秘密

图灵构造了虚拟的图灵机并且通过图灵机证明了：图灵机本质上会被限定在它能做的事情中。 图灵在论文的引言中就指出了，虽然可计算数很多，并且在很多方面与实数相似，但是本质上它是可数的。（这里指的可数是指可数的无穷）。在图灵机的构造中，图灵首先是使用了一系列的符号来标志各种操作，然后将各种符号映射成单独的数字，从而将各种命令的组合转换成了一个整数，也就是描述数。图灵通过证明每个可计算序列都至少对应着一个描述数（至少一个是因为一个可计算序列可以通过不同的命令序列来计算），但并不存在着一个描述数对应着多个可计算序列。因此既然整数是可数的，而可计算序列又和描述数存在着一对多的关系，那么可计算序列也是可数的，即可计算数是可数的。另外，作为延伸，由于可计算数是可数的，但是实数是不可数的，所以我们可以说实数中存在着很多不可计算的实数，而这些不可计算的实数并不是我们在传统意义上所说的超越数。因为其实图灵机是可以计算某些非随机（数字排列上有着一定规律）的“超越数”。 这里插一条与图灵论文无关的文字：图灵机并无法计算数位完全随机的“超越数”，因为计算机软件本身并无法实现完全的随机，而只能生成伪随机序列。那么如果要生成数位完全随机的超越数，只能通过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] = x return arr; 这里的问题就在于A一直在执行自己，那么每一次都需要执行到计算R(k)的步骤上，而R(k) = R(k-1) + 1，所以就需要回头重新计算R(k-1)，所以这会是一个无限的循环。而之前我们又假设A是一个非循环机。所以这是矛盾的。 由此我们证明没有一个通用的过程能判断一个机器是否是非循环的。同理，也没有这样的机器，当给定了一个机器A的标准描述时，来判断A是否打印过给定的符号。

丢番图《算术》 行人啊，请稍驻足，这里埋葬着丢番图。上帝赋予他一生的六分之一，享受童年的幸福；再过十二分之一，两颊长胡；又过了七分之一，燃起结婚的蜡烛。爱子的降生盼了五年之久，可怜那迟来的儿郎啊，只活到父亲岁数的一半，便进入冰冷的坟墓。悲伤只有通过数学来消除，四年后，他自己也走完了人生旅途。 丢番图方程指只允许整数解的代数方程。 费马：“另一方面，将一个立方数分解为2个立方数，或者将一个4次方数分解为两个4次方数，亦或将除平方之外的任何乘方分解为两个有同幂的乘方，这些都是不可能的。对此，我已经发现了一个非常漂亮的证明，但是这儿的空白之处不够写下它。” 费马宣称，例如x^3+y^3=z^3是没有整数解的，并且幂为4、5、6及之后的类似方程都没有解。（费马大定理，1995年英国数学家安德鲁 怀尔斯证明） 古希腊人对无理数并不陌生，但不怎么喜欢它们。据说，毕达哥拉斯的学生希帕索斯在公元前6世纪发现2的平方根是无理数。故事里还说，此发现引起了轩然大波，毕达哥拉斯及其追随者试图掩盖这一发现，甚至把希帕索斯扔进了地中海。他们相当肯定，无理数不存在。丢番图拒绝承认无理数是其问题的解，延续了无理数不合他口味的这一传统。 代数方程的解（也叫方程的根）称为代数数。 非代数数确实存在，称为超越数，因为它们超越了代数。 超越数：刘维尔数（小数点后第1（1！），2（2！），6（3！），24（4！），120（5！），……位为1，其余位置为0）；pi（化圆为方不可实现）；e。 实数：有理数、无理数；代数数、超越数。 康托尔展露了自己在艺术和音乐上的天赋，但是他在17岁时决定“献身于数学”。 aN*x^N+aN-1*x^(N-1)+……+a2*x^2+a1*x+a0=0 对于任何一个代数方程，将所有的系数（ai的值）和N相加，称所得的值为方程的高。……所有的代数数都可以根据它的高和解来排列。因此，代数数是可数的。 一种势适用于自然数、有理数、代数数；另一种势适用于实数和连续统。 有限集合的真子集总是有较小的基数；但有些无限集合的真子集有着与集合本身一样的基数。 在连续统（直线上的实数）和平面上的点，乃至N维空间中的点之间建立一一对应关系。 对角线过程 可以将代数数按照多种不同的方式排列，可以制定不同的规则让对角线和原数列中的每一个数都不同。每次这么做，都将得到一个新的超越数。 自然数集合（任何可数的无限集合）的基数——第一超限数（记为a）。 集合--->幂集；a--->2^a 康托尔的连续统假设：连续统的基数是a之后的下一个超限数，称这个基数为c，即c=2^a 连续统与可数集的唯一区别在于，是否包含超越数。 Y2K（千年虫） 欧几里得《几何原本》五个公设： 1.从一点到另一点可以画一条线。 2.直线可以向两边不断延伸。 3.给定圆心和半径可以确定一个圆。 4.所有的直角都相等。 5.如果一条直线与另两条直线相交，且在同一侧形成的两个内角之和小于两直角，那么无限延长这两条直线，它们会在这一侧相交。 对于希尔伯特来说，将几何学建立在稳固的公理体系根基上，比解决或证明定理重要的多。……希尔伯特把他的几何类比到了实数平面上。这基本就是笛卡尔坐标系上的解析几何。于是希尔伯特几何学的一致性问题就转化成了实数算术的一致性问题。 可解性的判定——判定过程（由有限步操作构成的过程）——一种算法（当时还没有这一说法）。 1905年，爱因斯坦的“奇迹之年”。 量子力学中最知名的成果——不确定性原理。 罗素发现了皮亚诺和弗雷格的集合论中都存在一个同样的问题：一个集合的成员可以是其他的集合，甚至可以包含自身。那么由所有不包含自身的集合所组成的集合呢？它包含自身吗？如果答案是否定的，它是一个不包含自身的集合，那么根据定义他应该包含自身；而如果它包含自身，那么它就不再是不包含自身的集合了。（罗素悖论） 罗素和怀特海《数学原理》——逻辑学的崛起。 希尔伯特计划：偏离了逻辑主义，试图为所有的数学体系寻求严格的公理系统。为了分析公理系统，希尔伯特构思出了“元数学”和“证明论”，能够使用数理逻辑推导其他数学体系结构中的结论。——形式化 要构建一个形式化的数学系统，首先要构建定义、公理和从公理推导至定理的法则。 独立性 一致性 完备性：“可证明性”和“正确性”的区别。几乎所有人都相信哥德巴赫猜想为真：所有大于2的偶数都可表示成两个质数之和。然而，它仍然被称为“猜想”，因为它依然是有史以来最伟大的未被证明的数学问题之一。 可判定性：一种判定过程——用以确定任一给定合式公式的可证明性的通用方法。 更好、更强大的判定过程是那种能够确定正确性而不是可证明性的过程。 希尔伯特的墓碑上刻着：我们必须知道。我们必将知道。 哥德尔的不完备性定理（将公理加入逻辑系统中），邱奇、图灵的不可判定性。 图灵关于可计算数和判定性问题的论文，带来一个推断：开发一个通用的故障发现算法是不可能的。

...