非形式的な言明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/01/07 02:51 UTC 版)
「ライス＝シャピロの定理」の記事における「非形式的な言明」の解説
定理の主張は非形式的には次のように述べられる： 計算可能関数の半決定可能な述語 A と、計算可能関数 f が与えられたとき、 f が A を満たす為には、f の有限部分で A を満たすものが存在することが必要十分である。いま f が A を満たしていると仮定しよう。するとライス＝シャピロの定理より f の有限部分 g が存在して A を満たす。このとき g の任意の計算可能な延長関数もまた A を満たす。したがって計算可能関数の無限個の入出力が真偽の決定に関与するような述語は帰納的可算ではありえない。
※この「非形式的な言明」の解説は、「ライス＝シャピロの定理」の解説の一部です。
「非形式的な言明」を含む「ライス＝シャピロの定理」の記事については、「ライス＝シャピロの定理」の概要を参照ください。
ウィキペディア小見出し辞書の「非形式的な言明」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 非形式的な言明のページへのリンク
