ライスの定理 - Wikipedia

ライスの定理（ライスのていり、英: 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が同じになる事

[SWIMATH2]

"定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない"

[Nagatani]

[計算機科学]