Automata-theory-rice-theorem

ライス定理

ライス定理は、チューリングマシンによって認識される言語の重要なセマンティックプロパティは決定できないと述べています。 プロパティPは、そのプロパティを満たすすべてのチューリングマシンの言語です。

正式な定義

Pが重要なプロパティであり、そのプロパティを保持している言語L〜p〜がチューリングマシンMによって認識される場合、L〜p〜= \ {<M> | L（M）∈P}は決定不能です。

説明とプロパティ

• 言語のプロパティPは、単なる言語のセットです。 Pに属する言語（L∈P）の場合、LはプロパティPを満たすと言われます。
• プロパティは、再帰的に列挙可能な言語によって満たされない場合、またはすべての再帰的に列挙可能な言語によって満たされる場合に、自明であると呼ばれます。
• 自明ではないプロパティは、再帰的に列挙可能な言語によって満たされ、他の言語では満たされません。 正式に言えば、L∈Pの非自明なプロパティでは、次の両方のプロパティが成り立ちます。
• *プロパティ1 *-同じ言語を認識するチューリングマシンM1およびM2が存在します。 （<M1>、<M2>∈L）または（<M1>、<M2>∉L）
• *プロパティ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でM〜0〜を実行します。 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も決定不能です。