1

理論コンピュータ サイエンスの分野から質問があります。

いわゆるユニバーサル言語 L_u は、w \in L(M) となる (M, w) のペアで構成されます。言語 L_ne は、空ではない言語を持つマシン M (実際には、それらの説明ですが、ここではあまり厳密ではありません) で構成されています。L_u と L_ne はどちらも非再帰的ですが、RE (再帰的に列挙可能) であることは誰もが知っています。一方、RE でさえない L_u (L_nu と呼びましょう) の補数です。

L_nu を L_ne に簡約できれば、L_ne も非 RE であることを証明できます。これは、そのような削減は不可能であることを意味します。しかし、なぜそれが必要なのかわかりません。

まず、言語 L を L' に還元するには、L の考えられる各正のインスタンスを L' の正のインスタンスに、L の考えられる負の各インスタンスを L' の負のインスタンスにマッピングする計算可能な関数 f を作成する必要があります。それだけですよね？

第二に、万能チューリングマシン (UTM) には YES 状態と NO 状態の 2 つの最終状態があると安全に想定できると思います。もちろん、与えられた入力 (M, w) に対して w \not\in L(M) の場合、UTM は決して NO 状態にならないということが起こり得ますが、UTM が停止した場合、 YES 状態または NO 状態のいずれかでそうします。それも正しいですね。

次に、次のように L_nu を L_ne に減らしてみましょう: ペア (M, w) が与えられた場合、UTM のロジックを使用して w で M を実行し、UTM が YES と答えた場合は NO と答え、その逆の場合は NO と言うマシン M' を構築します。明らかに、L_nu の正のインスタンス (w \not\in L(M)) は L_ne の正のインスタンス (この場合、M' は常に YES と言うため、L(M') は空ではありません) と L_nu の負のインスタンス ( w \in L(M)) は、L_ne の負のインスタンスに変換されます (L(M') は空です。M' は常に NO と言うからです)。マシン M' は明らかに、少なくともいくつかの正の入力に対して永久に実行されます(UTM を永久に実行させる w \not\in M を持つペア (M, w) が少なくとも 1 つあるため)。計算可能です: M' のコードには、UTM のコード (これは確実に実行できます) と、(M, w) に適用された場合に組み込みの UTM が YES 状態に到達したかどうかをチェックする単純なロジックが含まれています。 NO状態に。それはそれについてです。

これにより、L_ne が非 RE であることを「証明」しました。しかし、そうではないので、どこかで間違っているに違いありません。L_u から L_ne への標準的な簡約は、たとえば Hopcroft-Ullman-Motwani で与えられているように、非常によく似た推論を採用しているため、これは本当に当惑します。

誰かがこのなぞなぞを解決するのを手伝ってくれたら、私は感謝します!

4

1 に答える 1

0

この質問が飛び交うのを見たことがありますが、かなり難しいので答えるのをためらっています。問題が何であるかを指摘しようとする以下の解決策を試みました。これを注意深く読んで、私が提案しようとしていることに従っているかどうかを確認してください. 以下で詳しく説明するように、この問題の真の核心は、w で M を実行している UTM が、M が w で停止しない場合を正しく処理しないことだと思います。M が w で停止しない場合、(M , w) は L_nu にありますが、w で M を実行している UTM はそれを知ることができません。

L_ne の決定者がいる場合、L_nu を決定できますか?

L_nu 問題の入力はペア (M,w) です。次の 3 つのケースがあります。

  1. M は入力 w の停止受け入れに入ります: no を返します
  2. M は、入力 w に対して停止拒否に入ります: yes を返します
  3. M は入力 w に対して決して停止しません: 決して停止しないということは M が w を受け入れないことを意味するため、yes を返します。

UTM を使用して w で M を実行し、逆の結果を返すマシン記述 M' を確実に計算できます。次の 3 つのケースがあります。

  1. M' は、入力 w の停止受け入れに入ります: yes を返します
  2. M' は入力 w の停止拒否に入ります: no を返します
  3. M' は入力 w に対して停止することはありません: ループに陥る可能性は決してないため、これは no にマップする必要があります。

L_ne のディサイダー M'' があり、それに M' を入力すると、何が得られるでしょうか?

  1. 最初のケースでは、M'' はすべての入力を受け入れるため、M'' は yes を返します。
  2. 2 番目のケースでは、M'' は入力を受け入れないため、M'' は no を返します。
  3. 3 番目のケースでは、M'' は入力を受け入れないため、M'' は no を返します。

3 番目のケースでは、L_ne のディサイダーである M'' は、言語 L(M'') は空であると言いました。ただし、言語が空である理由はわかりません。M' の負のケースのいずれかである可能性があります。M' が明示的に停止拒否に入ったことが原因である場合、w が L(M) にあることがわかっているため、還元は「いいえ」と答えるはずです。M' が w で永久に実行されたことが原因である場合、M が w で停止しないことがわかっているため、リダクションは「はい」と答えるはずです。

M'' の実行時にこれら 2 つのシナリオを区別できないため、リダクションは失敗します。なぜ失敗したのですか？w で M を実行している UTM である M' は、M が w で停止に失敗した場合に正確に停止受け入れに入ることができないため、失敗しました。M' は、処理が永遠に続くことを知っているポイントに到達するとは限りません。一般に、M' は永久に実行する必要があり、そのような場合、L(M') は空になります。

于 2021-02-10T14:02:34.150 に答える