圖靈機和可計算性

所有數學問題都可以用計算機來解決嗎？

如上一篇 ，海狸是否會陷入無法停機的無限循環？這個看似簡單的數學問題就無法完全用計算機來徹底解決，或者說它是不可計算的。

可計算性Computability/Calculability

可計算性是指某個數學問題是否可以用計算機在有限步驟內徹底解決。

首先必須是數學問題，而不能是給我做個漢堡包這種需要真實的實體變化的問題。

其次必須是有限步驟，如果這個問題的算法遠遠超過計算機目前可能擁有的計算能力，那麼也應該視為不可計算的。

研究問題的可計算性質可以避免浪費時間在無底的坑裡面做無意掙扎。

關於問題

可計算性是針對問題而言的，問題又主要是以下兩類：

1. 判定問題Decision Problem。判定問題就是回答是或否的問題。一個典型的決策問題是：大數據集U及其子集S，元素u屬於大數據集U，判斷u是否屬於子集S。比如自然數中的n是否屬於質數，這就是一個判定問題，當然我們可以採用試除算法來判定

不可判定就是已經確定無法對這種問題進行正確回答，要麼答不對，要麼陷入死循環永遠答不出。比如繁忙海狸中的停機問題就是一個不可判定問題。

1. 功能問題Function Problem。功能問題比判定問題更復雜，不能只回答是或否，可能需要回答一個數字，比如關於一個自然數的因數個數，或者地圖導航到某地最近路線是哪條，這種問題的答案就需要一個數字或一條路徑才行。

另外還有搜索問題Search Problem(在對象Y中是否能夠找到符合要求的結構x)和最優化問題Optimization Problem(多個解決方案中哪一個更優）。

計算模型Model of computation

圖靈機是一種抽象的計算模型，理論上可以實現無限多種算法，類似的計算模型（功能模型Functional models）還有以下幾個，他們都被認為是圖靈等價或圖靈完整Turing completeness的：

• λ演算Lambda calculus，λ-calculus。阿隆佐·邱奇Alonzo Church在20世紀20~30年代發明。
• 組合邏輯Combinatory logic。摩西·施菲克爾Moses Schönfinkel和哈斯克爾庫裡Haskell Curry在20世紀20~30年代發明。
• μ-遞歸函數μ-recursive functions。μ音miu。最早在1934年由哥德爾提出。1967年，馬文閔斯基指出μ-遞歸函數與圖靈機等價。
• 寄存器機Register machine。由馬文閔斯基和其他幾位科學家幾乎同時在1961年發明。

可計算理論

如上所示，遞歸理論起源於20世紀30年代，由庫爾特·哥德爾KurtGödel，阿隆佐·邱奇Alonzo Church，羅莎·培特RózsaPéter，阿蘭·圖靈Alan Turing，斯蒂芬·克萊尼Stephen Kleene和埃米爾·珀斯特Emil Post等人提出。

早在1936年就邱奇和圖靈就受到哥德爾的不完備性定理的啟發，算法程序不可能正確的判斷任意數學問題的真假。後來這個理論就被稱為Church-Turing論文，定義了可計算概念的含義：可由算法計算的函數都是可計算函數。

可計算性的提出，也意味著科學家們對不可計算問題的認可，證明了數學中確實存在無法有效解決的問題。

此外還有描述可計算程度的相對可計算性Relative computability 和圖靈度Turing degrees。