本文已收录到 GitHub · AndroidFamily，有 Android 进阶知识体系，欢迎 Star。技术和职场问题，请关注公众号 [彭旭锐] 进 Android 面试交流群。
大家好，我是小彭。
今天，我们正式开启一个新专栏 —— 计算机组成原理。 计算机组成原理是计算机科学中最基础的理论知识，你越早掌握这些知识，你就能越早享受知识带来的 "复利效应"。
在构思到写作的过程中，我一直在思考应该以什么内容作为这个专栏的开篇，应该以什么内容来吸引住读者的眼球，也有过其它一些想法。最后，我决定抛开所有功利的想法，回归到一个最纯粹的计算机科学问题 —— “计算机可以解决所有问题吗？”。
学习路线图：
一个有纸、笔、橡皮擦并且坚持严格的行为准则的人，实质上就是一台通用图灵机。 —— 图灵
在计算机科学中， 可计算性（calculability） 是指一个问题是否存在解决算法。对于一个问题，如果能够使用有限的机械的步骤求出结果，就是可计算的，反之则认为这个问题是不可计算的。
一开始，人们普遍认为任何问题都是有算法的，都是可计算的，而科学家的工作正是找出这些问题的解决算法。后来，人们经过长时间研究，发现很多问题依然找不到算法，也无法做出不存在算法的证明。例如数学家希尔伯特提出的 23 个数学问题中的第 10 个问题：
这个问题其实是希尔伯特提出的另一个问题的子集：
在图灵之前，美国数学家阿隆佐·丘奇（图灵的导师）率先提出了可判定性问题的解决方法 —— Lambda 演算 数学表达系统，并证明了不存在这样的通用判定算法，但其使用了非常多的数学技巧，难以理解和应用。
直到 1936 年（小伙子才 24 岁！），英国科学家艾伦·图灵在数学杂志上发表了论文 《论可计算数及其在可判定性问题上的应用》 ，其中提出了解决 “可判定性问题” 的一个开创性思路。论文我看不懂，我尽量将自己能理解到的核心思路概括为 3 点，如果有错误，欢迎你帮我指出：
小结一下： 图灵首先提出了一个能够实现任何计算的计算机模型 —— 图灵机，相比于阿隆佐·丘奇提出 Lambda 演算系统，图灵机模型更加简单。随后，图灵提出了著名的停机问题，并通过巧妙的逻辑悖论证明了停机问题在图灵机上是不可计算的，这是最早被证明无法解决的可判定性问题之一，为希尔伯特的可判定性问题提供了一个反例论证。
图灵雕像
—— 图片引用自 Wikipedia
图灵机的工作原理与人类使用笔和橡皮擦在纸上进行计算的过程类似，图灵机主要由 4 个部分组成：
TAPE，纸带上写满连续的符号，类似于计算机的指令；HEAD ：一个可移动指针，可以从纸袋上读取符号；TABLE ：规定了图灵机在不同状态下遇到不同符号的处理规则；图灵机示意图
—— 图片引用自 Wikipedia
在计算过程中，图灵机的读写头从纸带头部开始，不断地读取纸袋上的符号。图灵机内部有不同的状态，每个状态会根据读取到的符号，到不同的符号表中查找下一步的动作，例如左移、右移、修改格子或修改寄存器。不断重复这个步骤，最终，当图灵机运行到停机状态时，表示计算完成， 整个计算过程自始至终都由机器自动完成。
图灵机模型
—— 图片引用自 Wikipedia
停机问题： 是否存在一个计算机程序，它能够根据任意计算机程序的描述和输入来判断该程序最终会停止还是永远运行。如果把图灵机想象成一个程序或一个算法，那么这个问题就等价于：是否存在一个通用图灵机，它能够根据任意图灵机的描述和输入来判定该图灵机最终会停止还是永远运行。
在此之前，先思考一个类似的逻辑悖论：
理发师悖论： 在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，我将为本城所有不给自己刮胡子的人刮胡子，我也只给这些人胡子”。来找他刮脸的人络绎不绝，可是，有一天，这位理发师发现自己的胡子长了，他本能地抓起了剃刀，但是他看到自己的广告牌后陷入沉思：如果他不给自己刮胡子，他就属于 “不给自己刮胡子的人”，那么他就该给自己刮胡子。而如果他给自己刮胡子，他就属于 “给自己刮脸的人”，他就不该给自己刮胡子。
那这个理发师到底该不该给自己刮胡子呢？无论他刮还是不刮都会与广告词矛盾，产生一个悖论。唯一的破解方法就是把理发师自己排除到广告词的规则外，这样他想刮还是不刮都可以。
现在，我们回过头来 follow 图灵对停机问题的逻辑证明：
可以看到，跟理发师悖论类似，H 不管怎么回答都是矛盾的。这一悖论也意味着停机问题不能用图灵机来解决。
停机悖论
我所理解的图灵机的应用价值主要体现在 2 个方面：
目前，量子计算机是计算机科学界最尖端的发展方向，那么量子计算机和我们熟悉的经典计算机有哪些不同呢，量子计算是超运算吗，量子计算机能解决所有问题？
量子计算机（Quantum computer）一种使用 “量子物理实验代替数学计算” 的计算机。
在 1982 年，诺贝尔物理奖获得者理查德·费曼在报告 《计算机模拟物理学》中最早提出相对成熟的量子计算概念：对于千变万化且初始状态不确定的问题，如果单纯依靠计算难以解决，那么直接用量子实验来模拟，再观察实验的结果来获得计算结果。根据大数定律，只要实验采样的次数足够多，就能以足够大的精度获得结果。举个类似的例子，18 世纪的蒲丰投针实验，就是一种用反复投针的物理实验得到圆周率的方法，也是用实验获得计算结果的案例。
然而，量子计算机依然遵循丘奇-图灵论题，量子计算机在可计算性方面并没有任何优势。 任何可以由量子计算机解决的问题，只要提供足够的时间，都可以由经典计算机解决。虽然如此，量子计算机在处理某些特定问题上会存在时间上的绝对优势，这就是量子优越性。
经典计算机和量子计算机解决的问题有一定交叉，但两者擅长的方向不一样。量子计算机在解决特定问题上的绝对优势，也叫量子优越性。 例如，在路径规划、密码破解、材料设计、人工智能，原子结合，基因序列等，只需要知道答案，不需要知道过程的问题上，量子计算机强于经典计算机。那么，量子计算机是如何实现这一优越性的呢？—— 量子比特。
量子计算最基础的单元是 ”量子比特“，与电子比特在同一时刻只能表示 “0” 或 “1” 不同，量子比特既可以是 “0” 或 “1” 其中之一，也可以是 “0” 和 ”1“ 的叠加态。那么，1 个量子比特可以是 2 个电子比特的叠加态，2 个纠缠的量子比特就可以是 4 种电子比特的叠加态，4 个纠缠的量子比特就是 16 种电子比特的叠加态…… 依次类推，$n$ 个纠缠的量子比特就是 $2^n$ 种电子比特的叠加态。
这个特点有什么用呢？举个例子，要寻找 1 亿种密码中的正确密码，经典计算机的解法是用 穷举 法依次尝试 1 亿种可能性，直到出现命中正确答案的结果后停止。 而量子计算机可以直接制造叠加所有可能性的量子比特，一次性尝试所有可能性。 再通过量子干涉操控放大命中正确答案的信号，而缩减错误答案的信号，使得最终量子态包含引起正确答案的信号， 通过观察得到正确答案。
4个相互纠缠的量子比特可以同时处于 16 种比特组合中的所有状态
—— 原图截图自 突破！Fluxonium两比特门精度99.72% —— 阿里达摩院扫地僧 著
今天，我们了解了图灵机模型和量子计算机的简单原理，并在此基础上思考了计算机的计算边界，并不是所有问题都可以用计算解决。 虽然图灵机是所有现代计算机的抽象逻辑模型，但图灵机并不是一个实际的机器。 你应该听过冯·诺依曼机，它跟图灵机一样吗？
