A_LBAのE_LBAへの削減

Question

私は熟考するのにかなり面白いものを持っています、そして、私がそれのために答えを得ることができれば好きになるでしょう。コンピューティング理論コースで今日のマッピング削減のトピックについて議論していましたが、なぜこの削減が存在できないのか疑問に思っていました。 （LBAS）。 $ e_ {lba} $が決定不可能であり、$ a_ {lba} $は決定可能であり、通常の証明は$ a_ {tm} $、または$ e_ {tm} $を使用して$ e_ {{e_ {{tm {tm} $を使用します。 LBA} $。この証拠がTMを使用してLBAを証明している理由が興味があります。しかし、私の教授は私の混乱の解決策を思い付くことができませんでした。もしそうなら、なぜ、なぜそうでないのかと思っていました。

定義：

$ a_ {lba} = { langle m、w rangle mid text {$ m $は、文字列$ w $} } $を受け入れる線形バインドオートマトンです。

$ e_ {lba} = { langle m rangle mid text {$ m $は、$ l（m）= emptyset $} }を備えた線形バインドオートマトンです。

$ a_ {tm} $および$ e_ {tm} $は、マシンをチューリングするための同等の問題です。

Answer 1

あなたは間違った方法をマッピングしています。現状では、決定不可能な問題から決定できない問題への削減になります。確かに可能です（以下を参照）が、何も教えてくれません。

$ a leq_ {m} b $の場合、$ b $を解くアルゴリズム（またはこの場合の決定を決定する）を使用して$ a $を解くことができることを思い出してください（$ a $のメンバーシップを決定）。したがって、あなたが見ている削減は、$ e_ {lba} $の決定者を使用して$ a_ {lba} $を決定できることを教えてくれます。また、$ e_ {lba} $が決定不可能であることも知っていますが、これは$ e_ {lba} $を決定しない$ a_ {lba} $の決定者が存在することを妨げません。

実際、存在できない削減は$ e_ {lba} leq_ {m} a_ {lba} $です。これは、$ e_ {lba} $を決定できることを意味するためです。

2番目の部分では、$ e_ {lba} $が決定不可能であるという証明（またはむしろ可能な証明の1つ）は、マッピング$ a_ {tm} leq_ {m} e_ {lba} $を構築することです。 $ e_ {lba} $の決定者は、$ a_ {tm} $の決定者を提供しますが、$ a_ {tm} $が決定不可能であることがわかっているため、$ e_ {lba} $も決定できない必要があります。

について どうして この証明は、チューリングマシンを含む言語を使用して、線形バインドオートマトンについて何かを示すことです。これは機能するためです。

削減

$ a_ {lba} $が決定可能であるため、入力lba $ m $およびstring $ w $を取得し、$ langle m、w rangle $で決定者を実行できます。それが受け入れる場合、これをすぐに拒否するLBA $ m_ {rej} $にマッピングします。決定者が拒否した場合、すぐに受け入れるLBA $ m_ {acc} $にマップします。したがって、$ m_ {acc} $はすべての入力を受け入れ、$ e_ {lba} $ではなく、$ m_ {rej} $はすべての入力を拒否し、$ e_ {lba} $です。

もちろん、この削減はある意味で些細なことであり、$ e_ {lba} $のサブセットは有限であり、したがって決定可能です（通常も！）。

別の視点

2つの言語が$ a $ a $ b $と$ a leq_ {m} b $を与えられると、2つの基本的な（便利な）ものがあります そうかもしれない 言うことができる：

• $ b $がIFの場合 決定可能 その後、$ a $も決定できます。
• $ a $ isの場合 決定不可能です その後、$ B $も管理できません。

私たちの場合、$ a $は決定可能であり、$ b $はこれらの可能性のどちらも一致しないため、$ a_ {lba} leq_ {m} e_ {lba} $は決定可能性について何も教えてくれませんいずれかの。