算法本质是确定性的：Yuri Gurevich 论辅助计算

在计算机科学中，“算法”一词常被加上各种前缀：概率算法、量子算法、非确定性算法。但微软研究院科学家 Yuri Gurevich 在近期一场演讲中提出了一个反直觉的核心论点：真正的算法永远是确定性的。所谓“非确定性”，不过是算法通过外部“助手”获取信息的结果。

这一观点源自他数十年来对抽象状态机（Abstract State Machine, ASM）理论的研究。本文基于该演讲内容，梳理其论证逻辑、关键概念与历史脉络。

算法曾是确定性的代名词

Gurevich 回顾了 1930 至 1950 年代逻辑学家的工作。当时的核心任务是对“有效方法”进行精确刻画，并最终将其重命名为“算法”。在这一传统中，确定性是定义的一部分，而非附加属性。

他以几何算法为例：过圆外一点作圆的切线有两条，中世纪传下来的经典算法能帮你找到切线，但算法本身不做选择，选择权在人。算法只负责执行确定步骤，人的干预发生在算法之外。正因如此，Gurevich 在早期关于抽象状态机的论文中写道，“非确定性算法”是自相矛盾的说法。

后来情况似乎变了。概率算法、量子算法、非确定性算法纷纷出现，人们以为算法概念像数系扩张一样被拓宽了。但 Gurevich 表示，他最近意识到情况并非如此简单：这些新物种并不是算法本身变得不确定，而是算法学会了“求助”。

图灵机是理解这一确定性传统的核心模型：它由一条无限长的纸带、一个读写头和一张有限状态转移表构成，每一步动作（写入符号、移动读写头、切换状态）都由当前状态与读到的符号唯一决定。丘奇-图灵论题进一步主张，任何能被“有效方法”计算的函数，都可由图灵机计算，这就把“算法”与“确定性机械步骤”牢牢绑定。正是在这一背景下，早期逻辑学家把非确定性视为需要被排除的含糊性，而非算法的一种合法变体。

计算机科学是关于算法的科学

1982 年，Gurevich 从数学转向计算机科学。他追问一个根本问题：计算机科学作为科学，研究对象是什么？它不像物理研究原子、化学研究分子。他的结论是：计算机科学的核心对象是算法。

数据库是一份证书而非算法，但操作系统本质上是调度算法，编程语言本身也是算法——输入程序、输入数据、执行。如果这个判断成立，那么“什么是算法”就成了基础性问题。

他同时表达了对当时逻辑学风格的不满：指称语义、代数方法等声明式进路，像是逻辑学家在教导程序员该怎么做。但程序员正在改变世界，逻辑学家没有道德权利对他们说教。Gurevich 想理解程序员做对了什么——程序员不会写一段文本来解释算法，而是直接编程、直接运行。这促使他走向可执行的高层规格说明，即抽象状态机。

三个公设：从状态到交互

抽象状态机的公理化经历了漫长过程。Gurevich 将其概括为三个公设，第三个公设的成型花了约 15 年。

第一个公设是顺序时间公设的修订版。算法被视为转移系统：有状态集合、初始状态集合，以及每个状态下的步骤集合。在引入交互后，步骤不再是简单函数，因为不同的步骤可能到达同一后继状态，但外部可观察的交互行为不同。终止也不再是状态的属性，而是步骤的属性——某个步骤终止后，到达一个“死状态”，不再做任何事。

第二个公设借助了 Tarski 的模型论传统。状态是逻辑结构，一个固定词汇表的函数解释。步骤则是承载交互内容的“挂钩”：每个步骤记录下算法向交互对象发送的消息日志。交互对象分两类：预言机（oracle） 会返回应答，接收者（recipient） 只接收消息、不应答。

第三个公设（有界探索公设）处理的是“算法只查看有限信息”这一直觉。每个步骤对应一个有界项集（tags），算法按偏序探索这些项；两个状态的差异只有通过某个布尔项取不同值才会被探测到。如果两个步骤在布尔项上一致，它们的终止状态和状态变更也一致。

模型论意义上的“逻辑结构”由论域（个体对象的集合）、词汇表（函数符号、关系符号与常量符号）以及这些符号在论域上的解释组成。把算法状态视为这种结构，好处是状态的内部表示不必依赖具体数据结构，只需关心哪些项在何种解释下取何值。Tarski 的真定义让“某个布尔项在此状态下为真”成为精确概念，这也是有界探索公设能够用“布尔项取不同值”来刻画状态差异的前提。

