ライスの定理

提供: miniwiki
移動先:案内、検索

ライスの定理（ライスのていり、英: Rice's theorem）は、計算機科学における計算可能関数の理論に関する定理で、 定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない、というもの。 名称の由来は Henry Gordon Rice から。

直観的説明

Aが関数fを計算するプログラムであるとき、fA=fと定義する。 たとえばAが「a=x+yを計算した後、a+zを出力する」という趣旨のプログラムであると、 fA(x,y,z)=x+y+zである。 ただし、Aにxを入力しても(無限ループにはまる等の理由で)有限時間で停止しない場合は、fA(x)=⊥と定義する。 ここで「⊥」はプログラムが停止しない事を表す特殊な記号。

なお、2つのプログラムA、Bに対し、AとBがプログラムとしては別物であっても fAとfBが同じになる事がある事に注意されたい。 たとえばBを「b=x+zを計算した後、b+yを出力する」という趣旨のプログラムとすると、 Bの見掛けは前述のAのそれとは異なるが、明らかにfA(x,y,z)=fB(x,y,z)=x+y+zである。

Fを関数に関する何らかの性質[1]とする。 たとえばFは「関数fAは恒等的に0である」とか「fA(x)≧x3である」のようなものである。 注意しなければならないのは、Fは関数fAに関する性質であってプログラムAに関する性質ではない事である。 よってFは「プログラムAは300行以下である」のようなものであってはならない。

そして「Aが与えられたとき、fAは性質Fを満たすかを決定せよ」という問題を考える。 ライスの定理は、Fが自明なものでない限り、この問題を常に正しく解く事できるプログラムは存在しない、というものである。 ここで自明な性質とは、「全てのfAが満たす性質」と「いかなるfAも満たさない性質」の事である。 [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は存在しない、というものである。

  • fAがFを満たす ⇒ M(A)はYESを出力して停止する。
  • fAが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を「fAは⊥を出力しない」にした場合が「停止性問題の決定不能性定理」に一致する事を簡単に確かめられる。

ライスの定理の証明

ライスの定理を停止性問題の決定不能性定理に帰着する。 証明は背理法による。

ライスの定理が成り立たなかったとすると、ある非自明な性質Fが存在し、 fAがFを満たすかどうかを決定できるプログラムMが存在する。 すなわち、fAがFを満たすときM(A)=YESで、 そうでないときM(A)=NOである。

Fは関数fAの性質であってA自身の性質では無かった。 したがってfA=fBを満たす任意のプログラムA、Bに対し、 fAがFを満たす必要十分条件はfBがFを満たす事である。 よってMの定義より、次の命題が成り立つ。

  • fA=fBならM(A)=M(B)。

無限ループを利用するなどして停止しないプログラム意図的に作るのは簡単である。 そこでUを、いかなる入力に対しても停止しないプログラムとする。 すると明らかに、fUは恒等的に⊥を出力する。

F'を、「Fを満たさない」という性質とする。 必要ならFをF'と取り換える事で、M(U)=NOと仮定してよい。

Fは非自明な性質なので、Fを満たすfVが存在する。 Mの性質より、M(V)=YESである。

Aを任意のプログラムとしxを任意のデータとするとき、TA,xを以下のようなプログラムとする。
0. 入力yを受け取る。
1. s=A(x)を計算する(が以後は使わない)。
2. t=V(y)を計算する。
3. tを出力する。

さらにHを、プログラムA(を表す数字)とxとを入力されると、M(TA,x)を実行するアルゴリズムとする。

H(A,x)は停止性問題を解く。というのも、前述した命題より、

  • A(x)が停止すれば、TA,xはステップ1を抜けて先に進み、V(y)を実行する。よって[math]f_{T_{A,x}}=f_{V}[/math]。したがってH(A,x)=M(TA,x)=M(V)=YES。
  • A(x)が停止しなければ、TA,xはステップ1が停止しないので、[math]f_{T_{A,x}}[/math]は恒等的に⊥。よって[math]f_{T_{A,x}}=f_{U}[/math]。したがってH(A,x)=M(TA,x)=M(U)=NO。

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

[math]\mathbf{P}^{(1)}[/math] を計算可能関数全体の集合とし、 [math]\phi\colon \mathbb{N} \to \mathbf{P}^{(1)}[/math] をアクセプタブル・ナンバリングとする：

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

[math]\phi\colon \mathbb{N} \to \mathbf{P}^{(1)}[/math] は計算可能関数へのゲーデル数割り当てであると解釈できる。 以下 [math]\phi(e)[/math] の事を [math]\phi_e[/math] と書く。

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

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

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

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

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

ライスの定理に類する結果

ライスの定理は、帰納的可算集合 (recursively enumerable sets) を決定可能なやりかたで二分することの不可能性について述べたものと考えられる。[3] この定理のバリエーションとして、帰納的可算集合のかわりに帰納的集合 (recursive sets; 計算可能集合) を考えたものもある。 これらの結果の類似性はそれぞれの定理が以下の主張をしていることから言える。

  • もともとのライスの定理は、「ある帰納的可算集合のクラスが"決定可能"ならば、与えられた帰納的可算集合がそのクラスに属するかどうかを判定するためには、ゼロ個の [math]i[/math] について、[math]i[/math] がその集合に属するかどうかを調べればよい」ことを主張する。
  • 帰納的集合にかんする定理は、「ある帰納的集合のクラスが"決定可能"ならば、与えられた帰納的集合がそのクラスに属するかどうかを判定するためには、有限個の [math]i[/math] について、[math]i[/math] がその集合に属するかどうかを調べればよい」ことを主張する。

類似定理のフォーマルな記述は省略する。[4] [5] (詳細は 英文記事参照。)

この結果は、 協力ゲーム理論あるいは社会選択理論といった分野において、シンプルゲームの中村ナンバーの考察などに応用されている (Kumabe and Mihara, 2008,[5] 2008[6])。

ライスの定理を精緻化したものとしてライス＝シャピロの定理がある。この定理はインデックス集合が帰納的可算である為にはある種の有限性を持つことが必要（かつ十分）であることを示す。

脚注

  1. ↑ 厳密には、Fは関数空間の部分集合Yを使って「fAはYの元である」の形に書ける性質。
  2. ↑ あるプログラムAが存在してf=fAと書ける関数fの事を計算可能関数という。Fが自明であるとは、厳密には、「任意の計算可能関数fに対し、fはFを満たす」と「任意の計算可能関数fに対し、fはFを満たさない」の事である。
  3. ↑ [math]C[/math] を帰納的可算集合のクラスとするとき、 計算可能な関数にたいするライスの定理で、[math]\{\phi_e: \textrm{dom}\, \phi_e \in C\}[/math]というクラスを考えればよい。 ただし [math]\textrm{dom}\, \phi_e :=\{x: \phi_e(x)\downarrow \}[/math] は [math]\phi_e[/math] の定義域であり、 あらゆる帰納的可算集合は適当な[math]e[/math] を選ぶことにより [math]\textrm{dom}\, \phi_e[/math] と書くことが出来る。
  4. ↑ 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.
  5. ↑ 5.0 5.1 テンプレート:Cite doi
  6. ↑ テンプレート:Cite doi

参考文献

  • Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.

関連項目

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ライスの定理&oldid=112429」から取得