《图灵的秘密》章节试读

《图灵的秘密》的笔记-基础知识 - 基础知识

丢番图《算术》
行人啊，请稍驻足，这里埋葬着丢番图。上帝赋予他一生的六分之一，享受童年的幸福；再过十二分之一，两颊长胡；又过了七分之一，燃起结婚的蜡烛。爱子的降生盼了五年之久，可怜那迟来的儿郎啊，只活到父亲岁数的一半，便进入冰冷的坟墓。悲伤只有通过数学来消除，四年后，他自己也走完了人生旅途。
丢番图方程指只允许整数解的代数方程。
费马：“另一方面，将一个立方数分解为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的偶数都可表示成两个质数之和。然而，它仍然被称为“猜想”，因为它依然是有史以来最伟大的未被证明的数学问题之一。
可判定性：一种判定过程——用以确定任一给定合式公式的可证明性的通用方法。
更好、更强大的判定过程是那种能够确定正确性而不是可证明性的过程。
希尔伯特的墓碑上刻着：我们必须知道。我们必将知道。
哥德尔的不完备性定理（将公理加入逻辑系统中），邱奇、图灵的不可判定性。
图灵关于可计算数和判定性问题的论文，带来一个推断：开发一个通用的故障发现算法是不可能的。

《图灵的秘密》的笔记-第1页

本书是根据图灵的论文「论可计算数及其在判定性问题上的应用」写的一本书，是对这篇论文的详细注释，探索turing构建图灵机的思维过程，对希尔伯特的可判定问题的研究进行详细论述。图灵天才般创造呢图灵机，＂后人借助他用无与伦比的想象力创造出来的翅膀才得以继续探索人类智慧的潜力和局限，并追求人类智慧在逻辑和数学上的意义。＂

《图灵的秘密》的笔记-第319页

《图灵的秘密》的笔记-第77页

Turing 真是奇葩，能想清楚这么变态的状态转移。我几下就晕了-_-!
00101101110...

《图灵的秘密》的笔记-第204页

《图灵的秘密》的笔记-第27页 - 无理数和超越数

超越数，那些1844年之前甚至不能证明其存在性的数，其实占了实数的绝大部分。事实上，它们几乎占满了所有的实数。
千百年来，我们对于数的概念完全是偏颇和扭曲的。我们总是重视整洁、秩序、模式，然而我们又生活在一个折中与近似的世界中。我们只关注那些对我们有意义的数字。为了数农场里的动物，我们发明了自然数；为了测量，我们发明了有理数；而在高等数学中，我们又发明了代数数。我们从连续统中挖出了所有这些数，却完全无视了实数海洋中其他有如微生物一般繁多的数。我们活在一种很安逸的幻觉中：有理数比无理数多得多，代数数比超越数多得多，当然这仅仅是我们的一厢情愿。然而事实上，在连续统的世界中几乎每一个数都是超越数。

《图灵的秘密》的笔记-第109页 - 第七章 子程序

为了纪念图灵机臭名昭著的低性能，我们使用“tar-pit”一词来描述过度一般化的计算机例程，准备这些例程比运行它们花费的时间更多
第六章 的 P90 到 P96，花了这么多篇幅，居然只是为了解释做开方运算时，那个图灵机是如何确定下一位是0还是1。共计用了27个格局。。。。。（当然，如果用骨架表的话，可以大大降低这个数字）
PS：在图灵机中一个格局指的是
1：格局名称；
2：此时cursor在纸带中碰见的所有可能性；
3：在这些可能性中，图灵机做的对应操作；
4：操作做完后，下一个格局名称是什么。
换句话说，其实一个格局可以当做一个函数。
那么一个由多种格局组成的机器其实就是：
一组函数，其中一个函数做为入口函数开始启动程序，之后这台机器只是在函数中来回跳转。这个机器的磁盘中只有那个纸带（即长度为无穷的一维数组），内存中只有当前cursor所指向的纸带中的一个格子

《图灵的秘密》的笔记-第62页

