13/11/15 21:49:09.92
>>495
URLﾘﾝｸ(ja.wikipedia.org)
数学と計算機科学において、「決定不能」という言葉には二つの異なった意味がある。
一つ目は証明論の文脈でゲーデルの定理に関連して使われる意味であり、特定の形式的体系の下で或る命題を証明も否定の証明もできないことを言う。
二つ目は（本項では詳述しないが）計算可能性理論に関連した用法であり、命題ではなく決定問題に適用される。
決定問題とは答が YES か NO のいずれかになるような問題の可算無限集合である。ある問題集合に含まれる全ての問題に正しく解答するような計算可能関数が存在しないとき、そうした問題は決定不能であると言う。