所有數學問題都可以用計算機來解決嗎？
如 上壹篇繁忙的海貍Busy beaver 中所展示的，海貍是否會陷入無法停機的無限循環？這個看似簡單的數學問題就無法完全用計算機來徹底解決，或者說它是不可計算的。
可計算性是指某個數學問題是否可以用計算機 在有限步驟內徹底解決 。
首先必須是數學問題，而不能是 給我做個漢堡包 這種需要真實的實體變化的問題。
其次必須是有限步驟，如果這個問題的算法遠遠超過計算機目前可能擁有的計算能力，那麽也應該視為不可計算的。
研究問題的可計算性質可以避免浪費時間在無底的坑裏面做無意掙紮。
可計算性是針對問題而言的，問題又主要是以下兩類：
另外還有 搜索問題Search Problem (在對象Y中是否能夠找到符合要求的結構x)和 最優化問題Optimization Problem (多個解決方案中哪壹個更優）。
圖靈機是壹種抽象的計算模型，理論上可以實現無限多種算法，類似的計算模型（功能模型Functional models）還有以下幾個，他們都被認為是 圖靈等價或圖靈完整Turing completeness 的：
如上所示，遞歸理論起源於20世紀30年代，由庫爾特·哥德爾KurtG?del，阿隆佐·邱奇Alonzo Church，羅莎·培特RózsaPéter，阿蘭·圖靈Alan Turing，斯蒂芬·克萊尼Stephen Kleene和埃米爾·珀斯特Emil Post等人提出。
早在1936年就邱奇和圖靈就受到哥德爾的不完備性定理的啟發，算法程序不可能正確的判斷任意數學問題的真假。後來這個理論就被稱為Church-Turing論文，定義了可計算概念的含義：可由算法計算的函數都是可計算函數。
可計算性的提出，也意味著科學家們對不可計算問題的認可，證明了數學中確實存在無法有效解決的問題。
此外還有描述可計算程度的相對可計算性Relative computability 和圖靈度Turing degrees。
END