decidability

decidabilityは主に計算機科学や数理論理学の文脈で使用される専門用語です。ある問題に対して、どのような入力が与えられたとしても、それがはいかいいえかを有限時間内に正しく判定できるアルゴリズムが存在する場合、その問題は決定可能であると言えます。単に答えが出ることではなく、必ず停止して結論を出す手法が数学的に保証されているかどうかが重要なポイントです。

決定不能性と計算限界

この概念と対照的なのが undecidability（決定不能性）です。最も有名な例はhalting problem（停止問題）であり、任意のプログラムが停止するかどうかを判定する汎用的なアルゴリズムは存在しないことが証明されています。このように、decidabilityを議論することは、コンピューターで解決可能な問題の限界を定義することに繋がります。

論理学における適用

計算機科学以外では、形式論理においてある命題がその体系の中で証明可能か、あるいは否定可能かを判定できる性質を指します。例えば、命題論理は決定可能ですが、一次述語論理は一般に決定不能であるとされています。このように、decidabilityは単なる解決できるかという日常的な意味ではなく、厳密なアルゴリズム的手続きの存在を指す言葉として使い分ける必要があります。