Riceの定理

同義語：Rice's theoremライスの定理

概要

前提知識: 計算可能関数, 停止問題, s-m-n定理

プログラムについての問いには 2 種類ある。「この番号のプログラムは 100 文字以下か」「ある命令を含むか」のように、書かれた形を調べれば答えが出る問いと、「入力 $0$ で停止するか」「どの入力でも停止するか」「別のプログラムと同じ関数を計算するか」のように、プログラムが計算する関数（振る舞い）についての問いである。Rice の定理（Rice's theorem）は、後者の問いが、すべての番号で真になる問いとすべての番号で偽になる問いを除いて、どれも計算では判定できないことを述べる。
停止問題の決定不能性は「ある特定の問いが判定できない」という個別の結果であるが、Rice の定理はそれを一般化し、振る舞いについての問いが一律に判定できないことを示す。証明は、判定したい性質をもつ関数ともたない関数を、停止するかどうかに応じて切り替える還元である。この記事では Rice の定理を証明し、さらに「半決定可能な振る舞いの性質は有限の情報だけで決まる」という Rice–Shapiro の定理を証明して、全域性や有限性の判定が半決定すらできないことを導く。

記法と前提

$\mathbb{N}=\{0,1,2,\dots\}$ とする。部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ について、$f(\vec x)$ が定義されることを $f(\vec x)\!\downarrow$、されないことを $f(\vec x)\!\uparrow$ と書き、$\alpha\simeq\beta$ は「両辺とも定義されて等しいか、両辺とも定義されない」ことを表す。部分計算可能・計算可能（全域的）・決定可能・半決定可能の意味は計算可能関数の定義「計算可能関数」に従う。部分計算可能関数は合成と μ 作用素で閉じており、合成は内側の値がすべて定義されるときにだけ定義される。
番号付けは計算可能関数の定義「標準の番号付け」の $\varphi_e$（1 変数）と $\varphi^{(2)}_e$（2 変数）に固定し、次の 4 つの事実を使う。

(N1)．$k=1,2$ について、部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ が部分計算可能であることは、ある $e$ で $f=\varphi^{(k)}_e$（$\varphi^{(1)}_e:=\varphi_e$）となることと同値である。
(N2)．$(e,x)\mapsto\varphi_e(x)$ と $(e,x,y)\mapsto\varphi^{(2)}_e(x,y)$ は部分計算可能である。
(N3)．原始再帰的な関係 $T(e,x,s)$ があって、$\varphi_e(x)\!\downarrow\iff\exists s\ T(e,x,s)$ が成り立つ。
(N4)．2 変数の部分計算可能関数 $g$ に対し、計算可能関数 $h\colon\mathbb{N}\to\mathbb{N}$ があって、すべての $a,y$ について $\varphi_{h(a)}(y)\simeq g(a,y)$ が成り立つ。
(N1)・(N2) は計算可能関数の命題「番号付けは部分計算可能関数をすべて並べる」、(N3) は同じ記事の定義「標準の番号付け」の直後の標準形、(N4) は s-m-n定理の系「引数の取り込み」である。(N4) は「引数 $a$ を埋め込んだプログラムの番号を、$a$ から計算できる」ことを述べている。
$W_e:=\{x\mid\varphi_e(x)\!\downarrow\}$ とおく。(N1) により、半決定可能な集合はちょうど $W_e$ の形の集合である。自己停止集合 $K:=\{e\mid\varphi_e(e)\!\downarrow\}$ は半決定可能だが決定可能でなく、補集合 $\mathbb{N}\setminus K$ は半決定可能でない（計算可能性理論の定理「自己停止集合の決定不能性」）。
$A,B\subset\mathbb{N}$ について、計算可能関数 $f$ ですべての $x$ について $x\in A\iff f(x)\in B$ となるものがあるとき、$A$ は $B$ に 多対一還元可能 であるといい $A\le_{\mathrm m}B$ と書く。$A\le_{\mathrm m}B$ で $B$ が決定可能なら $A$ も決定可能であり（$\chi_A=\chi_B\circ f$）、$B$ が半決定可能なら $A$ も半決定可能である（$B=\operatorname{dom}\psi$ なら $A=\operatorname{dom}(\psi\circ f)$）。$A\le_{\mathrm m}B$ なら $\mathbb{N}\setminus A\le_{\mathrm m}\mathbb{N}\setminus B$ でもある（同じ $f$ を使う）。
どこでも定義されない 1 変数の部分関数を $\emptyset$ と書く（グラフが空集合だからである）。$\emptyset$ は部分計算可能である。

