计算模型 (数学)
在computability theory和computational complexity theory中，计算模型（model of computation）是计算中允许使用的运算集及各自成本的定义。它是用于测量一个algorithm在execution time和/或memory space上的复杂度。通过假定一个计算模型，可能分析出所需的计算资源或讨论算法或计算机的限制。
模型
模型例如：
- Turing Machine
- Finite state machines
- Recursive functions
- Lambda calculus
- Combinatory logic
- Cellular automaton
- 抽象重写系统
使用
在算法的运行时分析领域，它通常用于定义一个具有单位成本运算的计算模型，或者只有单位成本运算。 一个常见例子是random access machine，它具有读取和写入其所有存储单元的单位成本。在这方面，它与上述图灵机模型不同。
在模型驱动工程中，计算模型解释了整个系统的行为，包括每个组件的行为与结果。
一个经常被忽略的关键点是，被公布的问题的下限经常是由比实践中可使用的运算集更不受限制的计算模型得出，因而可能天真地存在还会有更快算法的想法。[1]
分类
有着许多计算模型，它们在容许的运算集和它们的计算成本方面存在不同。它们可以被分为几大类：abstract machine 和相当于它的模型（例如 lambda calculus 相当于Turing machine），用于可计算性的证明和算法计算复杂性的上限；还有决策树模型，用于证明算法问题计算复杂度的下限。
参见
- Stack machine（零操作数机器）
- Accumulator machine（一操作数机器）
- Register machine（二、三、…操作数机器）
- Random access machine
- 细胞探针模型
参考资料
- ^ 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. Models Of Computation: Exploring the Power of Computing. 1998.