|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
計算可能性理論において、ライス＝シャピロの定理（）とはライスの定理の一般化した定理である。名称は Henry Gordon Rice と Norman Shapiro に因む。 ==非形式的な言明== 定理の主張は非形式的には次のように述べられる： 計算可能関数の半決定可能な述語 ''A'' と、計算可能関数 ''f'' が与えられたとき、 ''f'' が ''A'' を満たす為には、''f'' の有限部分で ''A'' を満たすものが存在することが必要十分である。いま ''f'' が ''A'' を満たしていると仮定しよう。するとライス＝シャピロの定理より ''f'' の有限部分 ''g'' が存在して ''A'' を満たす。このとき ''g'' の任意の計算可能な延長関数もまた ''A'' を満たす。したがって計算可能関数の無限個の入出力が真偽の決定に関与するような述語は帰納的可算ではありえない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ライス＝シャピロの定理」の詳細全文を読む スポンサード リンク
|