定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない、というもの。外部リンク直観的説明編集Aが関数fを計算するプログラムであるとき、fA=fと定義する。fA(x,y,z)=x+y+zである。Aにxを入力しても(無限ループにはまる等の理由で)有限時間で停止しない場合は、fA(x)=⊥と定義する。ここで「⊥」はプログラムが停止しない事を表す特殊な記号。fAとfBが同じになる事がある事に注意されたい。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は存在しない、というものである。M(A)はYESを出力して停止する。M(A)はNOを出力して停止する。ライスの定理でFの選び方を変える事で、以下の問題が全て決定不能な事が分かる。ここで「問題XXXが決定不能」とは、「問題XXXを解くプログラムは存在しない」の意。返すか与えられたプログラムの出力は常に10ビット以下か停止性問題の決定不能性定理との関係編集ライスの定理は「停止性問題の決定不能性定理」の一般化である。ここで停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が有限時間で停止するかどうかを決定せよ」という問題である。「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。次のようなプログラムHは存在しない、という定理である。H(A,x)はYESを出力して停止する。H(A,x)はNOを出力して停止する。ライスの定理のFを「fAは⊥を出力しない」にした場合が「停止性問題の決定不能性定理」に一致する事を簡単に確かめられる。ライスの定理の証明編集ライスの定理を停止性問題の決定不能性定理に帰着する。fAがFを満たすかどうかを決定できるプログラムMが存在する。ないときM(A)=NOである。Fは関数fAの性質であってA自身の性質では無かった。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を以下のようなプログラムとする。s=A(x)を計算する(が以後は使わない)。t=V(y)を計算する。Hを、プログラムA(を表す数字)とxとを入力されると、M(TA,x)を実行するアルゴリズムとする。H(A,x)は停止性問題を解く。いうのも、前述した命題より、A(x)が停止すれば、TA,xはステップ1を抜けて先に進み、V(y)を実行する。f_{T_{A,x}}=f_{V}}。したがってH(A,x)=M(TA,x)=M(V)=YES。f_{T_{A,x}}}は恒等的に⊥。f_{T_{A,x}}=f_{U}}。したがってH(A,x)=M(TA,x)=M(U)=NO。_{f(e)}}が成り立つ。^{(1)}}は計算可能関数へのゲーデル数割り当てであると解釈できる。^{(1)}}の部分集合と、計算可能関数の属性を同一視する。