ライスの定理の厳密な記述
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/29 18:36 UTC 版)
「ライスの定理」の記事における「ライスの定理の厳密な記述」の解説
P ( 1 ) {\displaystyle \mathbf {P} ^{(1)}} を計算可能関数全体の集合とし、 ϕ : N → P ( 1 ) {\displaystyle \phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}} をアクセプタブル・ナンバリングとする（以下 ϕ ( e ) {\displaystyle \phi (e)} の事を ϕ e {\displaystyle \phi _{e}} と書く）： ϕ {\displaystyle \phi } は全射である； 対応 ( e , x ) ↦ ϕ e ( x ) {\displaystyle (e,x)\mapsto \phi _{e}(x)} は計算可能である； 上の条件を満たす任意の ψ : N → P ( 1 ) {\displaystyle \psi \colon \mathbb {N} \to \mathbf {P} ^{(1)}} に対して、計算可能関数 f : N → N {\displaystyle f:\mathbb {N} \to \mathbb {N} } が存在して ψ e = ϕ f ( e ) {\displaystyle \psi _{e}=\phi _{f(e)}} が成り立つ。 ϕ : N → P ( 1 ) {\displaystyle \phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}} は計算可能関数へのゲーデル数割り当てであると解釈できる。 P ( 1 ) {\displaystyle \mathbf {P} ^{(1)}} の部分集合と、計算可能関数の属性を同一視する。すなわち集合 F ⊆ P ( 1 ) {\displaystyle F\subseteq \mathbf {P} ^{(1)}} に対し、 ϕ e ∈ F {\displaystyle \phi _{e}\in F} であるときだけ計算可能関数 ϕ e {\displaystyle \phi _{e}} が属性 F を持つと解釈する。 F ⊆ P ( 1 ) {\displaystyle F\subseteq \mathbf {P} ^{(1)}} に対し、「自然数 e {\displaystyle e} が与えられたとき、 ϕ e ∈ F {\displaystyle \phi _{e}\in F} であるかどうかを決定せよ」という決定問題を D F {\displaystyle D_{F}} と書く。 ライスの定理の主張は次の通り： 決定問題 D F {\displaystyle D_{F}} が決定可能である必要十分条件は、 F = ∅ {\displaystyle F=\emptyset } または F = P ( 1 ) {\displaystyle F=\mathbf {P} ^{(1)}} である。 D F {\displaystyle D_{F}} が非自明ならば D F {\displaystyle D_{F}} もしくはその補集合はm-困難である。すなわち任意の帰納的可算集合を多対一還元可能である。 ライスの定理はアクセプタブルでないナンバリングに対しては必ずしも成立しないことに注意しなければならない。例えばフリードバーグ・ナンバリングは単射であるから「自然数 e {\displaystyle e} は定数関数 x ↦ 0 {\displaystyle x\mapsto 0} の指標である」という性質は決定可能である。このことはライスの定理の結論に反する。
※この「ライスの定理の厳密な記述」の解説は、「ライスの定理」の解説の一部です。
「ライスの定理の厳密な記述」を含む「ライスの定理」の記事については、「ライスの定理」の概要を参照ください。
- ライスの定理の厳密な記述のページへのリンク