来自注释①
Gregory J.Chaitin, "Computers, Paradoxes and the Foundations of Machematics"
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/amsci.pdf配有各种配件的图灵机形象说明图

《图灵的秘密》的笔记-第315页

如果图灵机的内在限制不能在遵守物理定律的前提下被超越，那么对于那些执行计算或逻辑运算的内在机制而言，这又暗示着什么呢？当我们从探索人的思维和宇宙自身的角度来考虑这两个最重要的（也许甚至有些令人烦恼的）“内在机制”时，这个问题变得最为深刻。

《图灵的秘密》的笔记-160 - 160

再次提到了康托尔用于证明实数不可数的“对角线法”。第一次见到这个证明法，的确让我拍案叫绝。不过看到Matrix67的一篇日志《对角线方法之后的故事》后，我感到了盲从的羞愧，读书的深浅也从中见得。 http://www.matrix67.com/blog/archives/4812

《图灵的秘密》的笔记-第109页 - 运作的机器

第五章笔记：
这章开始有点味道了，可以这么理解这几个概念：
m-config：完成某些operations一个模块
symbol：分支条件
operations：几种CPU操作P、E、L、R
final-config：下一步的m-config的地址（turing论文中的机器没有内存）
可以先用现在计算机的概念理解，再反过来理解这些计算机是怎么来的和必要性。
另外讲几点自己目前的感悟：
1. turing论文中的机器告诉我们，可数的无限（如有理数）和有限对于人类大脑没有本质区别，因为事实上我们大脑只需要理解0和1就能理解所有有理数（你看二进制小数就把许多10进制有限推向了可数无限），构造出这些有理数这只不过是时间问题，就好比现在许多程序干的活人都能代替，只是我们受限于时间这个维度。
2. turing论文中的机器本质上是一个受限于某种模型的人。我们少了根手指照样能做几乎所有的事，turing找出了人类的某一组基，构成一个能刻画所有有理数的空间，这就是计算机能认识的世界，而我们通过写程序构造这些基的系数来表达空间中的有理数。
3. 要实现人工智能，可能需要让机器理解所有的无理数，因为那才是无穷产生的质变。现在的计算机程序就好像把我们能够理解的转告计算机，让它们代替我们工作。但如果要实现人工智能，本质问题等价于是要人类理解人类自身，也可能turing构造的基不在完备，需要寻找新的基。另一种思路是找到有理数到无理数的一座桥梁（应该不存在，因为桥梁是有限的）。

《图灵的秘密》的笔记-第38页

在这次演讲中，希尔伯特第一次提出了在20世纪20年代早期开始为大家所知的希尔伯特计划，该计划偏离了逻辑主义，试图为所有的数学体系寻求严格的公理系统。为了分析公理系统，希尔伯特构思出了“元数学”和“证明论”，能够使用数理逻辑推导其他数学体系结构中的结论。
现在，这种方法在数学中称为形式化。在希尔伯特的概念里，要构建一个形式化的数学系统，首先要构建定义、公理和从公理推导至定理的法则。理想状态下，生成的系统应该拥有以下四种互相关联的特性：
1、独立性
2、一致性
3、完备性
4、可判定性

《图灵的秘密》的笔记-第314页 - 第七章 万物皆是图灵机

倒数第二段：“假如我们拥有一种可以解决（不可判定）数论问题的不确定方法.....我们可以构造一种全新的机器（称为o-机器）......”
接下来作者的评价是有误解的。
Oracle-图灵机目前得到了很多的重视与推广，在复杂性理论、计算理论、现代密码学等领域中有广泛的应用。这种O-机器并不如作者想象的，需要构造出来（构造还会违反基本的物理定律）。而应该理解为一种假设。
假设你能得到神谕，神可以帮你解决所有你提出的具体问题，这样你似乎会有更强的能力。但这个结论似乎并不可靠，因为要论证你有更强的能力，你需要做的是不依赖神谕解决一个独立问题。
例如，我们知道，大整数分解是难题。如果有一个神可以帮你分解你交给他的所有大整数，再给你一个大整数，你能分解吗？如果不能，万能的神对你有什么帮助呢？
看了这一段，我想，不得不再次叹服，图灵在那个年代走得太快太远了，以至于100年之后的人还没有跟上他的步伐。

