本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 提问。

前言

大家好，我是小彭。

今日，咱们正式敞开一个新专栏 —— 核算机组成原理。 核算机组成原理是核算机科学中最根底的理论常识，你越早把握这些常识，你就能越早享用常识带来的 “复利效应”。

在构思到写作的进程中，我一直在考虑应该以什么内容作为这个专栏的开篇，应该以什么内容来吸引住读者的眼球，也有过其它一些主意。终究，我决议抛开一切名利的主意，回归到一个最朴实的核算机科学问题 —— “核算机能够处理一切问题吗？”。

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

思想导图：

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

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 种电子比特的叠加态…… 依次类推，nn 个羁绊的量子比特便是 2n2^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 著

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