计算模型 (数学)

在可计算性理论和計算複雜性理論中，计算模型（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.