ライスの定理
出典: フリー百科事典『ウィキペディア(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を使って「fAはYの元である」の形に書ける性質。
- ^ あるプログラムAが存在してf=fAと書ける関数fの事を計算可能関数という。Fが自明であるとは、厳密には、「任意の計算可能関数fに対し、fはFを満たす」と「任意の計算可能関数fに対し、fはFを満たさない」の事である。
- ^ を帰納的可算集合のクラスとするとき、 計算可能な関数にたいするライスの定理で、というクラスを考えればよい。 ただし は の定義域であり、 あらゆる帰納的可算集合は適当な を選ぶことにより と書くことが出来る。
- ^ Kreisel, G., Lacombe, D., Shoenfield, 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.
- ライスの定理のページへのリンク