決定可能性 (Decidability)

決定可能性とは、ある問題の任意の入力に対して、有限時間で正誤を必ず返して停止するアルゴリズムが存在する性質である。個別の入力を解けることや、実用的な速度で解けることとは異なる。

問題を形式化し、入力の集合・期待する判定・停止性を明示する。決定手続きがある場合は正しさと停止を示し、ない場合は停止性を利用した矛盾や既知の帰着によって限界を示す。

決定可能でも計算量が大きければ実務上は使えない。逆に、有限範囲・近似・制約付き入力に限定すると、元の問題が決定不能でも有用な自動化が可能になる。