邱奇-圖靈論題
維基百科,自由的 encyclopedia
邱奇-圖靈論題(英語:Church–Turing thesis,又稱邱奇-圖靈猜想,邱奇論題,邱奇猜想,圖靈論題)是一個關於可計算性理論的假設。該假設論述了關於函數特性的,可有效計算的函數值(用更現代的表述來說--在算法上可計算的)。簡單來說,邱奇-圖靈論題認為「任何在算法上可計算的問題同樣可由圖靈機計算」。
20世紀上半葉,對可計算性進行公式化表示的嘗試有:
- 美國數學家阿隆佐·邱奇創建了稱為λ演算的方法來定義函數。
- 英國數學家阿蘭·圖靈創建了可對輸入進行運算的理論機器模型,現在被稱為通用圖靈機。
- 邱奇以及數學家史蒂芬·科爾·克萊尼和邏輯學家J. Barkley Rosser(英語:J. Barkley Rosser)一起定義了一類函數, 這種函數的值可使用遞歸方法計算。
這三個理論在直覺上似乎是等價的--它們都定義了同一類函數。因此,計算機科學家和數學家們相信,可計算性的精確定義已經出現。邱奇-圖靈論題的非正式表述說:如果某個算法是可行的,那這個算法同樣可以被圖靈機,以及另外兩個理論所實現。
雖然這三個理論被證明是等價的,但是其中的前提假設--「能夠有效計算」是一個模糊的定義。因此,雖然這個假說已接近完全,但仍然不能由公式證明。