可計算性

可計算性（Computability）是指一個實際問題是否可以使用計算機來解決。從廣義上講如「為我烹製一個漢堡」這樣的問題是無法用計算機來解決的（至少在目前）。而計算機本身的優勢在於數值計算，因此可計算性通常指這一類問題是否可以用計算機解決。事實上，很多非數值問題（比如文字識別，圖象處理等）都可以通過轉化成為數值問題來交給計算機處理，但是一個可以使用計算機解決的問題應該被定義為「可以在有限步驟內被解決的問題」，故哥德巴赫猜想這樣的問題是不屬於「可計算問題」之列的，因為計算機沒有辦法給出數學意義上的證明，因此也沒有任何理由期待計算機能解決世界上所有的問題。分析某個問題的可計算性意義重大，它使得人們不必浪費時間在不可能解決的問題上（因而可以儘早轉而使用除計算機以外更加有效的手段），集中資源在可以解決的問題上。