ライスの定理
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を関数に関する何らかの性質とする。 たとえばFは「関数fAは恒等的に0である」とか「fA(x)≧xである」のようなものである。 注意しなければならないのは、Fは関数fAに関する性質であってプログラムAに関する性質ではない事である。 よってFは「プログラムAは300行以下である」のようなものであってはならない。
そして「Aが与えられたとき、fAは性質Fを満たすかを決定せよ」という問題を考える。 ライスの定理は、Fが自明なものでない限り、この問題を常に正しく解く事できるプログラムは存在しない、というものである。
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)を実行する。よって f T A , x = f V {\displaystyle f_{T_{A,x}}=f_{V}} 。したがってH(A,x)=M(TA,x)=M(V)=YES。
A(x)が停止しなければ、TA,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(TA,x)=M(U)=NO。