ライス＝シャピロの定理

計算可能性理論において、ライス＝シャピロの定理（）とはライスの定理の一般化した定理である。名称は Henry Gordon Rice と Norman Shapiro に因む。
非形式的な言明.
定理の主張は非形式的には次のように述べられる： 計算可能関数の半決定可能な述語 "A" と、計算可能関数 "f" が与えられたとき、 "f" が "A" を満たす為には、"f" の有限部分で "A" を満たすものが存在することが必要十分である。いま "f" が "A" を満たしていると仮定しよう。するとライス＝シャピロの定理より "f" の有限部分 "g" が存在して "A" を満たす。このとき "g" の任意の計算可能な延長関数もまた "A" を満たす。したがって計算可能関数の無限個の入出力が真偽の決定に関与するような述語は帰納的可算ではありえない。
形式的な言明.
いま "A" を（1変数）部分帰納的関数の集合で、指標の集合 formula_1 が帰納的可算であるものとする。ここに formula_2 は部分帰納的関数のアクセプタブル・ナンバリングである。
このとき任意の部分帰納的関数 formula_3 について、次は同値：
ここで有限関数とは有限な定義域を持つ部分関数をいう。また formula_6 とは formula_5 の定義域で formula_10 が成り立つこと（formula_5 が formula_3 の制限であること）をいう。
一般に、次の主張が成り立つ： 集合 formula_13 が帰納的可算であることと、次の2つの条件を満たすこととは同値である：
証明.
"A" を部分帰納的関数の集合で、指標の集合 formula_13 が帰納的可算であるものとする。
まず "f" が "A" に属す部分帰納的関数で、"f" のいかなる有限部分関数も "A" に属さないと仮定する。帰納的でない帰納的可算集合 formula_22 を取る（例えば formula_22 として停止性問題の対角線を取ればよい）。次の部分帰納的関数を考える：
formula_24
ここで formula_25 は有限集合の帰納的な増大列で formula_26 が成り立つようなものとする。smn定理より formula_27 なる全域帰納的関数 "h" が存在する。明らかに formula_28 が成り立つ。次の2つの場合が考えられる：
したがって formula_39 は formula_13 に多対一還元可能である。 formula_13 は帰納的可算であるから、 formula_39 も帰納的可算である。これは formula_22 の取り方に反する。
次に "f" を "A" に属さない部分帰納的関数で、 "f" の有限部分 "g" で "A" に属すものが存在すると仮定する。帰納的でない帰納的可算集合 formula_22 を取る。次の部分帰納的関数を考える：
formula_45
smn定理より formula_46 なる全域帰納的関数 "k" が存在する。明らかに formula_47 が成り立つ。次の2つの場合が考えられる：
したがって formula_39 は formula_13 に多対一還元可能である。 formula_13 は帰納的可算であるから、 formula_39 も帰納的可算である。これは formula_22 の取り方に反する。
ライスの定理の導出.
ライス＝シャピロの定理はライスの定理の一般化となっている。 "A" を部分帰納的関数の集合で、指標の集合 formula_13 が帰納的であるものとする。"A" が空な関数を含むならば、ライス＝シャピロの定理より "A" は部分帰納的関数全体に一致する。 "A" が空な関数を含まないならば、補集合がそれを含むから、ライス＝シャピロの定理より "A" の補集合が部分帰納的関数全体に一致する。これはライスの定理の主張にほかならない。