可計算性

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

參見