$ _ {tm} $を補完するマッピング削減

Question

マッピングの削減について一般的な質問があります。 $ a_ {tm} $に関数を削減する例をいくつか見てきました

ここで、$ a_ {tm} = { langle m、w rangle： text {for} m text {stringを受け入れるチューリングマシン} w } $

これは、決定不能を証明するのに最適です。しかし、代わりに認識されないことを証明したいと言ってください。つまり、$ a $ a $が認識できない場合、$ a le_ {m} b $を与えられた結果を使用したい場合、$ b $は認識できません。

したがって、$ overline {a_ {tm}} $に削減できる任意の認識できない言語$ c $についてle_ {m} c $？

簡単にするには、$ overline {a_ {tm}} $でTMを単に考慮するだけで十分です。

編集

clarification、$ overline {a_ {tm}} = { langle m、w rangle：m text {stringを受け入れないチューリングマシン} w } $

Answer 1

$ l _ { emptyset} = { langle m rangle mid l（m）= emptyset } $を取りましょう。

次に、削減$ overline {a_ {tm}} le l_ emptyset $を表示します。削減は、入力$（ langle m rangle、w）$の$ overline {a_ {tm}} $を取得し、入力$ { langle tilde m rangle} $に変換することによって行われます。 emptySet $そのような

$$（ langle m rangle、w） in overline {a_ {tm}} quad text {iff} quad langle tilde m rangle in l _ { emptyset} $$

$（ langle m rangle、w）$が与えられると、次の方法で$ tilde m $を構築できます。入力yの$ tilde m $は次のとおりです。

1. テープを削除します
2. テープに$ w $を書きます
3. $ w $で$ m $を実行し、同じことを実行します（$ m $が受け入れた場合、$ tilde m $も同様に受け入れます）。

$ m $のコーディングから$ w $から$ tilde m $のコーディングを構築することが可能であると確信してください。次に、この削減が有効であることを確認しましょう。

• $（ langle m rangle、w） in overline {a_ {tm}} $の場合、$ m $は拒否または停止しません。もしそうなら、$ tilde m $は、入力$ y $についても$ y $を受け入れません。これは、$ l（ tilde m）= emptyset $したがって、$ langle tilde m rangle in l _ { emptyset} $を意味します。
• $（ langle m rangle、w） notin overline {a_ {tm}} $の場合、$ m $は$ w $を受け入れます。したがって、$ l（ tilde m）= sigma^*$は、$ langle tilde m rangle notin l _ { emptyset} $であることを意味します。

「iff」条件が保持され、$ overline {a_ {tm}} $の入力を$ l_ emptyset $の入力に正常にマッピングしました。この場合、$ overline {a_ {tm}} $を$ l_ emptyset $に削減しました。つまり、$ l_ emptySet $を解くことができれば、最初に入力を変換し、変換された入力で$ l_ emptySet $を解くアルゴリズムを実行することにより、$ overline {a_ {tm}} $を解くこともできます。

Answer 2

任意の認識できない言語$ c $については、$ overline {a_ {tm}} leq_m c $を表示することはできません。 $ overline {a_ {tm}} leq_m c $の場合、特に$ c $のチューリング程度が$ overline {a_ {tm}} $のチューリング度以上である場合。チューリングの削減を意味します。 $ overline {a_ {tm}} $のチューリングの程度は$ 0 '$であり、チューリングの$ a_ {tm} $と同じです。 $ 0 '$（$ 0' $以下）でチューリングの学位が比類のない言語がたくさんあります。

G.を実行した例は、特に$ l_ emptySet $が$ m $ overline {a_ {tm}} $に相当するため、作品を与えました。ほとんどの「自然な」問題は、$ m $ -degreeで互いに匹敵する傾向があるという一般的な現象があります。しかし、arbitrary意的な問題を見ると、これはもはや真実ではありません。