计算模型 (数学)

关于以计算机模型模拟复杂系统，请见“计算模型”。

在可计算性理论和计算复杂性理论中，计算模型（model of computation）描述了如何根据一组输入值计算函数的输出，包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量算法的计算复杂度，总结出算法的性能，而不受特定技术和实现方式的性能差异所误导。

模型

计算模型可分为三大类：顺序模型、函数式模型以及同步模型。

顺序模型

顺序模型包括

• 图灵机
• 有限状态机
• 下推自动机

函数式模型

函数式模型包括

• 递归函数
• Λ演算
• 组合子逻辑
• 细胞自动机
• 抽象重写系统

同步模型

同步模型包括

• 演员模型

各模型的表现不尽相同；例如，有限状态机可以计算的函数，图灵机也可以计算，反之亦然。

使用

在算法分析领域，定义一个计算模型通常用具有单位成本的原始操作（也称单位成本操作）。一个常见例子是随机存取机器，任何存储单元的读写访问，都有着单位成本。在这方面，它与图灵机模型不同。

在模型驱动工程中，计算模型解释了整个系统的行为是如何由每个组件的行为所共同造成的。

一个经常被忽略的关键点是，一些已知计算复杂度下限的问题是由较为局限的运算集得出的，实践中可使用的运算集可能更加广泛而强大，因而一些算法的实际性能，可能比高度抽象的计算模型得出的结果要好。

分类

计算模型有很多，它们在各自容许的运算集和计算成本方面不同。它们可以被分为几大类：抽象机器和与其等同的模型（例如Λ演算相当于图灵机），用于可计算性、算法计算复杂性上限的证明；还有决策树模型，用于证明算法问题计算复杂度的下限。

参见

• 堆栈结构机器（零操作数机器）
• 累加器（一操作数机器）
• 寄存器机（二、三、…操作数机器）
• 随机存取机器
• 细胞探针模型

拓展阅读

• Fernández, Maribel. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. 2009. ISBN 978-1-84882-433-1. 
• Savage, John E. Models Of Computation: Exploring the Power of Computing. 1998 [2016-12-23]. （原始内容存档于2016-10-12）.