定義

指数集合

$A\subset\mathbb{N}$ が、$\varphi_a=\varphi_b$ かつ $a\in A$ ならば $b\in A$ を満たすとき、$A$ を 指数集合（index set）という。部分計算可能関数の集まり $\mathcal{C}$ に対し
$$ I_{\mathcal{C}}:=\{e\in\mathbb{N}\mid\varphi_e\in\mathcal{C}\} $$
とおく。$I_{\mathcal{C}}$ は指数集合であり、逆に指数集合 $A$ は $\mathcal{C}:=\{\varphi_a\mid a\in A\}$ によって $A=I_{\mathcal{C}}$ と書ける。$\mathcal{C}$ が空でも部分計算可能関数の全体でもないこと、すなわち $I_{\mathcal{C}}$ が $\emptyset$ でも $\mathbb{N}$ でもないことを、性質 $\mathcal{C}$ が 自明でない という。

指数集合は「番号 $e$ についての問いのうち、答えが $\varphi_e$ だけで決まるもの」を集合で表したものである。部分計算可能関数の集まり $\mathcal{C}$ を「関数の性質」とみなし、$I_{\mathcal{C}}$ をその性質をもつプログラムの番号の集合と読む。

例

指数集合とそうでない集合

次はどれも指数集合である。答えが $\varphi_e$ だけで決まるからである。
$$ \{e\mid\varphi_e(0)\!\downarrow\},\quad\{e\mid\varphi_e\text{ は全域的}\},\quad\{e\mid W_e=\emptyset\},\quad\{e\mid W_e\text{ は有限}\},\quad\{e\mid 17\text{ は }\varphi_e\text{ の値域に属する}\}. $$
$\{e\mid e\le 10\}$ は指数集合でない。部分計算可能関数はどれも無限個の番号をもつ（計算可能関数の命題「番号付けは部分計算可能関数をすべて並べる」の後の段落）ので、$\varphi_0=\varphi_b$ となる $b>10$ があり、$0$ は属するが $b$ は属さない。
自己停止集合 $K$ も指数集合でない。$\varphi_e(y)\simeq0$（$y=e$）、$\varphi_e(y)\!\uparrow$（$y\neq e$）となる番号 $e$ がある（Kleeneの再帰定理による）ので、$\varphi_b=\varphi_e$、$b\neq e$ となる $b$ をとると、$\varphi_e(e)\!\downarrow$ より $e\in K$、$\varphi_b(b)=\varphi_e(b)\!\uparrow$ より $b\notin K$ である。

Rice の定理

停止問題からの還元

$\mathcal{C}$ を部分計算可能関数の空でない集まりとし、$\emptyset\notin\mathcal{C}$ とする。このとき $K\le_{\mathrm m}I_{\mathcal{C}}$ である。

$g\in\mathcal{C}$ を 1 つとる。射影 $\pi(z_0,z_1):=z_0$ を使って
$$ h(x,y):\simeq\pi\bigl(g(y),\ \varphi_x(x)\bigr) $$
とおく。$h$ は (N2) の関数・$g$・$\pi$ の合成なので部分計算可能であり、$h(x,y)$ は $g(y)$ と $\varphi_x(x)$ がともに定義されるときにだけ定義されて、値 $g(y)$ をとる。(N4) により計算可能関数 $f$ で $\varphi_{f(x)}(y)\simeq h(x,y)$ となるものがある。
$x\in K$ なら $\varphi_x(x)\!\downarrow$ なので、すべての $y$ で $h(x,y)\simeq g(y)$ であり、$\varphi_{f(x)}=g\in\mathcal{C}$、すなわち $f(x)\in I_{\mathcal{C}}$ である。$x\notin K$ ならどの $y$ でも $h(x,y)$ は定義されないので $\varphi_{f(x)}=\emptyset\notin\mathcal{C}$、すなわち $f(x)\notin I_{\mathcal{C}}$ である。よって $f$ は $K$ から $I_{\mathcal{C}}$ への多対一還元である。$\square$