《图灵的秘密》的笔记-第149页

图灵以天才的创造力向我们展示如何使用纸带、读写磁头构造一个通用的计算机。图灵在构造出m-格局标准编码的基础上，实际上就是m-格局序列的基础上，设计出了一套图灵机指令的执行算法。这套算法从状态q1(DA)开始，依次执行m-格局的指令，将打印结果（图灵机的完全格局，输出字符+m-格局状态）输出到图灵机后面的纸带上。这套算法是以图灵机读写磁头的子程序（查找、复制、剪切等）为基础，解释和执行图灵机M的指令代码，图灵设计的这套算法实质上就是图灵机的解释程序，也即是元图灵机M'，这是图灵机的灵魂。天才的图灵以惊人的想象力和创造力，向我们展示了一套复杂而精确的体系，显示出计算机的本质。我不得不佩服图灵高超的技术和灵光闪现的思想，这着实令我佩服得五体投地，一代大师图灵永远活在所有计算机后辈的心目中，一座永远的丰碑，高山仰止，永留史册。

《图灵的秘密》的笔记-第71页

《图灵的秘密》的笔记-第182页

《图灵的秘密》的笔记-第151页

《图灵的秘密》的笔记-第68页 - 第四章 图灵的学业

“非循环机是好的机器”。。。
这句作者的评论似乎不对。从书中图灵的引文也看不出图灵有这种意图。而实际上“非循环机器”就是不停机不断打印数字的机器。而循环机就是停机或者打印了第二类字符。考虑到计算理论中考虑的是“有限步骤”的计算，所以，循环机在这个意义上才是“好”的机器。
1/4的二进制形式也没有必要不断打印无数个0，看不出打印无限个0有什么意义。
不得不再次重申，这是该书作者的解读。我看不出图灵在文章中有这样的意图。这里也行需要更多的理解。
比如，0.01 （一个有限的二进制）是不是可计算数？按作者的理解，0.01000（无穷个0）是可计算数，而1.01000......也是可计算数。但他没有回答我刚才这个问题，而我认为，0.01也是可计算数，因为它与0.01000（无穷个0）相差了一个整数0.
也就是说，我理解，有限的数列也应该是可计算的。我估计图灵考虑的是，按这个定义，有限数列显然是可计算，同时又可把无限数也纳入其中。
书没看完，不知道对不对。

《图灵的秘密》的笔记-第16章 - 第16章

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

《图灵的秘密》的笔记-第1页 - 引言

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

《图灵的秘密》的笔记-第291页 - lambda演算

英文版。
291页中间的部分：
The function θγ(n) can't be lambda-definable because zero is not lambda-definable.
在SICP中，习题2-6：
# 豆瓣无lisp代码，选择和lisp比较接近的ruby...
(define zero
(lambda (f)
(lambda (x) x)))
zero的定义中，不涉及计算，zero视为公理。
凡是lambda-definable都是可计算的，比如还是SICP习题2-6中的add-1。
暂时这么认为。
那么zero是不是邱奇数？？？

《图灵的秘密》的笔记-第89页

一个用二进制计算 \sqrt{2} 的算法：从整数位到小数位进行移动，总假设当前位为1，将当前得到的数与自身相乘，如果大于2，则当前位为0，如小于2，则当前位1。依次类推，就能不断计算出 \sqrt{2} 小数位的数字。
假设整数位为1，1 x 1 < 2，此位为1；
假设1.1（二进制），1.1 x 1.1 > 2，此位为0；
接着1.01，1.01 x 1.01 < 2；此位为1；
假设1.011...
用乘法来求平方根。

《图灵的秘密》的笔记-第63页 - 第四章 图灵的学业

