計算模型 (數學)

在可計算性理論和計算複雜性理論中，計算模型（model of computation）描述了如何根據一組輸入值計算函數的輸出^[1]，包含了負責運算、存儲和通訊等結構的具體組織方式。它可以用於測量算法的計算複雜度，總結出算法的性能，而不受特定技術和實現方式的性能差異所誤導。

模型

計算模型可分為三大類：順序模型、函數式模型以及同步模型。

順序模型包括

函數式模型包括

同步模型包括

各模型的表現不盡相同；例如，有限狀態機可以計算的函數，圖靈機也可以計算，反之亦然。

在算法分析領域，定義一個計算模型通常用具有單位成本的原始操作（也稱單位成本操作）。一個常見例子是隨機存取機器，任何存儲單元的讀寫訪問，都有着單位成本。在這方面，它與圖靈機模型不同。

在模型驅動工程中，計算模型解釋了整個系統的行為是如何由每個組件的行為所共同造成的。

一個經常被忽略的關鍵點是，一些已知計算複雜度下限的問題是由較為局限的運算集得出的，實踐中可使用的運算集可能更加廣泛而強大，因而一些算法的實際性能，可能比高度抽象的計算模型得出的結果要好。^[2]

計算模型有很多，它們在各自容許的運算集和計算成本方面不同。它們可以被分為幾大類：抽象機器和與其等同的模型（例如Λ演算相當於圖靈機），用於可計算性、算法計算複雜性上限的證明；還有決策樹模型（英語：Decision tree model），用於證明算法問題計算複雜度的下限。

^ 计算模型 (PDF). [2024-01-09]. （原始內容存檔 (PDF)於2024-03-29）.
^ 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 [2016-12-23]. （原始內容存檔於2016-10-12）.