問題タブ [decidable]

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

いわゆるユニバーサル言語 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 で与えられているように、非常によく似た推論を採用しているため、これは本当に当惑します。

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