Portal:数学/特集項目/1

計算可能性理論（computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。計算機科学の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし、多大な計算資源を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。