計算模型 (數學)

  關於以計算機模型模擬複雜系統，請見「計算模型」。

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