$f(x)$ は「まず $\varphi_x(x)$ を計算し、それが停止したら $g(y)$ を計算する」プログラムの番号である。$x$ が自己停止するかどうかで、このプログラムの振る舞いは $g$ か $\emptyset$ のどちらかに切り替わる。

主定理

Rice の定理

$\mathcal{C}$ を部分計算可能関数の集まりとする。$I_{\mathcal{C}}=\{e\mid\varphi_e\in\mathcal{C}\}$ が決定可能なら、$\mathcal{C}$ は空であるか、部分計算可能関数の全体である。言い換えると、$\emptyset$ でも $\mathbb{N}$ でもない指数集合は決定可能でない。

$\mathcal{C}$ が空でも全体でもないとして、$I_{\mathcal{C}}$ が決定可能でないことを示す。
$\emptyset\notin\mathcal{C}$ の場合：lem-rice-reduction により $K\le_{\mathrm m}I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が決定可能なら $K$ も決定可能になり、$K$ が決定可能でないことに反する。
$\emptyset\in\mathcal{C}$ の場合：$\mathcal{C}$ に属さない部分計算可能関数の集まりを $\mathcal{C}'$ とする。$\mathcal{C}$ は全体でないので $\mathcal{C}'$ は空でなく、$\emptyset\notin\mathcal{C}'$ である。lem-rice-reduction により $K\le_{\mathrm m}I_{\mathcal{C}'}=\mathbb{N}\setminus I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が決定可能なら補集合 $\mathbb{N}\setminus I_{\mathcal{C}}$ も決定可能であり、同じく矛盾する。$\square$

証明の後半から、次の強い結論も得られる。

空の関数を含む性質

$\mathcal{C}$ が $\emptyset$ を含み、部分計算可能関数の全体でないなら、$I_{\mathcal{C}}$ は半決定可能でない。

prf-rice-main の後半により $K\le_{\mathrm m}\mathbb{N}\setminus I_{\mathcal{C}}$ であり、補集合をとって $\mathbb{N}\setminus K\le_{\mathrm m}I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が半決定可能なら $\mathbb{N}\setminus K$ も半決定可能になり、$\mathbb{N}\setminus K$ が半決定可能でないことに反する。$\square$

使い方

Rice の定理から分かる決定不能性

次の集合はどれも、自明でない性質の指数集合なので決定可能でない。

$\{e\mid\varphi_e(0)\!\downarrow\}$、$\{e\mid\varphi_e\text{ は全域的}\}$、$\{e\mid\varphi_e\text{ は定数関数}\}$、$\{e\mid 17\text{ は }\varphi_e\text{ の値域に属する}\}$。
$\{e\mid W_e=\emptyset\}$ と $\{e\mid W_e\text{ は有限}\}$。どちらも $\emptyset$ を含む性質なので、cor-rice-not-ce により半決定可能でもない。
プログラムの同値性．$\mathrm{Eq}:=\{\langle a,b\rangle\mid\varphi_a=\varphi_b\}$（$\langle\cdot,\cdot\rangle$ は計算可能な全単射 $\mathbb{N}^2\to\mathbb{N}$）は決定可能でない。$\mathrm{Eq}$ が決定可能なら、固定した $b$ について $a\mapsto\langle a,b\rangle$ との合成で $\{a\mid\varphi_a=\varphi_b\}=I_{\{\varphi_b\}}$ が決定可能になるが、$\{\varphi_b\}$ は空でも全体でもない。

