本文已收录到 GitHub · AndroidFamily，有 Android 进阶常识体系，欢送 Star。技术和职场问题，请关注公众号 [彭旭锐] 进 Android 面试交换群。
前言
大家好，我是小彭。
明天，咱们正式开启一个新专栏 —— 计算机组成原理。计算机组成原理是计算机科学中最根底的理论知识，你越早把握这些常识，你就能越早享受常识带来的 “ 复利效应 ”。
在构思到写作的过程中，我始终在思考应该以什么内容作为这个专栏的开篇，应该以什么内容来吸引住读者的眼球，也有过其它一些想法。最初，我决定抛开所有功利的想法，回归到一个最纯正的计算机科学问题 ——“计算机能够解决所有问题吗？”。
学习路线图：
1. 图灵机 —— 哪些问题是可计算的？
一个有纸、笔、橡皮擦并且保持严格的行为准则的人，本质上就是一台通用图灵机。—— 图灵
1.1 图灵机的背景
在计算机科学中，可计算性（calculability） 是指一个问题是否存在解决算法。对于一个问题，如果可能应用无限的机械的步骤求出后果，就是可计算的，反之则认为这个问题是不可计算的。
一开始，人们普遍认为任何问题都是有算法的，都是可计算的，而科学家的工作正是找出这些问题的解决算法。起初，人们通过长时间钻研，发现很多问题仍然找不到算法，也无奈做出不存在算法的证实。例如数学家希尔伯特提出的 23 个数学问题中的第 10 个问题：
- 希尔伯特第 10 问题： 是否存在一个算法能断定任何丢番图方程有无整数解？
这个问题其实是希尔伯特提出的另一个问题的子集：
- 可判定性问题： 是否存在一个算法可能断定任何数学命题的真伪？如果存在这样的算法，那么很多数学问题都能够间接失去答案。如果不存在这样的算法，希尔伯特第 10 问题天然也不成立。
在图灵之前，美国数学家阿隆佐·丘奇（图灵的导师）率先提出了可判定性问题的解决办法 —— Lambda 演算 数学表白零碎，并证实了不存在这样的通用断定算法，但其应用了十分多的数学技巧，难以了解和利用。
直到 1936 年（小伙子才 24 岁！），英国科学家艾伦·图灵在数学杂志上发表了论文《论可计算数及其在可判定性问题上的利用》，其中提出了解决“可判定性问题”的一个开创性思路。论文我看不懂，我尽量将本人能了解到的外围思路概括为 3 点，如果有谬误，欢送你帮我指出：
- 1、自动机（Automatic Machines）： 图灵察看了人类应用笔和橡皮擦在纸上进行计算的过程，将事实世界中的所有计算行为归结为一系列简单机械的动作。在论文中，图灵将这种以简单机械的形式运行的设想中的机器称为自动机，而后人则将这种机器称为“图灵机”；同时，图灵证实了只有提供足够的工夫和内存，图灵机总是可能实现任何计算；
- 2、通用图灵机（Universal Turing Machines）： 假如有一个非凡的图灵机，它可能接管另外一些图灵机作为输出，并且可能产生和这些图灵机一样的输入，那么咱们说这个非凡的图灵机就是通用图灵机。在这里，咱们能够把图灵机设想成一个程序或一个算法，而通用图灵机就是可能运行程序的计算机，目前咱们所能接触到的所有古代电子计算机都是通用图灵机。
- 3、停机问题（Halting Problem）： 为了解决希尔伯特的可判定性问题，图灵将“断定数学命题真伪”的问题转化为“断定图灵机是否会停机”的问题，即驰名的停机问题 —— “是否存在一个可能断定其它图灵机是否会停机的通用图灵机”。 随后，图灵通过一个奇妙的逻辑矛盾证实了不存在这样的通用图灵机，等于证实了“不存在一个算法可能断定任何数学命题的真伪”。图灵的这个逻辑证实的推导过程，咱们先放到一方稍后再说。
小结一下： 图灵首先提出了一个可能实现任何计算的计算机模型 —— 图灵机，相比于阿隆佐·丘奇提出 Lambda 演算零碎，图灵机模型更加简略。随后，图灵提出了驰名的停机问题，并通过奇妙的逻辑悖论证实了停机问题在图灵机上是不可计算的，这是最早被证实无奈解决的可判定性问题之一，为希尔伯特的可判定性问题提供了一个反例论证。
图灵雕像
—— 图片援用自 Wikipedia
1.2 图灵机的工作原理
图灵机的工作原理与人类应用笔和橡皮擦在纸上进行计算的过程相似，图灵机次要由 4 个局部组成：
- 1、输出：一条有限长的纸带
TAPE，纸带上写满间断的符号，相似于计算机的指令； - 2、读写头
HEAD：一个可挪动指针，能够从纸袋上读取符号； - 3、符号表
TABLE：规定了图灵机在不同状态下遇到不同符号的解决规定； - 4、状态寄存器：记录图灵机外部状态（无限状态），其中有一个非凡的停机状态（HALT），当图灵机遇到停机状态时，程序完结。
图灵机示意图
—— 图片援用自 Wikipedia
在计算过程中，图灵机的读写头从纸带头部开始，一直地读取纸袋上的符号。图灵机外部有不同的状态，每个状态会依据读取到的符号，到不同的符号表中查找下一步的动作，例如左移、右移、批改格子或批改寄存器。一直反复这个步骤，最终，当图灵机运行到停机状态时，示意计算实现，整个计算过程从头至尾都由机器主动实现。
图灵机模型
—— 图片援用自 Wikipedia
1.3 停机问题的逻辑证实
停机问题： 是否存在一个计算机程序，它可能依据任意计算机程序的形容和输出来判断该程序最终会进行还是永远运行。如果把图灵机设想成一个程序或一个算法，那么这个问题就等价于：是否存在一个通用图灵机，它可能依据任意图灵机的形容和输出来断定该图灵机最终会进行还是永远运行。
在此之前，先思考一个相似的逻辑悖论：
理发师悖论： 在某个城市中有一位理发师，他的广告词是这样写的：“自己的理发技能非常高超，我将为本城所有不给本人刮胡子的人刮胡子，我也只给这些人胡子”。来找他刮脸的人川流不息，可是，有一天，这位理发师发现自己的胡子长了，他本能地抓起了剃刀，然而他看到本人的广告牌后陷入深思：如果他不给本人刮胡子，他就属于“不给本人刮胡子的人”，那么他就该给本人刮胡子。而如果他给本人刮胡子，他就属于“给本人刮脸的人”，他就不该给本人刮胡子。
那这个理发师到底该不该给本人刮胡子呢？无论他刮还是不刮都会与广告词矛盾，产生一个悖论。惟一的破解办法就是把理发师本人排除到广告词的规定外，这样他想刮还是不刮都能够。
当初，咱们回过头来 follow 图灵对停机问题的逻辑证实：
- 1、假如存在一个可能断定其它程序是否会停机的通用图灵机 H，输入后果是“会停机 or 不停机”。如果可能找到一个程序，图灵机 H 无奈正确地判断该程序是否会停机，就阐明停机问题无奈解决；
-
2、为了找到这样的程序，图灵基于 H 定义了另一个图灵机 ^H，^H 会产生与输出程序相同的输入：如果程序会停机则 ^H 不会停机，如果程序不会停机则 ^H 会停机。
- 如果 H 的输入后果是“程序会停机”，那么 ^H 进入一个死循环永远运行上来，即 ^H 不停机；
- 如果 H 的输入后果是“程序不停机”，那么 ^H 会输入“程序不停机”，并且停机。
-
3、当初 H 和 ^H 各司其职，勉强能够了解。思考一个非凡状况，如果把 ^H 自身作为 ^H 的输出程序，后果是什么？
- 如果 H 的输入后果是“^H 会停机”，那么 ^H 会进入死循环永远不停机；
- 如果 H 的输入后果是“^H 不停机”，那么 ^H 会停机。
能够看到，跟理发师悖论相似，H 不管怎么答复都是矛盾的。这一悖论也意味着停机问题不能用图灵机来解决。
停机悖论
1.4 图灵机的意义
我所了解的图灵机的利用价值次要体现在 2 个方面：
- 1、奠定了古代计算机的形象逻辑模型： 其实，在图灵机模型之前，也有其余科学技术提出了可能形容人类计算能力的模型，例如 Lambda 演算。但相比于其余模型，图灵机模型的劣势在于简略间接，而且很容易通过机械技术或电子技术实现。在图灵机模型的价值被世人认可后，图灵机模型也为古代计算机奠定了实践根底。 图灵起初被誉为“计算机科学之父”，图灵机模型的奉献比重很大。
- 2、证实了计算机存在计算边界： 图灵先是证实了图灵机总是可能实现任何计算，但又证实了停机问题无奈用图灵机解决。将这两点联合起来，阐明不是所有问题都能用计算解决，例如决策问题。这一实践起初建设了可计算实践的根底，前人称之为 “丘奇 - 图灵论题”：无论有多少工夫或内存，有些问题是计算机无法解决的，除非建设齐全超过图灵机的计算模型，或者说“超计算”。
目前，量子计算机是计算机科学界最尖端的倒退方向，那么量子计算机和咱们相熟的经典计算机有哪些不同呢，量子计算是超运算吗，量子计算机能解决所有问题？
2. 量子计算机 —— 用试验代替计算
2.1 什么是量子计算机？
量子计算机（Quantum computer）一种应用“量子物理试验代替数学计算”的计算机。
在 1982 年，诺贝尔物理奖获得者理查德·费曼在报告《计算机模仿物理学》中最早提出绝对成熟的量子计算概念：对于变幻无穷且初始状态不确定的问题，如果单纯依附计算难以解决，那么间接用量子试验来模仿，再察看试验的后果来取得计算结果。依据大数定律，只有试验采样的次数足够多，就能以足够大的精度取得后果。举个相似的例子，18 世纪的蒲丰投针试验，就是一种用重复投针的物理试验失去圆周率的办法，也是用试验取得计算结果的案例。
然而，量子计算机仍然遵循丘奇 - 图灵论题，量子计算机在可计算性方面并没有任何劣势。 任何能够由量子计算机解决的问题，只有提供足够的工夫，都能够由经典计算机解决。尽管如此，量子计算机在解决某些特定问题上会存在工夫上的绝对优势，这就是量子优越性。
2.2 什么是量子优越性？
经典计算机和量子计算机解决的问题有肯定穿插，但两者善于的方向不一样。量子计算机在解决特定问题上的绝对优势，也叫量子优越性。 例如，在门路布局、明码破解、资料设计、人工智能，原子联合，基因序列等，只须要晓得答案，不须要晓得过程的问题上，量子计算机强于经典计算机。那么，量子计算机是如何实现这一优越性的呢？—— 量子比特。
量子计算最根底的单元是”量子比特“，与电子比特在同一时刻只能示意“0”或“1”不同，量子比特既能够是“0”或“1”其中之一，也能够是“0”和”1“的叠加态。那么，1 个量子比特能够是 2 个电子比特的叠加态，2 个纠缠的量子比特就能够是 4 种电子比特的叠加态，4 个纠缠的量子比特就是 16 种电子比特的叠加态…… 顺次类推，$n$ 个纠缠的量子比特就是 $2^n$ 种电子比特的叠加态。
这个特点有什么用呢？举个例子，要寻找 1 亿种明码中的正确明码，经典计算机的解法是用 穷举 法顺次尝试 1 亿种可能性，直到呈现命中正确答案的后果后进行。 而量子计算机能够间接制作叠加所有可能性的量子比特，一次性尝试所有可能性。 再通过量子干预操控放大命中正确答案的信号，而缩减谬误答案的信号，使得最终量子态蕴含引起正确答案的信号，通过观察失去正确答案。
4 个互相纠缠的量子比特能够同时处于 16 种比特组合中的所有状态
—— 原图截图自 冲破！Fluxonium 两比特门精度 99.72% —— 阿里达摩院扫地僧 著
2.3 量子计算两大外围难题 —— 多比特 & 高精度
- 多比特数： 目前还未实现超过百级的比特数；
- 高精度： 操控量子的精度不够，且比特数越多，操控难度越大。当操作次数减少后，谬误也会累积，最终量子态蕴含的正确信息也会越少，反而失落了量子优越性。在现有的量子纠错计划下，保护 1 个物理比特的正确性须要另外 1000 个物理比特来纠错。
3. 总结
明天，咱们理解了图灵机模型和量子计算机的简略原理，并在此基础上思考了计算机的计算边界，并不是所有问题都能够用计算解决。尽管图灵机是所有古代计算机的形象逻辑模型，但图灵机并不是一个理论的机器。你应该听过冯·诺依曼机，它跟图灵机一样吗？
参考资料
- Truing machine —— Wikipedia
- Universal Turing Machine —— Wikipedia
- Halting problem —— Wikipedia
- Church–Turing Thesis —— Wikipedia
- Quantum Computing —— Wikipedia
- Qubit —— Wikipedia
- 冲破！Fluxonium 两比特门精度 99.72% —— 阿里达摩院扫地僧 著
- 10 分钟速成课 计算机科学（第 15 集 · 艾伦·图灵）—— Carrie Anne 著