计算模型 (数学)

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

在可计算性理论和計算複雜性理論中，计算模型（model of computation）描述了如何根据一组输入值计算得出输出值，也包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量一个算法在时间和/或空间上的复杂度。通过计算模型的抽象化总结，我们可以分析出算法的性能，而避免在具体程序层面，被不同的技术和实现方式造成的性能差异所误导。

模型

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

顺序模型：

• 图灵机
• 有限状态机

函数式模型：

• 递归函数
• Λ演算
• 组合子逻辑
• 細胞自動機
• 抽象重写系统（英语：Abstract rewriting system）

使用

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

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

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

分类

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

参见

• 堆疊結構機器（零操作数机器）
• 累加器（一操作数机器）
• 寄存器机（二、三、…操作数机器）
• 隨機存取機器
• 细胞探针模型（英语：Cell-probe model）

参考资料

1. Examples of the price of abstraction? （页面存档备份，存于互联网档案馆）, cstheory.stackexchange.com

拓展阅读

• 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. . 1998 [2016-12-23]. （原始内容存档于2016-10-12）.