ライスの定理
ライスの定理は、チューリングマシンによって認識される言語の重要なセマンティックプロパティは決定不可能であると述べています。プロパティPは、そのプロパティを満たすすべてのチューリングマシンの言語です。
正式な定義
Pが自明でないプロパティであり、プロパティを保持する言語L pがチューリングマシンMによって認識される場合、L p = {<M> | L（M）∈P}は決定不能です。
説明とプロパティ
言語のプロパティPは、単に言語のセットです。いずれかの言語がPに属する場合（L∈P）、Lは特性Pを満たすと言われます。
プロパティは、帰納的可算言語で満たされない場合、またはすべての帰納的可算言語で満たされる場合、自明であると呼ばれます。
自明でない特性は、帰納的可算言語によっては満たされ、他の言語では満たされません。正式に言えば、L∈Pである自明でないプロパティでは、次の両方のプロパティが成り立ちます。
Property 1 −同じ言語、つまり（<M1>、<M2>∈L）または（<M1>、<M2>∉L）を認識するチューリングマシンM1とM2が存在します。
Property 2 −チューリングマシンM1とM2が存在し、M1は言語を認識しますが、M2は認識しません。つまり、<M1>∈Lおよび<M2>∉L
証明
プロパティPが自明ではなく、φ∈Pであると仮定します。
、Pは、少なくとも1つの言語を満たすP、すなわち、L（M非自明であるので、0）∈P、∋チューリングマシンM 0。
wを特定の瞬間の入力とし、Nを次のチューリングマシンとします。
入力xについて
- wでMを実行
- Mが受け入れない（または停止しない）場合は、xを受け入れない（または停止しない）
- Mがwを受け入れる場合は、xでM0を実行します。M 0がxを受け入れる場合は、xを受け入れます。
インスタンスをマッピングする関数ATM = {<M、w> | Mは、次のようなNへの入力w}を受け入れます。
- Mがwを受け入れ、NがM 0と同じ言語を受け入れる場合、L（M）= L（M 0）∈p
- Mがwを受け入れず、Nがφを受け入れる場合、L（N）=φ∉p
A TMは決定不能であり、Lpに減らすことができるため、Lpも決定不能です。