ライスの定理と算術的階層
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
「再帰理論」の記事における「ライスの定理と算術的階層」の解説
ライスの定理は、すべての自明でないクラス C（帰納的可算集合からなるクラスであって空でも全体でもないもの）において、インデックス集合 E = {e: e番目の帰納的可算集合 We が C に含まれる} を考えると、停止問題かその補問題が E に多対一還元可能という属性を持つことを示す。しかし、このようなインデックス集合の多くは停止問題以上に複雑である。このような集合は算術的階層によって分類される。例えば、すべての有限集合のクラスのインデックス集合 FIN の階層レベルは Σ2、すべての帰納的集合のクラスのインデックス集合 REC の階層レベルは Σ3、すべての補有限集合のクラスのインデックス集合 COFIN の階層レベルは Σ3、すべてのチューリング完全な集合のクラスのインデックス集合 COMP の階層レベルは Σ4 である。
※この「ライスの定理と算術的階層」の解説は、「再帰理論」の解説の一部です。
「ライスの定理と算術的階層」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
ウィキペディア小見出し辞書の「ライスの定理と算術的階層」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ライスの定理と算術的階層のページへのリンク
