计算模型是一种数学框架,用于规定计算过程如何表示信息、改变状态并产生结果。它定义了算法可用的操作、存储的组织方式,以及执行时遵循的规则。根据用途的不同,模型还可以规定如何度量时间、内存、通信、随机性或其他资源。计算模型的例子包括图灵机、有限自动机、λ 演算、随机存取机、布尔电路和量子电路。
计算模型使人们能够将计算的本质属性与具体设备的细节区分开来。它们是可计算性理论和计算复杂性研究的基础:前者研究问题能否通过算法求解,后者研究求解问题所需的资源。计算模型还为编程语言设计、硬件分析、分布式系统设计以及验证工作提供指导。
不同的模型用于回答不同的问题。两个模型可能计算完全相同的一组函数,却对同一任务给出截然不同的成本。适合用来证明不可能性定理的模型,未必适合预测程序在现代处理器上的运行时间。因此,选择模型时,需要明确计算的哪些方面必须显式表示,哪些方面可以通过抽象而略去。
形式化规定与计算行为
计算模型通常描述一组配置、配置之间的转换规则,以及解释输入和输出的方式。配置记录了确定后续可能步骤所需的全部信息,例如指令地址、寄存器内容、纸带符号,或相互通信的进程各自的局部状态。若 为配置空间,则确定性转换规则可以表示为一个偏函数:
输入编码选定一个初始配置,而指定的一类终止配置则决定何时可以得到结果。这样,一次计算就是由转换规则连接起来的有限或无限配置序列。
这种表述区分了几种不同的行为。在确定性模型中,每个配置至多有一个后继配置。在非确定性模型中,每个配置可能有多个后继配置,可用关系 表示。对于判定问题,通常采用存在性接受约定:只要至少有一条计算分支接受输入,该输入就被接受。概率模型则为各个转换赋予概率。这些区别涉及计算的语义,而不只是实现方式的选择。尤其需要注意,非确定性分支并不意味着普通的物理机器可以直接选中一条成功的分支。
输入和输出的约定同样重要。模型可以计算有限字符串上的偏函数、识别一种形式语言、转换数据流,或者与环境持续交互。对于偏函数 ,只要函数在输入处有定义,机器就必须输出 ;对于其他输入,机器可以不终止。识别器可以接受属于某种语言的字符串,而对不属于该语言的字符串则无限运行。判定器必须对每个有效输入都停机,并给出正确答案。这些区别避免了将不终止与拒绝混为一谈。
资源度量又增加了一个层面。时间可以按基本转换的次数计量,内存可以按访问过的存储位置数量计量,通信则可以按传输的比特数计量。对于在输入 上终止的确定性计算,模型可以定义一个代价 ;于是,长度为 的输入所需的最坏情况时间为
只有明确规定输入大小,以及哪些操作算作基本操作之后,这样的定义才有意义。一个十亿位整数并不会仅仅因为写成了一个数学变量,就成为大小为常数的输入。
计算模型还应与具体算法、编程语言和机器架构区分开来。算法是在某种计算框架内表达的特定步骤。语言提供描述程序的语法和语义。指令集架构则规定由处理器实现的接口。这些概念相互关联,却不能彼此替代:许多语言都可以为同一种抽象机器实现算法,而同一种架构也可以支持多种不同的抽象计算方式。
历史基础与有效可计算性
现代计算模型研究源于数理逻辑,尤其是对机械推理和有效计算进行刻画的尝试。早期计算装置表明,某些数值运算可以机械化,但这些装置本身并未给出算法的一般数学定义。奠基性的核心问题是:如何精确定义一类过程,使其涵盖所有能够遵循有限条明确无歧义的规则来执行的过程。
20 世纪 30 年代,几种形式化方法殊途同归。阿隆佐·丘奇提出了 λ演算,并将其用于有效可计算性的研究。库尔特·哥德尔结合雅克·埃尔布朗的思想开展了递归函数研究,提供了另一条形式化途径。1936 年,艾伦·图灵提出了一种理想化机器,用有限控制器、纸带和局部符号操作来分析其行为。同年,埃米尔·波斯特独立提出了一种相关的有限组合过程表述。这些是各不相同的数学构造,而非相互竞争的实用电子计算机设计方案。
这些主要形式体系之间的等价性至关重要。通过适当的编码,λ 抽象、一般递归定义和图灵机过程所能表示的函数被证明属于同一个集合。这种一致性支持了丘奇—图灵论题:每个有效可计算的函数都能由图灵机计算。该论题将“有效过程”这一非形式化概念与一个形式化的类联系起来。两个精确定义的模型之间的等价性可以用数学方法证明;而断言这一类涵盖所有可能的有效过程,则是一个范围更广的主张。
图灵的通用图灵机表明,只要提供其他机器的编码描述及其输入,一个固定的计算机制就能够模拟这些机器。这使程序本身成为可以存储、解释和操作的对象。因此,通用性并不等同于仅仅具备大量内置操作。通用机器之所以具有通用性,是因为它拥有一个有限的解释器,能够处理任意多种计算的描述。
同一时期的奠基性研究也确立了计算的局限。停机问题所问的是:一个指定的程序在给定输入上运行时,最终是否会终止;不存在能够对所有程序和输入判定这一问题的通用算法。后续发展使模型的作用不再局限于划分可计算与不可计算的边界。有限自动机成为语言识别和电路设计的核心工具,而 20 世纪 60 年代则出现了对时间复杂度和存储复杂度的系统研究。哈特马尼斯和斯特恩斯于 1965 年发表的计算复杂性研究,体现了研究重心向资源受限计算的转移。由此,模型不仅成为确定何为计算的工具,也成为比较特定问题需要多少计算资源的工具。
自动机、纸带与存储层次
存储限制会导致计算能力的显著差异。有限状态机只有有限个内部状态,没有无界的辅助存储空间。在标准的输入读取形式下,它依次处理符号,并在读入每个符号后更新状态。它所识别的是正则语言,例如包含偶数个 符号的二进制串。当前状态可以记录奇偶性,因为无论输入有多长,都只需区分两种情况。
有限的存储空间无法保存任意多的信息。例如,没有任何有限自动机能够识别
因为要识别这种语言,就必须在检查 符号之前,区分开头 符号数量的无穷多种可能取值。这一限制并非源于硬件速度慢,也不是因为编程记法不便,而是由可区分的内部状态数量有限这一事实决定的。引入非确定性并不会扩大有限自动机能够识别的语言类别,但可能使某些自动机的描述大幅缩短。
下推自动机增加了一个无界的后进先出存储结构,在形式上相当于栈。它可以在每读入一个 时压入一个标记,在每读入一个 时弹出一个标记,从而识别上述两种符号数量相等的语言。非确定性下推自动机所识别的恰好是上下文无关语言,其中包括许多具有嵌套语法结构的语言。确定性下推自动机所识别的语言类别则更小,因此,与有限自动机的情形不同,非确定性在这里会影响识别能力。再增加一个不受限制的栈,就能大幅提升计算能力:两个栈可以分别表示读写位置两侧的纸带部分。
图灵机具有一个有限控制器和一条划分为多个单元的无界纸带。每一步,它都根据一张有限的转移表读取一个符号、写入一个符号、改变状态并移动读写头。“无界”意味着事先不设定固定的有限上限;一次会终止的计算只会使用有限多个单元。常见变体包括多纸带、多读写头以及采用不同几何结构的纸带。这些变体的可计算能力相同,但彼此模拟的开销可能相差很大。
在有限自动机与不受限制的图灵机之间,还有一些资源受限的模型,例如线性有界自动机,其可访问的纸带长度不超过输入长度的某个常数倍。这类机器将语言类别与存储限制联系起来,并且在标准的非确定性定义下,所识别的正是上下文有关语言。这一层次体系表明,讨论某个模型时,必须同时明确其存储机制和控制规则。可访问存储空间的一点小变化,就可能改变可解问题的集合;而有限控制部分即使大幅扩充,也可能不会改变这一集合。
函数式模型、递归模型与重写模型
并非所有模型都把计算描述为机器在可变存储上执行指令的过程。λ 演算通过表达式的构造与变换来描述计算。它的基本操作包括变量引用、函数抽象和函数应用。抽象 表示一个以 为参数的函数,将它应用于实参 时,可以进行 β 归约:
其中,替换操作必须避免意外捕获自由变量。计算通过归约表达式来推进,而不是通过移动读写头或更新程序计数器来推进。
无类型 λ 演算可以编码自然数、序对、条件表达式和递归行为,因此在计算能力上与图灵机等价。不过,从执行过程来看,求值顺序仍然很重要。一个表达式可能存在正规形,某种归约策略能够到达它,而另一种策略却可能一直对某个不必要且不终止的子表达式求值。丘奇–罗瑟性质实质上指出,从同一表达式出发的不同归约路径可以汇合;因此,如果正规形存在,那么除绑定变量的重命名外,它是唯一的。这并不意味着每个表达式都会终止。
递归函数模型通过构造数值函数的规则来刻画计算。原始递归根据初始值以及在较小自变量处已经算出的函数值来定义函数。每个原始递归函数都是全函数,但这一类函数并不包含所有可计算的全函数。阿克曼函数就是一个不属于此类的典型例子。加入无界极小化运算后,便得到部分递归函数,从而涵盖图灵可计算的部分函数这一一般类别。搜索可能永远找不到合适的值,这就对应于计算不终止的情形。
项重写系统推广了基于表达式的计算。一组有方向的规则将匹配的子表达式替换为新的表达式;算术化简和符号运算就是常见的例子。它有两个核心性质:终止性,即不存在无限的重写序列;合流性,即分岔的重写路径最终可以到达一个共同的结果。这两种性质相结合,构成了一种特别实用的计算框架,其中每个表达式都有唯一的不可约形式。不受限制的重写系统则可能两种性质都不具备。
这些方法深刻影响了函数式编程、符号计算和证明系统。它们也揭示了表达能力与终止保证之间的重要区别。类型系统可以排除不符合规则的程序,而某些演算还会保证每个类型正确的表达式都能终止。这类限制在证明助手中很有用,因为如果逻辑核心允许不受限制的不终止计算,就可能破坏证明所预期的解释。相比之下,通用编程语言通常允许可能不终止的递归。保证终止的演算无法表达所有可计算过程,这是一种有意施加的数学限制,未必是缺陷。
随机存取机与基本操作的成本
在常规算法分析中,与类似处理器的抽象模型相比,纸带机对数据访问的刻画往往不够直接。随机存取机由程序和可寻址的寄存器或存储单元组成。其指令通常包括读取、写入、算术运算、条件分支和间接寻址。纸带读写头必须经过中间的各个单元才能到达目标位置,而随机存取指令可以直接引用某个编号的位置。因此,这种模型很适合分析数组、图算法以及其他依赖索引访问的结构。
必须谨慎界定一条基本指令的含义。单位成本模型可以规定,无论操作数有多大,一次算术运算都只计为一步。如果寄存器能够存储任意大的整数,而且功能强大的算术运算始终只需常数成本,那么一次很短的计算就能处理二进制表示极其庞大的数值。这可能导致不切实际的复杂度估计。相比之下,对数成本模型或位成本模型让成本取决于所涉及的位数,从而将算术运算和寻址的成本纳入分析。
字长随机存取机模型提供了一种常见的折中方案。存储器由包含 位的字组成,对有界数量的字执行一组指定操作所需的时间为常数。通常, 要足够大,使其能够对大小为 的输入所涉及的存储空间进行寻址,一般要求 。许多分析取 ,另一些分析则将 保留为显式参数。是否将乘法、除法或某些位操作指令视为单位成本操作,会影响复杂度的上界和下界。
这些假设可以解释一些看似矛盾的结果。当所有键均不相同时,基于比较的排序在最坏情况下需要进行 次比较,因为必须通过比较区分 种可能的排列顺序。这个下界适用于只能通过比较获取顺序信息的模型。整数排序算法可以利用键的表示方式、数位提取或查表,因此不受这一限制。它们并没有推翻基于比较的排序下界,而是利用了另一组允许执行的操作。
随机存取还抽象掉了真实机器的一些重要特性。访问附近缓存中的值与从远处的存储器取回数据,延迟可能差别很大,尽管在简单的 RAM 分析中两者都只计为一步。存储层次结构、处理器流水线和指令级并行都可能使实际性能偏离操作次数所给出的结果。不过,只要能够揭示算法的主要结构,经过有意简化的成本模型仍然有用。其结论应当结合前提条件来理解:它们描述的是在指定的指令集、字长和成本计量规则下的执行情况,而不是对实际耗时秒数的无条件预测。
电路模型、一致性与复杂性类
布尔电路将计算表示为由导线连接逻辑门而成的有向无环网络。输入导线传递比特,逻辑门执行与、或、非等运算,输出导线则编码计算结果。电路的规模以逻辑门的数量衡量,深度则以存在依赖关系的逻辑门运算所形成的最长链衡量。规模近似反映计算所需的硬件数量或工作量;深度则反映在逻辑门可以并行运行时,关键依赖链的长度。
一个电路通常只能处理某个固定长度的输入。因此,要计算任意长度字符串上的函数,就需要一个电路族 ,为每个输入长度 配备一个电路。由此便产生了一致计算与非一致计算的区别。对于一致电路族,存在一个算法,能够在明确的资源限制下生成电路描述。对于非一致电路族,则不作这样的生成要求。因此,这类电路族可能包含任何单一有效过程都无法获得的信息。
P/poly 类由具有多项式规模电路族的判定问题组成。它的非一致性影响深远:每个一元语言都有多项式规模电路,甚至包括不可判定的一元语言,因为每个长度所对应的电路只需将相应答案硬编码进去即可。这并没有给出判定该语言的算法。缺少的环节是构造正确电路的有效方法。因此,当电路族旨在表示可执行的计算,而不只是针对各个长度分别给出的描述集合时,一致性条件至关重要。
机器模型与电路模型为复杂性理论提供了互补的定义方式。P 类通过确定性多项式时间计算来定义,而 NP 类则可以通过在多项式时间内验证长度为多项式的证书来刻画。非确定性机器给出了 NP 的另一种等价定义。P与NP问题所问的是这两个类是否相同。电路复杂性研究的是相关但不同的问题,即计算特定函数的电路所需的最小规模或最小深度。若能证明足够强的一般性电路下界,就能解决复杂性理论中的重大问题,但对于不受限制的电路,证明广泛适用的下界仍然十分困难。
模拟结果解释了为什么某些复杂性上的区分具有稳健性。在适当假设下,标准的确定性机器模型可以以多项式开销相互模拟,这支持了将多项式时间用作广义可行性概念的做法。但这种稳健性并不会自动延伸到线性运行时间与平方运行时间之类的细粒度论断。电路深度、纸带访问方式、字级算术运算以及内存访问限制,都可能改变这类界限。对于深度受限的电路,甚至逻辑门基的选择也很重要:例如,与仅使用有限形式布尔组合的常数深度电路相比,加入奇偶校验门会改变电路能够高效表达的内容。因此,任何关于复杂性的论断,都离不开其采用的计算模型和资源约定。
随机性、非确定性与量子计算
概率计算模型在普通的状态转移之外引入了随机选择。例如,概率图灵机可以按需读取相互独立、无偏的随机比特。对于每个输入,其输出和运行时间都成为随机变量。这为随机化算法提供了形式化基础,同时也将模型中的真正随机选择与伪随机数生成器提供的确定性数值区分开来。某个特定的伪随机数生成器能否充分替代随机性,取决于所采用的假设和具体应用。
对错误和运行时间的不同约定,产生了不同类别的随机化计算。蒙特卡洛算法有预先规定的资源上限,但可能以受限的概率返回错误答案。拉斯维加斯算法只要返回答案,答案就一定正确,但其运行时间是随机的。BPP 类采用多项式时间的概率计算,允许双侧错误,且错误概率须与二分之一保持一定差距,通常规定至多为 。通过独立重复运行并采用多数表决,可以使错误概率呈指数级下降。具体常数 并非关键;关键在于错误概率与二分之一之间的差距。
随机化计算与非确定性计算的区别在于接受规则。非确定性多项式时间机器只要有一条分支接受就会接受,即使这条分支在所有分支中所占的比例呈指数级微小。随机化多项式时间算法则需要以足够高的概率产生正确结果。因此,随机猜测证书通常不能将 NP 验证过程转化为高效的有界错误算法。这两种模型描述的是不同的资源,不能仅仅因为它们都涉及多条可能的执行路径,就将二者等同起来。
量子计算机使用受量子力学支配的状态。在基于量子门的描述中, 个量子比特的状态可表示为
量子电路对这一状态施加允许的量子门操作和测量。振幅并不是普通的分支概率:振幅之间可以发生干涉,而一次测量只能得到一个结果,其分布由相应振幅的模平方决定。振幅的数量呈指数级增长,并不意味着可以高效地读出其中编码的全部信息。
在采用标准的一致性和量子门近似约定时,BQP 是有界错误多项式时间计算在量子计算中的对应复杂性类。1994 年公布的肖尔算法给出了求解整数因数分解和离散对数问题的多项式时间量子算法。格罗弗算法则为无结构搜索的查询复杂度带来了平方级改进。这两种算法都不能证明量子计算机能够高效求解 NP 中的所有问题。在操作可被有效指定、输入和输出均为通常的有限形式的条件下,标准量子计算并不超越图灵可计算性的范围;其意义在于资源需求,而不在于产生了一类新的可有效计算函数。
并行、分布式与交互式模型
顺序模型将计算表示为单一、有序推进的过程,但许多系统都包含多个同时活动的组件。并行随机存取机(PRAM)将一组访问共享内存、同步运行的处理器理想化。其各种变体的区别在于是否允许并发读写,以及如何处理同时发生的写入。这些选择会影响算法设计:如果允许采用强大的规则来合并并发写入,那么某些任务就可能比在独占访问条件下更容易完成。
并行复杂性区分总工作量与实际经过的并行时间。如果一个算法总共执行 次操作,且其依赖链长度为 ,那么在相应的理想化单位成本假设下,用 个处理器执行该算法所需的时间至少为
第一个下界反映了处理能力的限制;第二个下界则反映了增加处理器也无法消除的依赖关系。这种工作量—深度视角有助于区分真正的并行算法与仅仅分配到多个处理器上执行的顺序算法。
分布式计算模型更强调通信、局部性以及各进程掌握的信息并不完整。进程可以通过消息传递或共享内存进行通信。同步模型假定执行过程受已知的时间界限约束;异步模型则不对进程的相对速度或消息延迟施加固定界限。故障假设可以包括崩溃、消息丢失或任意的错误行为。网络拓扑以及是否提供进程标识符,也可能改变系统所能实现的目标。
这些假设对分布式共识具有决定性影响。1985 年发表的费舍尔—林奇—帕特森结果表明,在该定理的标准条件下,对于一个完全异步的消息传递系统,只要允许哪怕一个进程发生崩溃故障,就无法保证确定性共识算法终止。这并不是说实用的共识服务不可能实现。系统可以采用部分同步、随机化、额外的故障信息或更弱的保证。该定理指出的是:在一个精确定义的模型中,某组要求无法同时满足。
交互式模型将研究范围扩展到那些并非接收一个完整输入、最终返回一个输出的计算。操作系统、网络服务器或控制器可能持续不断地响应传入事件。进程演算,包括通信系统演算和 π 演算,用于描述组合、同步以及不断演变的通信结构。正确性可以涉及可观察轨迹、安全性性质,或所要求的响应最终是否会发生。交互将研究的数学对象从有限输入上的函数转变为持续进行的行为,但这本身并不能证明计算超出了丘奇—图灵框架。还必须明确规定环境的能力及其交互规则。
数据访问、通信与专门资源模型
有些模型刻意忽略大部分内部计算,以便单独考察某一种开销高昂的资源。在通信复杂度中,两个或多个参与方各自持有输入的不同部分,必须在交换尽可能少的比特的同时,共同计算一个函数。局部计算通常不计成本。对于分别持有的两个 位字符串,确定性的相等性检验在最坏情况下需要的通信量与 成线性关系。借助共享的公共随机性,指纹法可以实现有界错误的相等性检验,其通信量取决于目标错误率,而不再随输入长度线性增长。这一对比揭示的是随机性对通信的影响,而非对局部处理器速度的影响。
单元探测模型同样将关注点集中在内存访问上。数据结构存储在具有指定字长的存储单元中,一次操作的成本就是读写的单元数。两次探测之间的计算不计成本。这一模型中的下界可能尤其有力,因为仅仅将缓慢的算术运算替换为更快的指令,并不能绕过这类下界。字长仍然至关重要:如果允许一个单元容纳任意多的信息,许多存储和查询问题就会变得微不足道。
对于规模超过主存容量的数据,外存模型衡量的是大小为 的快速内存与更大的存储系统之间的数据传输量,每次传输以包含 个数据项的块为单位。扫描 个连续数据项需要的块传输次数为 量级。在通常的参数范围内,高效比较排序的外存开销由下式决定:
对于小规模实例,则需采用适当的约定。这解释了为什么在数据搬移占主导地位时,仅仅尽量减少常规操作次数,仍可能导致较差的性能。
流式模型在按顺序提供输入的同时限制内存使用,通常只允许遍历一遍。需要精确结果的任务可能必须存储几乎全部输入,而近似与随机化则可能使紧凑摘要成为可能。例如,估计数据流中不同元素数量的算法,会使用概率型草图,而不是保留每一个元素。模型必须明确:更新是否只能插入数据项,还是也能删除数据项;是否允许多遍扫描;以及要求何种误差保证。这些区别对于流处理和大规模数据分析至关重要。
查询模型统计对输入访问机制或黑箱的调用次数,同时另行处理其他操作。它们有助于证明搜索和决策树的下界,也可用于比较经典计算与量子计算对同一抽象问题的访问方式。预言机模型则更进一步,允许在一步之内获得某个指定问题的答案,从而研究相对于额外信息源的计算。这类模型是分析工具,并不意味着其中的预言机能够被实际构建。它们的价值在于将信息获取与后续计算分离,并揭示究竟是哪一种资源决定了某个界限。
模拟、物理理想化与抽象的局限
比较不同模型,需要精确定义模拟的含义。如果一个模型能够重现另一个模型经过编码的配置和状态转移,同时保持相关结果,就称前者能够模拟后者。对于可计算性,核心问题在于能否计算出相同的函数。对于复杂性,还必须对时间、空间或通信方面的额外开销加以限制。图灵完备性表达的是在适当理想化条件下的通用计算能力;它并不意味着模拟是高效的、编程是容易的,也不意味着实践中可以获得无限的存储空间。
每一种通用模型都会对物理资源作出理想化假设。图灵机具有潜在无界的存储空间,而任何实际造出的设备,其内存都是有限的。对于一台固定的有限数字设备,只要描述足够细致,就可以将其表示为有限状态系统。无界模型的价值在于,它能够描述可扩展的计算过程,而无须预先设定某一种硬件容量。这样便能区分算法本身固有的限制与特定机器规模所造成的限制。
模拟计算模型和实数计算模型体现了另一种理想化。1989 年提出的 Blum–Shub–Smale 模型研究在实数等数学结构上运算的机器,通常将精确算术运算视为基本操作。这为代数复杂性提供了严格的框架,但精确的实数值可能包含无限多的信息。同样,分析模拟动力系统时,也可能采用连续状态和精确的演化过程。有关计算能力的结论取决于允许使用哪些常数、如何编码输入、能够测量什么,以及提高精度是否需要付出代价。如果一个模型假定能够精确访问任意不可计算实数,它就引入了常规有效过程无法获得的信息。
超计算的各种方案研究超越图灵可计算性的模型,例如假定在有限时间内完成无限次操作,或使用特殊的无限对象及其他非标准资源。即使尚未证明所需机制在物理上可实现,也可以研究这些模型的数学性质。因此,关于物理系统能够计算什么的物理丘奇—图灵论题,应当与原本讨论有效计算的丘奇—图灵论题区分开来。进一步声称经典机器能够高效模拟一切物理上可实现的计算,则是更强的主张,而且面临量子计算带来的挑战。
在应用中,模型的选择通常取决于所研究的性质。形式验证可以将系统抽象为状态和状态转移,使某项安全性性质能够通过模型检测来检验。性能分析则可能保留内存传输或通信延迟,而省略与成本无关的逻辑细节。适合用于证明功能正确性的抽象,未必能够刻画时序信息泄漏、调度行为或精度误差。因此,结论是否有效,不仅取决于模型内部的证明,还取决于所选模型是否保留了该结论所依赖的特征。