計算可能性との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 10:10 UTC 版)
決定可能集合の概念と同様、決定可能な理論や論理体系の定義は、「実効的方法 (effective method)」や「計算可能関数 (computable function)」によって与えられる。これらは一般にチャーチ＝チューリングのテーゼと等しいと見なされている。実際、論理体系や理論が決定不能であるという証明は、計算可能性の形式定義を使い、ある適当な集合が決定可能集合ではないことを示し、チャーチのテーゼを使って、その理論や論理体系が実効的方法では決定可能でないことを示す。
※この「計算可能性との関係」の解説は、「決定可能性」の解説の一部です。
「計算可能性との関係」を含む「決定可能性」の記事については、「決定可能性」の概要を参照ください。
ウィキペディア小見出し辞書の「計算可能性との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 計算可能性との関係のページへのリンク
