ライスの定理

ライスの定理（ライスのていり、）は、計算機科学における計算可能関数の理論に関する定理で、
定められた性質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"を関数に関する何らかの性質とする。
たとえば"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"も満たさない性質」の事である。
ライスの定理をより厳密に記述するため、記号を導入する。
プログラム"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"の選び方を変える事で、以下の問題が全て決定不能な事が分かる。
ここで「問題XXXが決定不能」とは、「問題XXXを解くプログラムは存在しない」の意。
停止性問題の決定不能性定理との関係.
ライスの定理は「停止性問題の決定不能性定理」の一般化である。
ここで停止性問題とは、「プログラム"A"とデータ"x"が与えられたとき、"A"("x")が有限時間で停止するかどうかを決定せよ」という問題である。
また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。
すなわち次のようなプログラム"H"は存在しない、という定理である。
ライスの定理の"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"を以下のようなプログラムとする。<br>
0. 入力"y"を受け取る。<br>
1. "s"="A"("x")を計算する(が以後は使わない)。<br>
2. "t"="V"("y")を計算する。<br>
3. "t"を出力する。<br>
さらに"H"を、プログラム"A"(を表す数字)と"x"とを入力されると、"M"("T""A","x")を実行するアルゴリズムとする。
"H"("A","x")は停止性問題を解く。というのも、前述した命題より、
ライスの定理の厳密な記述.
formula_4 を計算可能関数全体の集合とし、
formula_5 をアクセプタブル・ナンバリングとする（以下 formula_6 の事を formula_7 と書く）：
formula_5 は計算可能関数へのゲーデル数割り当てであると解釈できる。
formula_4 の部分集合と、計算可能関数の属性を同一視する。
すなわち集合 formula_15 に対し、
formula_16 であるときだけ計算可能関数 formula_7 が属性 "F" を持つと解釈する。
formula_15 に対し、「自然数 formula_19 が与えられたとき、formula_16 であるかどうかを決定せよ」という決定問題を formula_21 と書く。
ライスの定理の主張は次の通り：
ライスの定理はアクセプタブルでないナンバリングに対しては必ずしも成立しないことに注意しなければならない。例えばフリードバーグ・ナンバリングは単射であるから「自然数 formula_19 は定数関数 formula_28 の指標である」という性質は決定可能である。このことはライスの定理の結論に反する。
ライスの定理に類する結果.
ライスの定理は、帰納的可算集合 (recursively enumerable sets) を決定可能なやりかたで二分することの不可能性について述べたものと考えられる。
この定理のバリエーションとして、帰納的可算集合のかわりに帰納的集合 (recursive sets; 計算可能集合) を考えたものもある。
これらの結果の類似性はそれぞれの定理が以下の主張をしていることから言える。
類似定理のフォーマルな記述は省略する。
この結果は、協力ゲーム理論あるいは社会選択理論といった分野において、シンプルゲームの中村ナンバーの考察などに応用されている (Kumabe and Mihara, 2008, 2008)。
ライスの定理を精緻化したものとしてライス＝シャピロの定理がある。この定理はインデックス集合が帰納的可算である為にはある種の有限性を持つことが必要（かつ十分）であることを示す。