Rice の定理の結論は「決定可能でない」であり、「半決定可能でない」までは言えない。$\{e\mid\varphi_e(0)\!\downarrow\}$ と $\{e\mid W_e\neq\emptyset\}$ は自明でない性質の指数集合だが、どちらも半決定可能である。後者は、$\langle x,s\rangle$ を順に調べて $T(e,x,s)$ となる組を探す計算 $\mu w\,T(e,(w)_0,(w)_1)$ の定義域になっている（$(w)_0,(w)_1$ は $w=\langle x,s\rangle$ の成分）。半決定可能な指数集合が満たす必要条件を与えるのが次の節の Rice–Shapiro の定理である。

Rice–Shapiro の定理

定義域が有限集合である部分関数を 有限関数 という。有限関数は部分計算可能である。定義域 $D$ の外で $0$ をとるように $\theta$ を延ばした関数 $v$ は原始再帰関数（有限個の場合分け）で、$\chi_D$ も原始再帰的なので、$\theta(y)\simeq\pi\bigl(v(y),\ \mu z\,[\,\chi_D(y)=1\,]\bigr)$ と書けるからである（$\pi(z_0,z_1):=z_0$ は射影）。部分関数 $\theta,f$ について、$\theta$ のグラフが $f$ のグラフに含まれることを $\theta\subset f$ と書く。

Rice–Shapiro の定理

$\mathcal{C}$ を部分計算可能関数の集まりとし、$I_{\mathcal{C}}$ が半決定可能であるとする。このとき、任意の部分計算可能関数 $f$ について
$$ f\in\mathcal{C}\iff\theta\subset f\text{ となる有限関数 }\theta\in\mathcal{C}\text{ がある} $$
が成り立つ。

停止を見張る時間で関数を切る

どちらの向きも、成り立たないと仮定して $\mathbb{N}\setminus K\le_{\mathrm m}I_{\mathcal{C}}$ を導く。$I_{\mathcal{C}}$ は半決定可能なので、$\mathbb{N}\setminus K$ も半決定可能になって矛盾する。
⇒． $f\in\mathcal{C}$ だが、$\theta\subset f$ となる有限関数はどれも $\mathcal{C}$ に属さないとする。(N3) の $T$ を使って
$$ h(x,y):\simeq\begin{cases}f(y)&(T(x,x,s)\text{ となる }s\le y\text{ がない}),\\ \text{定義されない}&(\text{ある}).\end{cases} $$
とおく。条件は原始再帰的な関係の有界量化なので決定可能であり（原始再帰関数の命題「有界な和・積・量化・最小化」）、$r(x,y)\in\{0,1\}$ をその特性関数（条件が成り立てば $1$）とすると $h(x,y)\simeq\pi\bigl(f(y),\ \mu z\,[\,r(x,y)=1\,]\bigr)$ と書けるので、$h$ は部分計算可能である。(N4) により計算可能関数 $t$ で $\varphi_{t(x)}(y)\simeq h(x,y)$ となるものをとる。
$x\notin K$ なら、どの $s$ でも $T(x,x,s)$ でないので $\varphi_{t(x)}=f\in\mathcal{C}$ である。$x\in K$ なら $T(x,x,s_0)$ となる最小の $s_0$ があり、$\varphi_{t(x)}$ は $f$ を $\{y\mid y< s_0\}$ に制限した有限関数で、仮定から $\mathcal{C}$ に属さない。よって $x\notin K\iff t(x)\in I_{\mathcal{C}}$ である。
⇐．有限関数 $\theta\in\mathcal{C}$ と部分計算可能関数 $f\notin\mathcal{C}$ で $\theta\subset f$ となるものがあるとする。$\theta$ の定義域を $D$（有限集合）とする。2 変数の部分計算可能関数 $(x,y)\mapsto\theta(y)$ と $k(x,y):\simeq\pi\bigl(f(y),\ \varphi_x(x)\bigr)$ の番号をそれぞれ $c_1,c_2$ とし（(N1)）、
$$ j(y):=\begin{cases}c_1&(y\in D),\\ c_2&(y\notin D),\end{cases}\qquad h(x,y):\simeq\varphi^{(2)}_{j(y)}(x,y) $$
とおく。$D$ は有限なので $j$ は計算可能であり、$h$ は (N2) の関数と $j$ の合成なので部分計算可能である。$y\in D$ なら $h(x,y)=\theta(y)$、$y\notin D$ なら $h(x,y)\simeq k(x,y)$ である。(N4) により計算可能関数 $t$ で $\varphi_{t(x)}(y)\simeq h(x,y)$ となるものをとる。
$x\in K$ なら、$y\in D$ では $h(x,y)=\theta(y)=f(y)$、$y\notin D$ では $h(x,y)\simeq f(y)$ なので $\varphi_{t(x)}=f\notin\mathcal{C}$ である。$x\notin K$ なら、$y\notin D$ で $h(x,y)$ は定義されないので $\varphi_{t(x)}=\theta\in\mathcal{C}$ である。よって $x\notin K\iff t(x)\in I_{\mathcal{C}}$ である。$\square$