用“助手”重写概率与量子算法

演讲中最具冲击力的部分，是把概率算法和量子算法重新表述为确定性算法加外部助手。

以简化的费马素性测试为例：重复 k 次，每次随机选取 a，若 a^(n-1) mod n ≠ 1 则返回合数。传统上这是概率算法。但 Gurevich 的改写是：算法本身确定性地调用一个名为 choose in 的预言机，请求它在 1 到 n-1 之间选一个数。预言机怎么选、是否真随机，是预言机的事，不是算法的事。

量子算法同理。以 Grover 搜索算法为例，在量子线路表示中，Hadamard 门、酉变换等操作对算法而言只是返回 true 的预言机调用——它们作为副作用改变量子态，但量子态对算法不可见。只有最后的测量门产生可观测的 0/1 输出。算法看到的是确定性的控制流：重复 m 次，计数器递增，最后并行输出 n 个比特。

Gurevich 坦言，他对量子物理几乎是门外汉。但从数学上看，量子计算中用到的线性代数并不神秘，甚至海森堡不确定性原理在他的表述中只是线性代数的一个引理。数学简单，物理诠释才是难题。

预言机（oracle）概念源于可计算性理论中的图灵归约：一台图灵机可以在一步内查询一个外部黑箱并得到正确答案，而不必自己计算该问题。经典结果如相对化证明表明，预言机的存在会改变可计算性与复杂性的图景。Gurevich 借用这一装置的方式不同：他不关心预言机可计算与否，只把它作为交互对象的抽象，用“询问—应答”把随机源或量子门的效果封装在算法定义之外，从而保持算法本体的确定性。

Spec Explorer 与一场反垄断官司

理论之外，演讲还穿插了一段产业往事。1990 年代末，Gurevich 在微软研究院组建团队，开发了 Spec Explorer——基于抽象状态机的高层可执行规格说明工具。团队成员 Wolfgang Grieskamp 等人的工作让工具变得健壮。

两类人成了用户。一是测试人员。当时测试岗位地位低、薪酬差，开发者不愿与他们沟通。Spec Explorer 让测试人员能主动提问、主动构造测试。二是高层管理者，包括比尔·盖茨。据 Gurevich 回忆，盖茨听了几分钟后就问：“这和图灵机有什么不同？”随后他理解了要点，还帮着向随行人员解释。

真正的转折来自欧盟。微软因在 Windows 中使用的特殊协议让内部程序获得比第三方更直接的访问权限，被欧盟起诉并败诉。欧盟要求微软交出高层可执行规格说明，而非源代码。Spec Explorer 由此进入核心位置，数百名工程师（多在中国和印度）用其编写协议规格。

Gurevich 评价，这一时刻让形式化建模站在了软件史上最重要的监管战役中心。不过他也承认，欧盟的胜利某种程度上是皮洛士式胜利——跨平台工具等新发展让整个局面变得过时。

启示：助手模式是一种认知框架

Gurevich 的论证不只是术语辨析。它提供了一种看待计算系统的框架：把不确定性来源外置为交互对象，算法核心保持确定性，系统行为则由算法与助手的协作决定。

这与分布式系统、人机协作乃至大模型工具调用中的“外部环境”思路有相通之处。算法不预测环境，只发送请求、接收应答，并在确定性规则下推进。至于助手内部如何运作，属于另一个层次的问题。

当然，这一框架的代价是：算法的行为保证依赖于对助手行为的假设。费马测试的可靠性取决于随机源的质量，量子算法的正确性取决于量子门是否按预期工作。Gurevich 没有回避这一点，他只是坚持：这些假设位于算法定义之外。

对于今天的 AI 与计算从业者，这个视角值得玩味。当我们说一个 AI 系统“具有不确定性”时，究竟是模型本身不确定，还是我们把采样器、工具调用、环境反馈当成了系统的一部分？把边界划在哪里，决定了我们如何定义、测试和信任一个系统。

在分布式系统里，这一思路对应的是把网络、时钟、故障模型视为环境假设，而非协议逻辑的一部分；在强化学习中，环境被形式化为提供观测与奖励的外部交互对象；在大模型工具调用中，函数返回值被当作外部预言机的应答。共同点是：核心控制流保持可判定、可复现，不确定性被推到接口之外，并以显式假设的形式被记录和验证。