|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
ライスの定理（ライスのていり、）は、計算機科学における計算可能関数の理論に関する定理で、 定められた性質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''は関数空間の部分集合''Y''を使って「''f''''A''は''Y''の元である」の形に書ける性質。〕とする。 たとえば''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''が存在して''f''=''f''''A''と書ける関数''f''の事を計算可能関数という。''F''が自明であるとは、厳密には、「任意の計算可能関数''f''に対し、''f''は''F''を満たす」と「任意の計算可能関数''f''に対し、''f''は''F''を満たさない」の事である。〕 ライスの定理をより厳密に記述するため、記号を導入する。 プログラム''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ビット以下か 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ライスの定理」の詳細全文を読む スポンサード リンク
|