⇒ の還元 $t(x)$ は「入力 $y$ を、自己停止の計算を見張る時間とみなし、$y$ 段までに停止していなければ $f(y)$ を計算する」プログラムの番号である。自己停止が見つかった時点で、それ以降の入力は永久に止まらず、関数は有限の切れ端になる。

半決定可能でない指数集合

次の集合はどれも半決定可能でない。

$\mathrm{Tot}:=\{e\mid\varphi_e\text{ は全域的}\}$ と、その補集合 $\mathbb{N}\setminus\mathrm{Tot}$。
$\{e\mid W_e\text{ は有限}\}$ と $\{e\mid W_e=\mathbb{N}\}$。

どれも thm-rice-shapiro の条件が破れることを見ればよい。

全域的な関数（たとえば恒等的に $0$ の関数）は全域的な関数の集まりに属するが、その有限部分関数は全域的でない。よって ⇒ が破れ、$\mathrm{Tot}$ は半決定可能でない。補集合 $\mathbb{N}\setminus\mathrm{Tot}$ は全域的でない関数の集まりの指数集合で、有限関数 $\emptyset$ はそこに属し、全域的な関数 $f$ について $\emptyset\subset f$ だが $f$ は属さない。よって ⇐ が破れる。
有限関数の集まりは $\emptyset$ を含むので、⇐ が破れることは 1 の後半と同じである（cor-rice-not-ce からも分かる）。$\{e\mid W_e=\mathbb{N}\}=\mathrm{Tot}$ である。$\square$

$\mathrm{Tot}$ も補集合も半決定可能でないことは、計算可能性理論の定理「全域性の集合とその補集合はどちらも半決定可能でない」でも還元を直接組み立てて示されている。
Rice–Shapiro の定理の条件は、半決定可能であるための必要条件であって十分条件ではない。

有限関数の条件を満たすが半決定可能でない性質

$\theta_n:=\{(n,0)\}$（$n$ でだけ定義されて値 $0$ をとる関数）とし、$\mathcal{C}:=\{f\mid n\notin K\text{ かつ }f(n)=0\text{ となる }n\text{ がある}\}$ とおく。$f\in\mathcal{C}$ なら $\theta_n\subset f$ かつ $\theta_n\in\mathcal{C}$ となる $n$ があり、逆に有限関数 $\theta\in\mathcal{C}$ が $\theta\subset f$ なら $f\in\mathcal{C}$ なので、$\mathcal{C}$ は thm-rice-shapiro の同値を満たす。しかし $I_{\mathcal{C}}$ は半決定可能でない。

詳細

