計算可能性理論 (Computability Theory)

計算可能性理論は、どの問題がアルゴリズムで解けるか、解ける場合にどの資源が必要かを形式的に扱う。チューリング機械などの計算モデルを用い、モデルが違っても同じ計算可能関数の範囲を比較する。

問題を言語や関数として定義し、停止問題・帰着・対角化などを使って可解性を調べる。実装上の「難しい」と、原理的にアルゴリズムが存在しないことを混同しない。

計算可能性は現実の性能保証ではない。決定可能な問題でも指数時間なら規模に耐えず、近似、制約、ヒューリスティック、対話的な人間判断が必要になる。