ライス＝シャピロの定理

計算可能性理論において、ライス＝シャピロの定理（英: 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\}$ が帰納的可算であるものとする。ここに $\varphi$ は部分帰納的関数のアクセプタブル・ナンバリングである。

このとき任意の部分帰納的関数 $\psi$ について、次は同値：

• $\psi \in A$;
• 有限関数 $\theta$ で $\theta \subseteq \psi$ かつ $\theta \in A$ なるものが存在する。

ここで有限関数とは有限な定義域を持つ部分関数をいう。また $\theta \subseteq \psi$ とは $\theta$ の定義域で $\theta (x)=\psi (x)$ が成り立つこと（$\theta$ が $\psi$ の制限であること）をいう。

一般に、次の主張が成り立つ： 集合 $\mathrm {Index} (A)$ が帰納的可算であることと、次の2つの条件を満たすこととは同値である：

• $\{c(\theta ):\theta :{\mbox{finite}}\wedge \theta \in A\}$ は帰納的可算;
• $n\in A$ であることと、有限関数 $\theta$ で $\theta \subseteq \varphi _{n}$ かつ $\theta \in A$ なるものが存在することとは同値。ここで $c(\theta )$ は $\theta$ の標準的な指標である。

証明

A を部分帰納的関数の集合で、指標の集合 $\mathrm {Index} (A)$ が帰納的可算であるものとする。

まず f が A に属す部分帰納的関数で、f のいかなる有限部分関数も A に属さないと仮定する。帰納的でない帰納的可算集合 $W_{e}$ を取る（例えば $W_{e}$ として停止性問題の対角線を取ればよい）。次の部分帰納的関数を考える：

$g(x,y)={\begin{cases}\uparrow &x\in W_{e,y}\\f(y)&{\mbox{otherwise}}\end{cases}}$

ここで $W_{e,y}$ は有限集合の帰納的な増大列で $\lim W_{e,y}=W_{e}$ が成り立つようなものとする。smn定理より $\varphi _{h(x)}(y)=g(x,y)$ なる全域帰納的関数 h が存在する。明らかに $\varphi _{h(x)}\subseteq f$ が成り立つ。次の2つの場合が考えられる：

• $x$ が $W_{e}$ に属すとき： $x\in W_{e,y}{\mbox{ a.e. }}y$ が成り立つ。したがって $g(x,y)=\varphi _{h(x)}$ の定義域は有限である。仮定より f のいかなる有限部分も A に属さないから、$h(x)\notin \mathrm {Index} (A)$ が成り立つ。
• $x$ が $W_{e}$ に属さないとき： $x\notin W_{e,y}$ が任意の y で成り立つ。したがって $\varphi _{h(x)}=f$ が成り立つ。仮定より f は A に属すから、$h(x)\in \mathrm {Index} (A)$ が成り立つ。

したがって $\mathbb {N} \setminus W_{e}$ は $\mathrm {Index} (A)$ に多対一還元可能である。 $\mathrm {Index} (A)$ は帰納的可算であるから、 $\mathbb {N} \setminus W_{e}$ も帰納的可算である。これは $W_{e}$ の取り方に反する。

次に f を A に属さない部分帰納的関数で、 f の有限部分 g で A に属すものが存在すると仮定する。帰納的でない帰納的可算集合 $W_{e}$ を取る。次の部分帰納的関数を考える：

$h(x,y)={\begin{cases}f(y)&g(y)\downarrow {\mbox{ or }}x\in W_{e}\\\uparrow &{\mbox{otherwise}}\end{cases}}$

smn定理より $\varphi _{k(x)}(y)=h(x,y)$ なる全域帰納的関数 k が存在する。明らかに $\varphi _{k(x)}\subseteq f$ が成り立つ。次の2つの場合が考えられる：

• $x$ が $W_{e}$ に属すとき： $\varphi _{k(x)}=f$ が成り立つ。仮定より f は A に属さないから、 $k(x)\notin \mathrm {Index} (A)$ が成り立つ。
• $x$ が $W_{e}$ に属さないとき： $\varphi _{k(x)}=g$ が成り立つ。仮定より g は A に属すから、 $k(x)\in \mathrm {Index} (A)$ が成り立つ。

したがって $\mathbb {N} \setminus W_{e}$ は $\mathrm {Index} (A)$ に多対一還元可能である。 $\mathrm {Index} (A)$ は帰納的可算であるから、 $\mathbb {N} \setminus W_{e}$ も帰納的可算である。これは $W_{e}$ の取り方に反する。

ライスの定理の導出

ライス＝シャピロの定理はライスの定理の一般化となっている。 A を部分帰納的関数の集合で、指標の集合 $\mathrm {Index} (A)$ が帰納的であるものとする。A が空な関数を含むならば、ライス＝シャピロの定理より A は部分帰納的関数全体に一致する。 A が空な関数を含まないならば、補集合がそれを含むから、ライス＝シャピロの定理より A の補集合が部分帰納的関数全体に一致する。これはライスの定理の主張にほかならない。

参考文献

• Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press ; Theorem 7-2.16.
• Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. pp. 482. ISBN 0-262-68052-1 
• Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland 

関連項目

• ライスの定理