$g(n,y):\simeq\mu z\,[\,(y\mathbin{\dot-}n)+(n\mathbin{\dot-}y)=0\,]$ は、$y=n$ なら $0$、$y\neq n$ なら定義されない（μ の条件が $z$ によらず偽）ので、$g(n,\cdot)=\theta_n$ である。(N4) により計算可能関数 $u$ で $\varphi_{u(n)}=\theta_n$ となるものがある。$\theta_n\in\mathcal{C}$ は $n\notin K$ と同値なので、$n\notin K\iff u(n)\in I_{\mathcal{C}}$、すなわち $\mathbb{N}\setminus K\le_{\mathrm m}I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が半決定可能なら $\mathbb{N}\setminus K$ も半決定可能になり矛盾する。

不動点による別証明

Rice の定理は、プログラムが自分の番号を参照できることを述べる Kleeneの再帰定理からも導ける。使うのはその不動点の形「任意の計算可能関数 $f\colon\mathbb{N}\to\mathbb{N}$ に対し、$\varphi_e=\varphi_{f(e)}$ となる番号 $e$ がある」である。
$I_{\mathcal{C}}$ が決定可能で、$a\in I_{\mathcal{C}}$ と $b\notin I_{\mathcal{C}}$ があるとする。

詳細

$f(x):=b$（$x\in I_{\mathcal{C}}$）、$f(x):=a$（$x\notin I_{\mathcal{C}}$）とおくと、$I_{\mathcal{C}}$ が決定可能なので $f$ は計算可能である。不動点 $e$ をとる。$e\in I_{\mathcal{C}}$ なら $\varphi_e=\varphi_{f(e)}=\varphi_b$ であり、$I_{\mathcal{C}}$ は指数集合なので $b\in I_{\mathcal{C}}$ となって矛盾する。$e\notin I_{\mathcal{C}}$ なら $\varphi_e=\varphi_a$ なので $e\in I_{\mathcal{C}}$ となり、やはり矛盾する。

この証明は「性質をもつなら、もたないプログラムのふりをする」プログラムを自己参照で作るもので、停止問題の決定不能性の対角線論法を性質一般に移したものになっている。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
指数集合である（thm-rice-main）	$\{e\mid e\le10\}$	決定可能でないこと
$\mathcal{C}$ が空でも全体でもない（thm-rice-main）	$\mathcal{C}$ を部分計算可能関数の全体とし、$I_{\mathcal{C}}=\mathbb{N}$	決定可能でないこと
番号付けがすべての部分計算可能関数を並べる（(N1)）	原始再帰関数を組み立てる式の番号付けと、性質「$f(0)=0$」	自明でない性質の番号の集合が決定可能でないこと
$\emptyset\notin\mathcal{C}$（lem-rice-reduction）	$\mathcal{C}=\{\emptyset\}$	$K\le_{\mathrm m}I_{\mathcal{C}}$
$I_{\mathcal{C}}$ が半決定可能（thm-rice-shapiro）	$\mathcal{C}$ を全域的な部分計算可能関数の全体とする	⇒ の向き（$\mathcal{C}$ の元が $\mathcal{C}$ に属する有限部分関数をもつこと）

反例の確かめ

1・2 行目は集合が決定可能であることを、3〜5 行目は結論が成り立たないことを確かめる。

詳細

1 行目：特性関数は原始再帰関数なので決定可能である。ex-rice-index-sets の 2 のとおり指数集合でない。番号の大きさは番号の書き方の性質であって、関数の性質ではない。

2 行目：$I_{\mathcal{C}}=\mathbb{N}$ の特性関数は定数 $1$ である。$\mathcal{C}$ が空なら $I_{\mathcal{C}}=\emptyset$ で同様である。

