玻尔百科什么是“计算”？从最基础的层面看，它是一个为了达成某一结果的循序渐进的过程——一份“食谱”。但我们如何将这个直观的概念形式化，构建一个严谨的数学框架呢？这个根本性问题是计算理论的核心，它不仅揭示了算法的巨大威力，也揭示了其令人惊讶且绝对的局限性。几十年来，计算机科学家和逻辑学家一直试图界定能够被机械化解决的问题的精确边界，并在这个过程中发现了一片充满可能性与不可能性的丰富图景。本文将作为探索这片迷人领域的指南。“原理与机制”一章将奠定基础，介绍 Alan Turing 优雅的计算模型、通用机器的强大概念，以及诸如停机问题等不可判定问题的重大发现。随后，“应用与跨学科联系”一章将探讨这些理论局限性的深远影响，将可解问题的世界划分为“简单”和“困难”（P vs NP）的类别，并审视这些概念如何应用于从数据压缩、金融到生物学和法律等不同领域。读完本文，您将对支配我们计算机乃至任何系统性推理和发现过程的法则有更深刻的理解。
{'PARADOX': {'PARADOX': {'PARADOX': ")\n2. 如果 HALTS 报告 PARADOX 会停机，那么进入一个无限循环。\n3. 如果 HALTS 报告 PARADOX 会永远循环，那么立即停机。\n\n现在问这个问题：当 PARADOX以自身的描述为输入运行时，它会停机吗？\n* 如果我们的HALTS判定器说它会停机，那么PARADOX被编程为永远循环。判定器错了。\n* 如果我们的HALTS判定器说它会永远循环，那么PARADOX被编程为停机。判定器又错了。\n\n摆脱这个矛盾的唯一方法是断定我们最初的假设是错误的。这种通用的停机判定器不可能存在。\n\n这种“[不可判定性](/sciencepedia/feynman/keyword/undecidability)”是一个深刻的理论限制，而非实践限制。它与一个程序运行了万亿亿年——一个有限但荒谬漫长的时间——无关。一个真正的停机判定器必须能正确识别出这样一个程序*确实*会停机。这种不可能性源于那些其本质与此类逻辑悖论紧密相连的程序。\n\n### 不可能性的[级联](/sciencepedia/feynman/keyword/cascade_interconnection)：归约\n\n[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)并非孤立的奇特现象。它是[不可判定性](/sciencepedia/feynman/keyword/undecidability)的“零号病人”。一旦我们知道一个问题无法解决，我们就可以通过一种强大的技术——**归约**——来证明许多其他问题也无法解决。\n\n逻辑很简单：“如果我能解决你那个奇怪的问题 B，我就可以用它作为工具来解决我的问题 A。但我已经知道问题 A 是不可能解决的。因此，你的问题 B 也一定不可能解决。”\n\n考虑一个看似简单的问题：我们能否判定一台任意的[图灵机](/sciencepedia/feynman/keyword/turing_machines)，在空白纸带上启动后，是否会写入符号 '1'？我们称之为PRINT_1问题。我们可以通过将[停机问题归约](/sciencepedia/feynman/keyword/halting_problem_reduction)到它来证明这是不可判定的。对于任何给定的程序 $M$，我们可以轻易地构造一个新程序 $M'$，它首先模拟 $M$，*[当且仅当](/sciencepedia/feynman/keyword/if_and_only_if)* $M$ 停机时，$M'$ 才在纸带上写入一个 '1'。\n\n现在，如果我们有一个神奇的PRINT_1判定器，我们就可以用它来解决[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)。我们只需将我们构造的机器 $M'$ 输入给它。如果判定器说“$M'$ 会打印一个 '1'”，我们就知道这是因为 $M$ 的模拟一定已经停机了。如果它说“$M'$ 永远不会打印 '1'”，我们就知道 $M$ 一定会永远运行。既然我们知道[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)是不可判定的，我们那个神奇的PRINT_1判定器就不可能存在。\n\n这项技术揭示了一个广阔、相互关联的[不可判定问题](/sciencepedia/feynman/keyword/undecidable_problems)图景。最惊人的例子或许是**希尔伯特第十问题**。几个世纪以来，数学家们一直在寻找一种通用方法，来判断任何给定的、具有整数系数的多元[多项式](/sciencepedia/feynman/keyword/polynomials)方程（例如 $x^3 + y^3 - z^3 = 0$）是否有整数解。Matiyasevich 在他人工作的基础上证明了这个问题是不可判定的。不存在任何单一[算法](/sciencepedia/feynman/keyword/algorithm)，可以接受任何此[类方程](/sciencepedia/feynman/keyword/class_equation)并判定其是否存在整数根。Turing 发现的抽象限制，深深地触及了[数论](/sciencepedia/feynman/keyword/number_theory)的核心。\n\n### 知与不知的优雅[对称](/sciencepedia/feynman/keyword/symmetry)\n\n这让我们看到了最后一个优美的结构。我们看到[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)是可识别的，但不可判定。那么它的[补集](/sciencepedia/feynman/keyword/set_theory_complement)——所有*不会*停机的程序的集合——又如何呢？稍加思索就会发现，你甚至无法识别这个集合。要识别它，你需要一台机器，对于任何永远循环的程序，它都能停机并说“是”。但要知道它永远循环，你就得永远等下去！\n\n这揭示了一个深刻而优雅的定理：一个语言 $L$ 是可判定的，[当且仅当](/sciencepedia/feynman/keyword/if_and_only_if) $L$ 和它的[补集](/sciencepedia/feynman/keyword/set_theory_complement) $\\bar{L}$ 都是[图灵可识别](/sciencepedia/feynman/keyword/turing_recognizable)的。\n\n如果你有一个针对“是”情况的识别器和一个针对“否”情况的识别器，你可以并行运行它们。迟早有一个会停机，给你一个明确的答案。这意味着，对于任何像[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)或希尔伯特第十问题这样可识别但不可判定的问题，它的[补集](/sciencepedia/feynman/keyword/set_theory_complement)必然是*不可识别的*。我们在认知能力上存在一种根本的不[对称性](/sciencepedia/feynman/keyword/symmetry)。我们可以通过找到解来确认解的存在，但解的不存在性可能是我们永远无法通过一个通用的、机械的过程来确定地证实的。\n\n从一个简单的食谱模型，我们一路走来，经历了通用机器、关于所有[算法](/sciencepedia/feynman/keyword/algorithm)的宏[大统一](/sciencepedia/feynman/keyword/grand_unification)论题，最终发现了知识的根本性、不可逾越的壁垒——不仅在[计算机科学](/sciencepedia/feynman/keyword/computer_science)中，而且在数学的根基处。这就是[计算理论](/sciencepedia/feynman/keyword/theory_of_computation)经久不衰的遗产：它不仅告诉我们能知道什么，也为我们不能知道什么提供了严谨的版图。", 'applications': '## 应用与跨学科联系\n\n在熟悉了计算的基本原理——[图灵机](/sciencepedia/feynman/keyword/turing_machines)和形式化[算法](/sciencepedia/feynman/keyword/algorithm)的理论齿轮和杠杆之后——我们可能倾向于认为这只是数学中一个狭窄、抽象的角落。事实远非如此。这些原理不仅仅关乎我们桌上的电脑；它们是一种描述过程、知识和极限的通用语言。它们提供了一个全新而强大的镜头，用以审视世界，从[蛋白质](/sciencepedia/feynman/keyword/proteins)的折叠到我们法律体系的基础。在本章中，我们将踏上一段旅程，以计算定律为罗盘，探索其应用的广阔而往往令人惊讶的图景。我们将发现这些定律在何处划下了坚实的界线，创造了可证明无法攀登的智力高山，我们还将绘制出可能之事的版图，揭示出一个丰富的问题地理，从易于穿越的平原到难以逾越的险峰。\n\n### 无法攀登的山脉：一个可计算世界的硬性限制\n\n20世纪最深刻的发现之一是，存在一些问题，它们被完美地提出，却可被证明无法用[算法](/sciencepedia/feynman/keyword/algorithm)来回答。其中最著名的是[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)：我们能否编写一个单一的程序，它可以检查任何其他程序及其输入，并确切地告诉我们该程序是会永远运行还是最终会停止？[Alan Turing](/sciencepedia/feynman/keyword/alan_turing) 证明了我们不能。这不是我们当前技术的失败，也不是我们缺乏创造力；这是一个根本性的限制，一道无论多少处理能力都无法突破的逻辑之墙。\n\n这个发现不仅仅是一个理论上的奇闻。它具有深刻而实际的后果。想象一下，一家科技初创公司声称发明了一种革命性的新编程语言，能够解决对于所有现有语言（如 Python 或 C++）来说都是“不可判定”的问题。[丘奇-图灵论题](/sciencepedia/feynman/keyword/church_turing_thesis)为我们提供了一个评估这一主张的锐利工具。该论题假定，[图灵机](/sciencepedia/feynman/keyword/turing_machines)捕捉了“[算法](/sciencepedia/feynman/keyword/algorithm)上可计算”这一直观概念的全部含义。由于所有现代通用编程语言在能力上都等同于[图灵机](/sciencepedia/feynman/keyword/turing_machines)（这一特性称为[图灵完备](/sciencepedia/feynman/keyword/turing_complete_2)性），它们都共享相同的基本限制。没有任何新的语法或架构可以神奇地解决[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)。这样的主张只有在一种情况下才可能成立，那就是这种新语言依赖于某种非[算法](/sciencepedia/feynman/keyword/algorithm)的、“神奇的”组件——理论家称之为“谕示机”——它存在于我们已知的计算宇宙之外。\n\n这些限制在一些出人意料的具体领域中浮现。考虑[数据压缩](/sciencepedia/feynman/keyword/data_compression)的任务。我们都使用 zip 文件和[图像压缩](/sciencepedia/feynman/keyword/image_compression)来使数据变小。但我们能否编写出终极压缩程序？一个能为任何给定的数据找到其绝对最短可能描述，并将其压缩到该理论最小尺寸的程序？这个最小尺寸被称为字符串的[柯尔莫哥洛夫复杂度](/sciencepedia/feynman/keyword/kolmogorov_complexity)。事实证明，这是一个不可计算的量。如果存在一个能为任何字符串计算[柯尔莫哥洛夫复杂度](/sciencepedia/feynman/keyword/kolmogorov_complexity)的“完美”压缩器，这将为我们提供一个解决[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)的后门。因此，[计算理论](/sciencepedia/feynman/keyword/theory_of_computation)中的一个基本逻辑障碍直接转化为[信息论](/sciencepedia/feynman/keyword/information_theory)中的一个实际限制：完美、通用压缩的梦想，现在是，并且永远都只是一个梦想。\n\n其影响甚至进一步波及到支配我们社会的[复杂系统](/sciencepedia/feynman/keyword/complex_systems)。以金融世界为例。交易越来越被复杂的[算法](/sciencepedia/feynman/keyword/algorithm)所主导。我们能否构建一个主监管AI，一个能够分析任何交易[算法](/sciencepedia/feynman/keyword/algorithm)并预测其行为是否会导致市场崩溃的计算监督者？这其中的利害关系再高不过了。然而，答案再次是响亮的“不”。交易[算法](/sciencepedia/feynman/keyword/algorithm)可以是一个任意复杂的程序。一个旨在判定它是否会触发“崩溃”行为的程序，在功能上等同于一个旨在解决[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)的程序。计算的内在通用性，虽然允许了如此复杂的策略，但也保证了它们的最终不可预测性。\n\n也许[不可判定性](/sciencepedia/feynman/keyword/undecidability)最发人深省的前沿领域在于法律和哲学。我们能构建Aegis，一个完美且公正的AI法官吗？想象一下，向它输入所有法律、证据和证词的全部、明确的文本。它能总是停机并做出“有罪”或“无罪”的正确判决吗？这是一个完美正义的诱人愿景。但它在逻辑上是不可能的。如果一个法律体系足够丰富，可以谈论其自身的规则和解释这些规则的过程，它就变得足够强大，可以表达类似于“这句话是假的”的[自指](/sciencepedia/feynman/keyword/self_referencing)悖论。人们可以构建一个假设的案例，其法律条文实际上规定：“[当且仅当](/sciencepedia/feynman/keyword/if_and_only_if) Aegis系统宣布被告无罪时，被告才是有罪的。”无论Aegis 做出何种判决，都会产生矛盾。这不是语言模糊或证据不全的问题；这是披着法律外衣的[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)。有趣的是，虽然*判定*任何案件的最终结果是不可能的，但*验证*一个给定的法律论证是否正确地遵循既定的公理和[推理规则](/sciencepedia/feynman/keyword/rules_of_inference)的过程，*是*一个可计算的任务。这一优美的区别反映了创造性飞跃与例行检查之间的差异，并表明在任何足够复杂的正式系统中，判断都扮演着一个根本性的、不可逾越的角色。\n\n### 绘制可及世界的版图：[复杂性](/sciencepedia/feynman/keyword/complexity)的景观\n\n虽然有些问题无法解决，但我们在科学和工业中面临的大多数问题幸好是可解的。真正的问题不是我们*能否*解决它们，而是*需要多长时间*。这就是[计算复杂性](/sciencepedia/feynman/keyword/computational_complexity)的领域，它将问题分类，不是分为“可解”和“不可解”，而是分为“简单”和“困难”。\n\n这片景观中的巨大[分界线](/sciencepedia/feynman/keyword/separatrix)是 P 类和 NP 类之间的区别。简单来说，P 是可以被高效解决的问题类别，其中“高效”意味着解决时间随输入规模呈[多项式](/sciencepedia/feynman/keyword/polynomials)[函数增长](/sciencepedia/feynman/keyword/growth_of_functions)（例如 $n^2$ 或 $n^3$）。许多实际问题都属于这一类。考虑一个简单的任务：判断一个字符串是否可以通过[交换](/sciencepedia/feynman/keyword/crossing_over)恰好一对字母变成另一个字符串，比如将 "trade" 变为 "tread"。一种朴素的方法可能涉及检查每一对可能的字符[交换](/sciencepedia/feynman/keyword/crossing_over)，这可能会很慢。但一个更聪明的[算法](/sciencepedia/feynman/keyword/algorithm)可以通过简单地计算字符串不同的位置数量来解决这个问题。如果没有差异，我们检查是否有重复字母。如果有两个差异，我们检查它们是否是相互[交换](/sciencepedia/feynman/keyword/crossing_over)。否则，就不可能。这种聪明的方法所花费的时间与字符串的长度成正比，使其稳稳地属于 P 类。\n\n在[分界线](/sciencepedia/feynman/keyword/separatrix)的另一边，是那些似乎需要通过对[指数级](/sciencepedia/feynman/keyword/exponential_order)增长的可能性进行惊人的、暴力搜索的问题。其中最著名的是[旅行商问题（TSP）](/sciencepedia/feynman/keyword/traveling_salesperson_problem_(tsp)|lang=zh-CN|style=Feynman)：给定一个城市列表和它们之间的距离，找到访问每个城市一次并返回起点的最短可能路线。这个问题属于 NP 类，意味着如果有人给你一条建议的路线，你可以*轻松验证*它是否足够短。但*找到*那条路线似乎需要检查一个随着城市数量增长而爆炸性增加的可能性数量。\n\nP = NP 是否成立是[计算机科学](/sciencepedia/feynman/keyword/computer_science)中最重要的开放问题。它问的是：如果我们能轻松识别一个正确的解（NP），我们是否也能轻松地找到它（P）？证明 P ≠ NP 将是一项巨大的科学发现。它将远比为 TSP 找到一个稍快一点的[算法](/sciencepedia/feynman/keyword/algorithm)（比如说一个运行时间为 $O(1.998^n)$ 而不是 $O(2^n)$ 的[算法](/sciencepedia/feynman/keyword/algorithm)）重要得多。这样的[算法](/sciencepedia/feynman/keyword/algorithm)改进虽然有价值，但仍会将问题留在“困难”的范畴内。而证明 P ≠ NP，则将建立一条计算的基本定律。它将意味着对于物流、[药物发现](/sciencepedia/feynman/keyword/drug_discovery)、[电路设计](/sciencepedia/feynman/keyword/circuit_design)和[人工智能](/sciencepedia/feynman/keyword/artificial_intelligence)中成千上万个重要问题，不存在巧妙的捷径。没有神奇的[算法](/sciencepedia/feynman/keyword/algorithm)等待被发现；创造力和暴力搜索，在某种深刻的意义上，是根本不同的。\n\n这片景观甚至比简单的“简单”与“困难”[二分法](/sciencepedia/feynman/keyword/bisection_method)更为丰富。[层次定理](/sciencepedia/feynman/keyword/hierarchy_theorems)告诉我们，[复杂性](/sciencepedia/feynman/keyword/complexity)的世界不是一个平坦的平原，而是一个拥有无数不断增高的山峰的山脉 ([@problem_-id:1426903])。这些定理形式化地证明了一个直观的想法：给计算机更多资源可以让它解决更多问题。一个能在 $n^3$ 时间内解决的问题与一个需要 $n^2$ 时间的问题属于根本不同的类别。更多的时间为你带来更多的计算能力。这揭示了计算宇宙一个优美而复杂的结构，一个精细分级的难度[连续体](/sciencepedia/feynman/keyword/continuous_bodies)。\n\n### 探索新前沿：物理世界中的计算\n\n这些抽象的计算思想如何与物理世界联系起来？自然本身是否在计算，如果是，它是否遵循同样的规则？\n\n考虑[蛋白质折叠](/sciencepedia/feynman/keyword/protein_folding)的生物过程。一条长长的[氨基酸](/sciencepedia/feynman/keyword/amino_acids)链在短短几微秒内自我折叠成复杂的三维形状。我们最好的超级[计算机模拟](/sciencepedia/feynman/keyword/computer_simulation)其中涉及的物理过程，可能需要数年才能预测出相同的形状。人们很容易将这种惊人的效率视为自然正在进行某种“超计算”，从而反驳[丘奇-图灵论题](/sciencepedia/feynman/keyword/church_turing_thesis)。但这种观点[混淆](/sciencepedia/feynman/keyword/confounding)了[复杂性](/sciencepedia/feynman/keyword/complexity)与[可计算性](/sciencepedia/feynman/keyword/computability)。[蛋白质](/sciencepedia/feynman/keyword/proteins)并没有解决一个不可计算的问题；它是一个遵循[热力学定律](/sciencepedia/feynman/keyword/laws_of_thermodynamics)的物理系统，迅速地稳定在一个低能量状态。它是一种大规模并行的[模拟计算机](/sciencepedia/feynman/keyword/analog_computer)，为单一任务高度优化。它比我们的数字模拟快，并不意味着它打破了计算定律，就像河水下流不是在“解决”一个复杂的[微分方程](/sciencepedia/feynman/keyword/differential_equations)一样。它只是突显了自然可以是一台非常高效的计算机。\n\n这引出了一个最激动人心的前沿领域：我们能否基于不同的物理原理构建新型计算机？这就是[量子计算](/sciencepedia/feynman/keyword/quantum_computing)的承诺。[量子计算](/sciencepedia/feynman/keyword/quantum_computing)机利用[叠加](/sciencepedia/feynman/keyword/superposition)和[纠缠](/sciencepedia/feynman/keyword/entanglement)等奇特的原理，其运行方式与[经典计算](/sciencepedia/feynman/keyword/classical_computation)机根本不同。它并不能像有时大众所想象的那样，赋予解决像[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)这样的不可计算问题的能力。它的力量在于改变某些问题的*[复杂性](/sciencepedia/feynman/keyword/complexity)*。最著名的例子是[整数分解](/sciencepedia/feynman/keyword/integer_factorization)，即找到一个大数的质因数的问题。在[经典计算](/sciencepedia/feynman/keyword/classical_computation)中，这个问题被认为是“困难的”。然而，对于[量子计算](/sciencepedia/feynman/keyword/quantum_computing)机来说，它是“简单的”，属于[量子复杂性类](/sciencepedia/feynman/keyword/quantum_complexity_classes) BQP。\n\n即使工程挑战依然巨大，对 BQP 等类的理论探索也是有价值的。想象一下，未来我们发现建造一台大型、可扩展的[量子计算](/sciencepedia/feynman/keyword/quantum_computing)机在物理上是不可能的。BQP 类会变得无关紧要吗？完全不会。BQP 的数学定义及其与其他类的关系，作为一个[理论计算机科学](/sciencepedia/feynman/keyword/theoretical_computer_science)的[分支](/sciencepedia/feynman/keyword/clade)，将保持其完全的有效性。它将成为一幅我们无法物理访问的世界的地图，但它仍然教给我们关于数学可能性边界的知识。对计算的追求，无论是在理论上还是在实践中，都是[算法](/sciencepedia/feynman/keyword/algorithm)的抽象世界与物理学的具体世界之间持续的对话。\n\n从逻辑的硬性限制到生命的物理过程，[计算理论](/sciencepedia/feynman/keyword/theory_of_computation)提供了一个统一的框架。它为我们提供了一个罗盘，不仅可以导航我们能建造什么，还可以导航我们能知道什么。这张地图仍在绘制中，其未被探索的领域预示着将继续重塑我们对科学、社会和我们自身的理解的发现。', '#text': ','}, '#text': '):\n1. 运行 HALTS('}, '#text': '## 原理与机制\n\n想象一下，你想要向某人解释什么是“食谱”。你不会从马亚尔反应的[分子化学](/sciencepedia/feynman/keyword/molecular_chemistry)讲起，而是会从一些简单的东西开始：一份配料清单和一系列步骤。“首先，拿一个鸡蛋。然后，敲开它。”整个宏伟的[计算理论](/sciencepedia/feynman/keyword/theory_of_computation)大厦就建立在这样一个同样谦逊而优雅的基础之上：寻找对“食谱”最完美、最根本的定义。\n\n### [算法](/sciencepedia/feynman/keyword/algorithm)的本质：[图灵机](/sciencepedia/feynman/keyword/turing_machines)\n\n[算法](/sciencepedia/feynman/keyword/algorithm)究竟是什么？其核心是一套明确的、有限的规则，可以被机械地遵循，无需任何洞察力或创造力。[Alan Turing](/sciencepedia/feynman/keyword/alan_turing) 的天才之处在于将这个直观的概念提炼成一台优美而简单的抽象机器。忘掉[硅](/sciencepedia/feynman/keyword/silicon)芯片和[发光](/sciencepedia/feynman/keyword/luminescence)的屏幕；想象一个只有三个部分的设备：\n\n1. 一条**纸带**，无限长，被分成一个个单元格。每个单元格可以容纳一个来自有限字母表的符号（如 0、1和一个空白符号sqcup）。这是机器的[内存](/sciencepedia/feynman/keyword/random_access_memory)和工作区。\n2. 一个**读写头**，它可以一次查看一个单元格，读取其中的符号，写入新符号，并向左或向右移动一步。\n3. 一套**有限的规则**（或状态），充当机器的大脑。一条规则很简单：“如果你处于状态 $q_i$ 并且看到符号 $s_j$，那么写入符号 $s_k$，向方向 $d$ 移动，并转换到状态 $q_l$。”\n\n就是这样。这就是一台**[图灵机](/sciencepedia/feynman/keyword/turing_machines)**。它就像一台配有非常简单说明书的打字机。然而，这个简单的模型被认为足够强大，能够捕捉我们所说的“计算”的本质。它是食谱的形式化[等价](/sciencepedia/feynman/keyword/biconditional)物。步骤的序列是程序，台面上的配料是纸带上的输入，而完成的菜肴则是机器停机时留在纸带上的输出。\n\n### 主宰[算法](/sciencepedia/feynman/keyword/algorithm)：通用机器\n\n有一段时间，人们可能认为对于每个不同的问题，都需要一台专门构建的[图灵机](/sciencepedia/feynman/keyword/turing_machines)。一台机器用于加法，另一台用于排序列表，第三台用于检查回文。这就像每种食谱都需要一个不同的厨房——一个做蛋糕，一个做汤，一个做沙拉。这样效率极低。\n\n理解上的下一个巨大飞跃是**[通用图灵机](/sciencepedia/feynman/keyword/universal_turing_machine)（UTM）**的概念。这是一个真正深刻的思想：一台固定的、单一的[图灵机](/sciencepedia/feynman/keyword/turing_machines)，可以模拟*任何其他*[图灵机](/sciencepedia/feynman/keyword/turing_machines)的行为。它是如何工作的？你只需将你想模拟的机器的描述——它的规则、它的状态——写在[通用图灵机](/sciencepedia/feynman/keyword/universal_turing_machine)的纸带上。然后，你再写上你想给那台被模拟机器的输入。[通用图灵机](/sciencepedia/feynman/keyword/universal_turing_machine)读取这个描述，然后一丝不苟地、一步一步地，对给定的输入执行被描述机器的规则。\n\n这不亚于**软件**思想的诞生。纸带上机器的描述 $\\langle M \\rangle$ 是程序。纸带上的输入 $w$ 是数据。[通用图灵机](/sciencepedia/feynman/keyword/universal_turing_machine)本身是硬件，是通用处理器。将一台机器的逻辑编码为数据，让另一台机器可以读取并据此行动的能力，是支撑每一台计算机、每一部智能手机、你用过的每一个数字设备的原理。为了实现这一点，编码方案必须是有效的；我们必须有一种可计算的方法来将机器的描述及其输入打包在一起，并能再次解包。但一旦这一点确立，我们就拥有了一份“主宰食谱”，可以执行任何可以想象到的其他食谱。\n\n### 伟大的统一：[丘奇-图灵论题](/sciencepedia/feynman/keyword/church_turing_thesis)\n\n所以，我们有了这个强大的模型——[图灵机](/sciencepedia/feynman/keyword/turing_machines)，以及一个可以运行任何程序的通用版本。但它是唯一的选择吗？如果某个其他才华横溢的头脑，也许在另一个世界，发明了一种完全不同的[计算模型](/sciencepedia/feynman/keyword/models_of_computation)，比如 Axiomats 假想的“准算盘” 或“Lambda [积分器](/sciencepedia/feynman/keyword/integrator)”？他们的模型能否解决[图灵机](/sciencepedia/feynman/keyword/turing_machines)无法解决的问题？\n\n这就是**[丘奇-图灵论题](/sciencepedia/feynman/keyword/church_turing_thesis)**登场的地方。它不是一个可以被形式化证明的定理，而是一个经受了数十年检验的基础性假说。它指出，任何能够被“有效计算”——即通过任何直观的、循序渐进的[算法](/sciencepedia/feynman/keyword/algorithm)过程——的函数，都可以由[图灵机计算](/sciencepedia/feynman/keyword/turing_machine_computation)。\n\n每当数学家或逻辑学家试图提出“[算法](/sciencepedia/feynman/keyword/algorithm)”的其他定义——如 lambda 演算、[递归](/sciencepedia/feynman/keyword/recursion)函数等等——这些定义最终都被证明在能力上与[图灵机](/sciencepedia/feynman/keyword/turing_machines)完[全等](/sciencepedia/feynman/keyword/congruence)价。如此多不同且独立的、旨在形式化计算思想的尝试都通向同一座山峰，这一事实为该论题提供了强有力的证据。这表明 Turing 不仅仅是发明了一种[计算模型](/sciencepedia/feynman/keyword/models_of_computation)；他发现了一条关于[算法](/sciencepedia/feynman/keyword/algorithm)本身性质的基本定律。\n\n将这个形式化论题与其物理对应物区分开来至关重要。**物理[丘奇-图灵论题](/sciencepedia/feynman/keyword/church_turing_thesis)**推测，我们宇宙中没有任何物理过程能够计算出[图灵机](/sciencepedia/feynman/keyword/turing_machines)无法计算的东西。如果我们发现一个神秘的外星造物，可以瞬间解决一个已知[图灵机](/sciencepedia/feynman/keyword/turing_machines)无法解决的问题，这将打破该论题的物理版本。然而，除非我们能理解其内部工作原理并将其描述为一个循序渐进的[算法](/sciencepedia/feynman/keyword/algorithm)，否则原始的、形式化的[丘奇-图灵论题](/sciencepedia/feynman/keyword/church_turing_thesis)将保持不变——它是一个关于[算法](/sciencepedia/feynman/keyword/algorithm)的论题，而不是关于神秘黑箱的论题。\n\n### 不可知之物：[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)与[不可判定性](/sciencepedia/feynman/keyword/undecidability)\n\n有了这个统一的计算框架，我们可以问一个非常自然且重要的问题：我们能创造一个完美的调试工具吗？我们能否编写一个单一的程序，它可以审查*任何*其他程序及其输入，并确切地告诉我们该程序最终会完成（停机）还是会陷入无限循环？这就是著名的**[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)**。\n\n乍一看，这似乎是可行的。让我们做一个区分。如果我们可以构建一台机器，对所有“是”实例停机并回答“是”，即使它在“否”实例上永远运行，那么这个问题就是**[图灵可识别](/sciencepedia/feynman/keyword/turing_recognizable)的**。如果存在一台机器，对于每个可能的输入，*总是*能停机并给出正确的“是”或“否”的回答，那么这个问题就是**图灵可判定的**。\n\n为[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)构建一个*识别器*是很容易的。正如 Alice 在一个著名的[思想实验](/sciencepedia/feynman/keyword/thought_experiments)中建议的那样，你只需模拟所讨论的程序。如果它停机，你的模拟最终会结束，你就可以自信地报告“是的，它停机了！”但如果程序永远运行，你的模拟也会永远运行。你将永远无法报告“不，它不会停机”。\n\n我们的梦想是构建一个*判定器*，一台像 Bob 的机器那样保证能给出答案的机器。Turing 证明的惊人事实是，这是不可能的。[停机问题](/sciencepedia/feynman/keyword/the_halting_problem)是**不可判定的**。其证明是[自我指涉](/sciencepedia/feynman/keyword/self_referencing)的杰作，一个无法逃脱的逻辑陷阱。想象我们有一个假设的停机判定器，称之为 HALTS(P, I)。现在，让我们构建一个淘气的、悖论性的程序，名为 PARADOX，它以自己的描述作为输入：\n\nPARADOX('}