ライスの定理 ライスの定理の厳密な記述

ウィキペディア

ライスの定理

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

ライスの定理の厳密な記述

$\mathbf {P} ^{(1)}$ を計算可能関数全体の集合とし、 $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ をアクセプタブル・ナンバリングとする（以下 $\phi (e)$ の事を $\phi _{e}$ と書く）：

• $\phi$ は全射である；
• 対応 $(e,x)\mapsto \phi _{e}(x)$ は計算可能である；
• 上の条件を満たす任意の $\psi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ に対して、計算可能関数 $f:\mathbb {N} \to \mathbb {N}$ が存在して $\psi _{e}=\phi _{f(e)}$ が成り立つ。

$\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ は計算可能関数へのゲーデル数割り当てであると解釈できる。

$\mathbf {P} ^{(1)}$ の部分集合と、計算可能関数の属性を同一視する。 すなわち集合 $F\subseteq \mathbf {P} ^{(1)}$ に対し、 $\phi _{e}\in F$ であるときだけ計算可能関数 $\phi _{e}$ が属性 F を持つと解釈する。

$F\subseteq \mathbf {P} ^{(1)}$ に対し、「自然数 $e$ が与えられたとき、$\phi _{e}\in F$ であるかどうかを決定せよ」という決定問題を $D_{F}$ と書く。

ライスの定理の主張は次の通り：

• 決定問題 $D_{F}$ が決定可能である必要十分条件は、$F=\emptyset$ または $F=\mathbf {P} ^{(1)}$ である。
• $D_{F}$ が非自明ならば $D_{F}$ もしくはその補集合はm-困難である。すなわち任意の帰納的可算集合を多対一還元可能である。

ライスの定理はアクセプタブルでないナンバリングに対しては必ずしも成立しないことに注意しなければならない。例えばフリードバーグ・ナンバリングは単射であるから「自然数 $e$ は定数関数 $x\mapsto 0$ の指標である」という性質は決定可能である。このことはライスの定理の結論に反する。