ライスの定理

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/09/20 08:37 UTC 版)

ライスの定理に類する結果

ライスの定理は、帰納的可算集合 (recursively enumerable sets) を決定可能なやりかたで二分することの不可能性について述べたものと考えられる。^[3] この定理のバリエーションとして、帰納的可算集合のかわりに帰納的集合 (recursive sets; 計算可能集合) を考えたものもある。これらの結果の類似性はそれぞれの定理が以下の主張をしていることから言える。

もともとのライスの定理は、「ある帰納的可算集合のクラスが"決定可能"ならば、与えられた帰納的可算集合がそのクラスに属するかどうかを判定するためには、ゼロ個の $i$ について、 $i$ がその集合に属するかどうかを調べればよい」ことを主張する。
帰納的集合にかんする定理は、「ある帰納的集合のクラスが"決定可能"ならば、与えられた帰納的集合がそのクラスに属するかどうかを判定するためには、有限個の $i$ について、 $i$ がその集合に属するかどうかを調べればよい」ことを主張する。

類似定理のフォーマルな記述は省略する。^[4] ^[5] (詳細は英文記事参照。)

この結果は、協力ゲーム理論あるいは社会選択理論といった分野において、シンプルゲームの中村ナンバーの考察などに応用されている (Kumabe and Mihara, 2008,^[5] 2008^[6])。

ライスの定理を精緻化したものとしてライス＝シャピロの定理がある。この定理はインデックス集合が帰納的可算である為にはある種の有限性を持つことが必要（かつ十分）であることを示す。

脚注

^ 厳密には、Fは関数空間の部分集合Yを使って「f_AはYの元である」の形に書ける性質。
^ あるプログラムAが存在してf=f_Aと書ける関数fの事を計算可能関数という。Fが自明であるとは、厳密には、「任意の計算可能関数fに対し、fはFを満たす」と「任意の計算可能関数fに対し、fはFを満たさない」の事である。
^ $C$ を帰納的可算集合のクラスとするとき、計算可能な関数にたいするライスの定理で、 $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ というクラスを考えればよい。ただし ${\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ は $\phi _{e}$ の定義域であり、あらゆる帰納的可算集合は適当な $e$ を選ぶことにより ${\textrm {dom}}\,\phi _{e}$ と書くことが出来る。
^ Kreisel, G., Lacombe, D., Shoenﬁeld, J.R., 1959. Partial recursive functionals and effective operations. In: Heyting, A. (Ed.), Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, pp. 290–297.
^ ^a ^b Kumabe, Masahiro; Mihara, H. Reiju (2008). “Computability of simple games: A characterization and application to the core”. Journal of Mathematical Economics 44 (3-4): 348–366. doi:10.1016/j.jmateco.2007.05.012. ISSN 03044068.
^ Kumabe, Masahiro; Mihara, H. Reiju (2008). “The Nakamura numbers for computable simple games”. Social Choice and Welfare 31 (4): 621–640. doi:10.1007/s00355-008-0300-5. ISSN 0176-1714.