ライスの定理に類する結果
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/29 18:36 UTC 版)
「ライスの定理」の記事における「ライスの定理に類する結果」の解説
ライスの定理は、帰納的可算集合 (recursively enumerable sets) を決定可能なやりかたで二分することの不可能性について述べたものと考えられる。この定理のバリエーションとして、帰納的可算集合のかわりに帰納的集合 (recursive sets; 計算可能集合) を考えたものもある。これらの結果の類似性はそれぞれの定理が以下の主張をしていることから言える。 もともとのライスの定理は、「ある帰納的可算集合のクラスが"決定可能"ならば、与えられた帰納的可算集合がそのクラスに属するかどうかを判定するためには、ゼロ個の i {\displaystyle i} について、 i {\displaystyle i} がその集合に属するかどうかを調べればよい」ことを主張する。 帰納的集合にかんする定理は、「ある帰納的集合のクラスが"決定可能"ならば、与えられた帰納的集合がそのクラスに属するかどうかを判定するためには、有限個の i {\displaystyle i} について、 i {\displaystyle i} がその集合に属するかどうかを調べればよい」ことを主張する。 類似定理のフォーマルな記述は省略する。(詳細は 英文記事参照。) この結果は、 協力ゲーム理論あるいは社会選択理論といった分野において、シンプルゲームの中村ナンバーの考察などに応用されている (Kumabe and Mihara, 2008, 2008)。 ライスの定理を精緻化したものとしてライス＝シャピロの定理がある。この定理はインデックス集合が帰納的可算である為にはある種の有限性を持つことが必要（かつ十分）であることを示す。
※この「ライスの定理に類する結果」の解説は、「ライスの定理」の解説の一部です。
「ライスの定理に類する結果」を含む「ライスの定理」の記事については、「ライスの定理」の概要を参照ください。
- ライスの定理に類する結果のページへのリンク
