[解決済み] T = {<M> | Mはwを受け入れるときはいつでも$w^R$を受け入れるTMである}とする。Tが決定不可能であることを示せ

質問

T = {<M> | Mはwを受け入れるTMであるとする。 ^r wを受け入れるたびに}。
Tが決定不可能であることを示せ。

この質問には2つの答えがあります -。 サンディエゴ :

5.9
T = { <M> | Mはwを受け入れるTMであるとする。 ^r wを受け入れるたびに}。

Tが決定可能であると仮定し、決定者RがTを決定するようにする。 Aから削減 <サブ TM を構成して、以下のようにTM Sを作成する。

• S: 入力時 <M,w>
  1. は、次のようにTM Qを作成する。
     入力xに
     1. x が 01 または 10 の形式でない場合、拒否する。
     2. x が形式 01 を持つ場合、受け入れる。
     3. else (x has form 10), Run M on w and accept if M accepts w.
  2. でRを実行する。
  3. Rが受け入れる場合はAccept、Rが拒否する場合はRefject。

SがAを決定するから <サブ TM これは決定不可能であることが知られているので、Tは決定不可能であることがわかる。

出典未公開。

• 5.12 を示す。 A <サブ TM ≤ <サブ m S をマッピングすることで、' M , w ' から ' M' ここで M' は次のTMである。

  • M' = "入力時 x :
    1. もし x = 01 とすると 受け入れる .
    2. もし x ≠ 10 ならば 拒否する .
    3. もし x = 10 シミュレート M について w .
       もし M 受け入れる w では 受け入れる もし M が停止し、拒否された場合 リジェクト ."

  もし、' M , w ' ∈ A <サブ TM では M 受け入れる w と L ( M' ) = {01,10}なので、' M' ' ∈ S .
  逆に、もし' M , w ' ∉ A <サブ TM では L ( M' ) = {01}なので、' M' ' ∉ S . したがって
  ' M , w ' ∈ A <サブ TM ⇔ ' M' ' ∈ S .

しかし、次のことが理解できません。

1- x と w の関係はどうなっているのか？

2- なぜ、2つのケースを考慮するのか？ M , w ' ∈ A <サブ TM と' M , w ' ∉ A <サブ TM ?

3- AがSに写像還元可能であれば、なぜSが決定不可能になるのか？

これらの点について、どなたか教えてください。

どのように解決するのですか？

教育サイトではないので、SOで質問するのは不適切だと思いますが、回答させていただきました。

1- x と w の関係はどうなっていますか？

回答1: xは、操作するための記号を使用するための記号です。この記号は言語のアルファベットにはないはずで、ただそれだけです。それは とは何の関係もありません。

2- なぜ「M, w」∈ATMと「M, w」∉ATMの2つのケースを考えるのでしょうか？

回答2: Lのような言語が決定可能かどうかを証明するためには、wのような文字列が言語のメンバーであるかどうかを判断する必要があります。そこで は、2種類の文字列w∉Lとw∈Lを考えなければならない。

3- AがSに還元可能な写像である場合、なぜSが決定不可能になるのでしょうか？

回答3． ある文字列が言語化されているかどうかを確認するプロセスはAとSで類似しており、もし確認するためのアルゴリズムが見つからなければ Aのアルゴリズムは、Sにも適用できない。