ライスの定理

ウィキペディア

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

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

参考文献

Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.

外部リンク

Eric W. Weisstein, Rice's Theorem at MathWorld.

脚注

^ 厳密には、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.