テンプレート:Portal:コンピュータ/特集項目

計算可能性理論（computability theory）では、チューリング機械などの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる。計算理論や数学の一分野である。

計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能函数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は計算可能函数またはより大きな問題クラスを主に扱う。

計算機科学の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし、多大な計算資源を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。

計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。言語として、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。……もっと読む