ライスの定理 (ライスのていり、英 : Rice's theorem )は、計算機科学 における計算可能関数 の理論に関する定理で、
定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない、というもの。
名称の由来は Henry Gordon Rice から。
直観的説明
A が関数f を計算するプログラムであるとき、f A =f と定義する。
たとえばA が「a=x+yを計算した後、a+zを出力する」という趣旨のプログラムであると、
f A (x ,y ,z )=x +y +z である。
ただし、A にx を入力しても(無限ループにはまる等の理由で)有限時間で停止しない場合は、f A (x )=⊥と定義する。
ここで「⊥」はプログラムが停止しない事を表す特殊な記号。
なお、2つのプログラムA 、B に対し、A とB がプログラムとしては別物であっても
f A とf B が同じになる事がある事に注意されたい。
たとえばB を「b=x+zを計算した後、b+yを出力する」という趣旨のプログラムとすると、
B の見掛けは前述のA のそれとは異なるが、明らかにf A (x ,y ,z )=f B (x ,y ,z )=x +y +z である。
F を関数に関する何らかの性質[ 1] とする。
たとえばF は「関数f A は恒等的に0である」とか「f A (x )≧x 3 である」のようなものである。
注意しなければならないのは、F は関数f A に関する性質であってプログラムA に関する性質ではない事である。
よってF は「プログラムA は300行以下である」のようなものであってはならない。
そして「A が与えられたとき、f A は性質F を満たすかを決定せよ」という問題を考える。
ライスの定理は、F が自明なものでない限り、この問題を常に正しく解く事できるプログラムは存在しない、というものである。
ここで自明な性質とは、「全てのf A が満たす性質」と「いかなるf A も満たさない性質」の事である。
[ 2]
ライスの定理をより厳密に記述するため、記号を導入する。
プログラムA にデータx を入力して実行する事をA (x )と書き、A (x )がy を出力するときy =A (x )と書く。
コンピュータではいかなるデータも0と1の数字で表し、したがってプログラム自身も0と1の数字で表せる。
以下記号を簡単にする為、プログラムA を数字で表したものも、A と書く。
よって例えばプログラムA 、B に対し、「A (B )」は、「プログラムB を表す数字をb とし、A にb を入力して実行する」の意である。
ライスの定理は、F を自明でない任意の性質とするとき、次のようなプログラムM は存在しない、というものである。
f A がF を満たす ⇒ M (A )はYESを出力して停止する。
f A がF を満たさない ⇒ M (A )はNOを出力して停止する。
ライスの定理でF の選び方を変える事で、以下の問題が全て決定不能な事が分かる。
ここで「問題XXXが決定不能」とは、「問題XXXを解くプログラムは存在しない」の意。
与えられたプログラムが全ての入力に対して 0 を返すか
与えられたプログラムが少なくとも1つの入力に対して 0 を返すか
与えられたプログラムの出力は常に10ビット以下か
停止性問題の決定不能性定理との関係
ライスの定理は「停止性問題 の決定不能性定理」の一般化である。
ここで停止性問題とは、「プログラムA とデータx が与えられたとき、A (x )が有限時間で停止するかどうかを決定せよ」という問題である。
また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。
すなわち次のようなプログラムH は存在しない、という定理である。
A (x )が停止する ⇒ H (A ,x )はYESを出力して停止する。
A (x )は停止しない ⇒ H (A ,x )はNOを出力して停止する。
ライスの定理のF を「f A は⊥を出力しない」にした場合が「停止性問題の決定不能性定理」に一致する事を簡単に確かめられる。
ライスの定理の証明
ライスの定理を停止性問題の決定不能性定理に帰着する。
証明は背理法による。
ライスの定理が成り立たなかったとすると、ある非自明な性質F が存在し、
f A がF を満たすかどうかを決定できるプログラムM が存在する。
すなわち、f A がF を満たすときM (A )=YESで、
そうでないときM (A )=NOである。
F は関数f A の性質であってA 自身の性質では無かった。
したがってf A =f B を満たす任意のプログラムA 、B に対し、
f A がF を満たす必要十分条件はf B がF を満たす事である。
よってM の定義より、次の命題が成り立つ。
無限ループを利用するなどして停止しないプログラム意図的に作るのは簡単である。
そこでU を、いかなる入力に対しても停止しないプログラムとする。
すると明らかに、f U は恒等的に⊥を出力する。
F' を、「F を満たさない」という性質とする。
必要ならF をF' と取り換える事で、M (U )=NOと仮定してよい。
F は非自明な性質なので、F を満たすf V が存在する。
M の性質より、M (V )=YESである。
A を任意のプログラムとしx を任意のデータとするとき、T A ,x を以下のようなプログラムとする。
0. 入力y を受け取る。
1. s =A (x )を計算する(が以後は使わない)。
2. t =V (y )を計算する。
3. t を出力する。
さらにH を、プログラムA (を表す数字)とx とを入力されると、M (T A ,x )を実行するアルゴリズムとする。
H (A ,x )は停止性問題を解く。というのも、前述した命題より、
A (x )が停止すれば、T A ,x はステップ1を抜けて先に進み、V (y )を実行する。よって
f
T
A
,
x
=
f
V
{\displaystyle f_{T_{A,x}}=f_{V}}
。したがってH (A ,x )=M (T A ,x )=M (V )=YES。
A (x )が停止しなければ、T A ,x はステップ1が停止しないので、
f
T
A
,
x
{\displaystyle f_{T_{A,x}}}
は恒等的に⊥。よって
f
T
A
,
x
=
f
U
{\displaystyle f_{T_{A,x}}=f_{U}}
。したがってH (A ,x )=M (T A ,x )=M (U )=NO。
ライスの定理の厳密な記述
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}
の指標である」という性質は決定可能である。このことはライスの定理の結論に反する。
ライスの定理に類する結果
ライスの定理は、帰納的可算集合 (recursively enumerable sets) を決定可能なやりかたで二分することの不可能性について述べたものと考えられる。[ 3]
この定理のバリエーションとして、帰納的可算集合のかわりに帰納的集合 (recursive sets; 計算可能集合) を考えたものもある。
これらの結果の類似性はそれぞれの定理が以下の主張をしていることから言える。
もともとのライスの定理は、「ある帰納的可算集合のクラスが"決定可能"ならば、与えられた帰納的可算集合がそのクラスに属するかどうかを判定するためには、ゼロ個の
i
{\displaystyle i}
について、
i
{\displaystyle i}
がその集合に属するかどうかを調べればよい」ことを主張する。
帰納的集合にかんする定理は、「ある帰納的集合のクラスが"決定可能"ならば、与えられた帰納的集合がそのクラスに属するかどうかを判定するためには、有限個の
i
{\displaystyle i}
について、
i
{\displaystyle i}
がその集合に属するかどうかを調べればよい」ことを主張する。
類似定理のフォーマルな記述は省略する。[ 4]
[ 5]
(詳細は 英文記事 参照。)
この結果は、 協力ゲーム理論 あるいは社会選択理論 といった分野において、シンプルゲームの中村ナンバー の考察などに応用されている (Kumabe and Mihara, 2008,[ 5] 2008[ 6] )。
ライスの定理を精緻化したものとしてライス=シャピロの定理 がある。この定理はインデックス集合が帰納的可算である為にはある種の有限性を持つことが必要(かつ十分)であることを示す。
脚注
^ 厳密には、F は関数空間の部分集合Y を使って「f A はY の元である」の形に書ける性質。
^ あるプログラムA が存在してf =f A と書ける関数f の事を計算可能関数という。F が自明であるとは、厳密には、「任意の計算可能関数f に対し、f はF を満たす」と「任意の計算可能関数f に対し、f はF を満たさない」の事である。
^
C
{\displaystyle C}
を帰納的可算集合のクラスとするとき、
計算可能な関数にたいするライスの定理で、
{
ϕ
e
:
dom
ϕ
e
∈
C
}
{\displaystyle \{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}}
というクラスを考えればよい。
ただし
dom
ϕ
e
:=
{
x
:
ϕ
e
(
x
)
↓
}
{\displaystyle {\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}}
は
ϕ
e
{\displaystyle \phi _{e}}
の定義域であり、
あらゆる帰納的可算集合は適当な
e
{\displaystyle e}
を選ぶことにより
dom
ϕ
e
{\displaystyle {\textrm {dom}}\,\phi _{e}}
と書くことが出来る。
^ Kreisel, G., Lacombe, D., Shoenfield, J.R., 1959. Partial recursive functionals and effective operations. In: Heyting, A. (Ed.), Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, pp. 290–297.
^ a b Kumabe, Masahiro; Mihara, H. Reiju (2008). “Computability of simple games: A characterization and application to the core”. Journal of Mathematical Economics 44 (3-4): 348–366. doi :10.1016/j.jmateco.2007.05.012 . ISSN 03044068 .
^ Kumabe, Masahiro; Mihara, H. Reiju (2008). “The Nakamura numbers for computable simple games”. Social Choice and Welfare 31 (4): 621–640. doi :10.1007/s00355-008-0300-5 . ISSN 0176-1714 .
参考文献
Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74 , 358-366, 1953.
関連項目
外部リンク