“2.定义， \alpha机器 和 c-机器”
图灵这里给出的定义应该分别是“确定性图灵机”与“非确定性图灵机”。 作者的解读似乎有问题，他说：“。。。机器的行为会因人的交互动作而改变”，还有在第64页第一、二段的评论，包括说“选择机虽然有趣，但是它们在图灵的论文中无足轻重”。
也许在这篇文章中不重要，但是不确定性图灵机不得不说在计算复杂性理论中非常重要。
我认为，作者在这里对选择机有一定的误解。图灵似乎并没有说要人机交互，而说的是机器的行为部份地由格局确定（他没有说，choice来自哪里），他说的是possible。
只能说，大部份使用图灵机的科学家也许都是对图灵机的再创造。图灵得到的误解真是够多的。

《图灵的秘密》的笔记-第12页 - 间接证法

间接证法（归谬法、背理法）先提出一个假设，然后根据这个假设进行符合逻辑的推理，直到推出一个矛盾的结论。这个矛盾的结论说明我们最初的假设是错误的

《图灵的秘密》的笔记-第128页

《图灵的秘密》的笔记-可计算数的证明 - 可计算数的证明

图灵构造了虚拟的图灵机并且通过图灵机证明了：图灵机本质上会被限定在它能做的事情中。

图灵在论文的引言中就指出了，虽然可计算数很多，并且在很多方面与实数相似，但是本质上它是可数的。（这里指的可数是指可数的无穷）。在图灵机的构造中，图灵首先是使用了一系列的符号来标志各种操作，然后将各种符号映射成单独的数字，从而将各种命令的组合转换成了一个整数，也就是描述数。图灵通过证明每个可计算序列都至少对应着一个描述数（至少一个是因为一个可计算序列可以通过不同的命令序列来计算），但并不存在着一个描述数对应着多个可计算序列。因此既然整数是可数的，而可计算序列又和描述数存在着一对多的关系，那么可计算序列也是可数的，即可计算数是可数的。另外，作为延伸，由于可计算数是可数的，但是实数是不可数的，所以我们可以说实数中存在着很多不可计算的实数，而这些不可计算的实数并不是我们在传统意义上所说的超越数。因为其实图灵机是可以计算某些非随机（数字排列上有着一定规律）的“超越数”。

这里插一条与图灵论文无关的文字：图灵机并无法计算数位完全随机的“超越数”，因为计算机软件本身并无法实现完全的随机，而只能生成伪随机序列。那么如果要生成数位完全随机的超越数，只能通过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是否打印过给定的符号。

《图灵的秘密》的笔记-第59页

图灵曾说可计算数就是那些可以被机器写下来的数，而现在又用人类记忆的有限性来解释定义中的“有限步骤”。将人与机器随意地关联起来，这种做法是图灵研究的一大特点。人类思维的状态是离散的。据此，图灵将人与机器关联了起来。

《图灵的秘密》的笔记-第70页

《图灵的秘密》的笔记-第一部分 - 第一部分

第27页：广角镜头、精简语言的美。
第35页：“非欧音乐”笑喷饭。
第51页：“明确的”指令意味着“非智能”和“无意识”，也就是说计算能力越强越严谨的机器对“无意识”和“非智能”的要求就越高，因为你必须要保证机器在前进的路上不被路边的“野花”吸引了目光。

《图灵的秘密》的笔记-第264页

图灵所指的数的可计算性，是指能被图灵机（可以理解为内存无限大的计算机）计算出来。这个计算出来也不是指你能计算出一个实数小数点后面一共有多少位，而是指能精确到其任意一位。
证明是一件困难的事情，困难在人很难将发散的思维集中在一个点上。这或许是人类进化过程中无数次受惠于对知识的“信任跳跃”造成的对证明的无耐心。“信任跳跃”这个词我第一次看到是在Eric S.Roberts的《程序设计抽象思想》中对递归的介绍，大意为：你或许无法证明递归是work的，但你可以对其“信任跳跃”，just do it。
图灵证明了哪些数可计算，哪些不可计算。知道一件事不可能与知道一件事可能同样重要，这样你就可以避免在不可能的事情上浪费时间。