丘奇-圖靈論題

丘奇-圖靈論題（以前通常簡稱為丘奇論題）指出，任何現實世界的計算都可以轉化為涉及圖靈機的等效計算。在丘奇最初的表述（Church 1935, 1936）中，該論題指出，現實世界的計算可以使用λ演算來完成，這等同於使用一般遞迴函式。

丘奇-圖靈論題涵蓋了比最初設想的更多種類的計算，例如涉及元胞自動機、組合子、暫存器機和替換系統的計算。它也適用於理論計算機科學中發現的其他型別的計算，例如量子計算和機率計算。

關於丘奇-圖靈論題存在相互矛盾的觀點。一種觀點認為它可以被證明，另一種觀點認為它作為計算的定義。從未有過證明，但其有效性的證據來自於這樣一個事實：迄今為止發現的每一種現實的計算模型都被證明是等效的。如果存在一種裝置可以回答圖靈機無法回答的問題，那麼它將被稱為預言機。

對於不同的任務，一些計算模型在計算時間和記憶體方面更有效率。例如，據推測，與現代計算機相比，量子計算機可以在較低的時間複雜度下執行許多常見任務，因為對於足夠大版本的這些問題，量子計算機解決問題的速度將比普通計算機更快。相比之下，存在一些問題，例如停機問題，普通計算機無法回答，並且根據丘奇-圖靈論題，沒有其他計算裝置可以回答這樣的問題。

丘奇-圖靈論題已被斯蒂芬·沃爾夫勒姆在他的計算等效原理（Wolfram 2002）中擴充套件為一個關於自然世界過程的命題，該原理還聲稱，在系統達到通用性之前，只有少數幾個中間計算能力級別，並且大多數自然系統都是通用的。