3 行目：原始再帰関数を組み立てる式に番号を付け、番号 $t$ の式が表す 1 変数関数を $f_t$ とする（式を表さない番号には定数 $0$ を当てる）。$(t,y)\mapsto f_t(y)$ は計算可能である。式の番号 $t$ と引数の列の符号 $w$ に式の値（式を表さないときや引数の個数が合わないときは $0$）を対応させる関数は、式の最後の構成（定数 $0$・後者・射影・合成・原始再帰）による場合分けで、部分式の値と、原始再帰では再帰の変数を 1 つ減らした値を自分の番号で呼び出す部分計算可能関数を Kleeneの再帰定理で作ればよく（場合分けは同記事の例「階乗を自己参照で定義する」と同じく番号の選択で処理する）、式の構成と再帰の変数についての帰納法で、すべての式と引数で定義されて式の値に等しいことが分かる（番号付けの作り方は OLT26 §29.14、pp. 440–441）。この番号付けでは、評価 $(t,y)\mapsto f_t(y)$ が計算可能で（(N2) にあたる）、原始再帰関数 $g(a,y)$ の式の $a$ に定数の式を代入すれば $y\mapsto g(a,y)$ の番号が $a$ から計算できる（(N4) にあたる）が、並ぶのは全域的な原始再帰関数だけで、(N1) が成り立たない。性質「$f(0)=0$」をもつ番号の集合 $\{t\mid f_t(0)=0\}$ は、$f_t(0)$ を計算して比べればよいので決定可能であり、定数 $0$ と定数 $1$ の関数がともに並ぶので $\emptyset$ でも全体でもない。

4 行目：$K\le_{\mathrm m}I_{\{\emptyset\}}=\{e\mid W_e=\emptyset\}$ なら、補集合をとって $\mathbb{N}\setminus K\le_{\mathrm m}\{e\mid W_e\neq\emptyset\}$ であり、右辺は半決定可能（ex-rice-applications の後の段落）なので $\mathbb{N}\setminus K$ も半決定可能になって矛盾する。

5 行目：恒等的に $0$ の関数は $\mathcal{C}$ に属するが、その有限部分関数は全域的でないので $\mathcal{C}$ に属さない。thm-rice-shapiro の対偶により $I_{\mathcal{C}}=\mathrm{Tot}$ は半決定可能でない（cor-rice-shapiro-examples）。

3 行目の番号付けでも、振る舞いについての問いがすべて判定できるわけではない。たとえば「$f_t$ は恒等的に $0$ か」はこの番号付けでも決定可能でない。原始再帰的な関数 $(x,y)\mapsto$（$T(x,x,s)$ となる $s\le y$ があれば $1$、なければ $0$）を表す式の $x$ に定数 $x$ の式を代入した式の番号 $c(x)$ は $x$ から計算でき、$f_{c(x)}$ が恒等的に $0$ であることは $x\notin K$ と同値だからである。Rice の定理は、すべての部分計算可能関数を並べ、しかも万能関数と s-m-n 定理が使える番号付けで、振る舞いについての問いが一律に判定できないことを述べている。

補足

計算機科学での読み方．プログラムの静的解析（実行せずにプログラムの性質を調べること）は、振る舞いについての自明でない性質を正確に判定できない。実用の解析は、答えを「はい」「いいえ」「分からない」の 3 通りにするか、安全側に近似する。
還元の強さ．lem-rice-reduction は多対一還元 $K\le_{\mathrm m}I_{\mathcal{C}}$ を与えるので、Rice の定理は「どの自明でない指数集合も、$K$ か $\mathbb{N}\setminus K$ と少なくとも同じだけ難しい」と言い換えられる。どこまで難しいかは性質ごとに異なる。$\{e\mid\varphi_e(0)\!\downarrow\}$ は半決定可能なので $K$ に多対一還元でき（計算可能性理論の定理「自己停止集合の完全性」）、$K$ と互いに還元できる。一方 $\mathrm{Tot}$ は半決定可能でない（cor-rice-shapiro-examples）ので、$K$ にも $\mathbb{N}\setminus K$ にも多対一還元できない。

参照箇所

OLT26 Chapter 30：Proposition 30.22（p. 464、全域性の集合の決定不能性）、Theorem 30.23（p. 465、Rice の定理と指数集合の説明。証明は pp. 466–467）、Corollary 30.24（p. 467、応用の例）、Lemma 30.25・Theorem 30.26（p. 468、不動点定理）。Chapter 29 §29.14（pp. 440–441、原始再帰関数の番号付け）。
Rice–Shapiro の定理（thm-rice-shapiro）とその系、ex-rice-shapiro-converse は、この記事の証明による。