ライス＝シャピロの定理

ウィキペディア

ライス＝シャピロの定理

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

計算可能性理論において、ライス＝シャピロの定理（英: Rice-Shapiro theorem）とはライスの定理の一般化した定理である。名称は Henry Gordon Rice と Norman Shapiro に因む。

非形式的な言明

定理の主張は非形式的には次のように述べられる： 計算可能関数の半決定可能な述語 A と、計算可能関数 f が与えられたとき、 f が A を満たす為には、f の有限部分で A を満たすものが存在することが必要十分である。いま f が A を満たしていると仮定しよう。するとライス＝シャピロの定理より f の有限部分 g が存在して A を満たす。このとき g の任意の計算可能な延長関数もまた A を満たす。したがって計算可能関数の無限個の入出力が真偽の決定に関与するような述語は帰納的可算ではありえない。

形式的な言明

いま A を（1変数）部分帰納的関数の集合で、指標の集合 $\mathrm {Index} (A)=\{e\mid \varphi _{e}\in A\}$ この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。