从图灵机到量子计算机，计算机可以解决所有问题吗？

本文已收录到 GitHub · AndroidFamily[1]，有 Android 进阶知识体系，欢迎 Star。

前言

大家好，我是小彭。

今天，我们正式开启一个新专栏 —— 计算机组成原理。计算机组成原理是计算机科学中最基础的理论知识，你越早掌握这些知识，你就能越早享受知识带来的 "复利效应"。

在构思到写作的过程中，我一直在思考应该以什么内容作为这个专栏的开篇，应该以什么内容来吸引住读者的眼球，也有过其它一些想法。最后，我决定抛开所有功利的想法，回归到一个最纯粹的计算机科学问题 —— “计算机可以解决所有问题吗？”。

学习路线图：

1. 图灵机 —— 哪些问题是可计算的？

一个有纸、笔、橡皮擦并且坚持严格的行为准则的人，实质上就是一台通用图灵机。—— 图灵

1.1 图灵机的背景

在计算机科学中， 可计算性（calculability） 是指一个问题是否存在解决算法。对于一个问题，如果能够使用有限的机械的步骤求出结果，就是可计算的，反之则认为这个问题是不可计算的。

一开始，人们普遍认为任何问题都是有算法的，都是可计算的，而科学家的工作正是找出这些问题的解决算法。后来，人们经过长时间研究，发现很多问题依然找不到算法，也无法做出不存在算法的证明。例如数学家希尔伯特提出的 23 个数学问题中的第 10 个问题：

• 希尔伯特第 10 问题： 是否存在一个算法能判定任何丢番图方程有无整数解？

这个问题其实是希尔伯特提出的另一个问题的子集：

• 可判定性问题： 是否存在一个算法能够判定任何数学命题的真伪？如果存在这样的算法，那么很多数学问题都可以直接得到答案。如果不存在这样的算法，希尔伯特第 10 问题自然也不成立。

在图灵之前，美国数学家阿隆佐·丘奇（图灵的导师）率先提出了可判定性问题的解决方法 —— Lambda 演算[2] 数学表达系统，并证明了不存在这样的通用判定算法，但其使用了非常多的数学技巧，难以理解和应用。

直到 1936 年（小伙子才 24 岁！），英国科学家艾伦·图灵在数学杂志上发表了论文 《论可计算数及其在可判定性问题上的应用》[3] ，其中提出了解决 “可判定性问题” 的一个开创性思路。论文我看不懂，我尽量将自己能理解到的核心思路概括为 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%[4] —— 阿里达摩院扫地僧 著

2.3 量子计算两大核心难题 —— 多比特 & 高精度

• 多比特数： 目前还未实现超过百级的比特数；
• 高精度： 操控量子的精度不够，且比特数越多，操控难度越大。当操作次数增加后，错误也会累积，最终量子态包含的正确信息也会越少，反而丢失了量子优越性。在现有的量子纠错方案下，维护 1 个物理比特的正确性需要另外 1000 个物理比特来纠错。

3. 总结

今天，我们了解了图灵机模型和量子计算机的简单原理，并在此基础上思考了计算机的计算边界，并不是所有问题都可以用计算解决。虽然图灵机是所有现代计算机的抽象逻辑模型，但图灵机并不是一个实际的机器。你应该听过冯·诺依曼机，它跟图灵机一样吗？

参考资料

• Truing machine[5] —— Wikipedia
• Universal Turing Machine[6] —— Wikipedia
• Halting problem[7] —— Wikipedia
• Church–Turing Thesis[8] —— Wikipedia
• Quantum Computing[9] —— Wikipedia
• Qubit[10] —— Wikipedia
• 突破！Fluxonium两比特门精度99.72%[11] —— 阿里达摩院扫地僧 著
• 10分钟速成课 计算机科学（第 15 集 · 艾伦·图灵）[12] —— Carrie Anne 著

参考资料

[1]

GitHub · AndroidFamily: https://github.com/pengxurui/AndroidFamily

[2]

Lambda 演算: https://en.wikipedia.org/wiki/Lambda_calculus

[3]

《论可计算数及其在可判定性问题上的应用》: https://www.doc88.com/p-2177812966344.html

[4]

突破！Fluxonium两比特门精度99.72%: https://v.douyin.com/6AGhMpo/

[5]

Truing machine: https://en.wikipedia.org/wiki/Turing_machine

[6]

Universal Turing Machine: https://en.wikipedia.org/wiki/Universal_Turing_machine

[7]

Halting problem: https://en.wikipedia.org/wiki/Halting_problem

[8]

Church–Turing Thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

[9]

Quantum Computing: https://en.wikipedia.org/wiki/Quantum_computing

[10]

Qubit: https://en.wikipedia.org/wiki/Qubit

[11]

突破！Fluxonium两比特门精度99.72%: https://v.douyin.com/6AGhMpo/

[12]

10分钟速成课 计算机科学（第 15 集 · 艾伦·图灵）: https://www.youtube.com/watch?v=v0f5IveW3zg&list=PLdYq_l3Bzf1elCyzIfx2JgHfSMTsWbnfg&index=15