1

私はの証拠を見てきました

ATM = {〈M,w〉 | M is a TM and M accepts w} is undecidable.

最初に別のチューリングマシンを構築します

H入力を使用し て、別のチューリングマシンを作成する<M,w>場合は受け入れますM accept w otherwise reject

D which on input <M>
1.run H on <M,<M>>
2.output the opposite of what H outputs.

That is if H accepts reject and if H reject accept

入力としてのチューリングマシンが独自の説明を取得し、それを拒否する可能性があるのか​​わかりません。説明してもらえますか？

4

2 に答える 2

1

マシンへの入力には特別なステータスはなく、要件もありません。マシンはそれ自体を自由に拒否できます。:)

チューリングマシンを構築する気がしないので、Javaでの単純化された例を次に示します（これは、チューリングの完全性に十分に近いため、説明に役立ちます）。

class SelfReject {
    public boolean equals(Object other) {
        ...
    }

    public boolean accepts(Object input) {
        return (!this.equals(input));
    }
}

このタイプのオブジェクトは、それ自体に等しいオブジェクト以外のすべての入力を受け入れます。

于 2013-02-10T02:32:39.430 に答える
1

どこで行き詰まったのかわからないので、多かれ少なかれあなたの質問を繰り返して、うまくいけばギャップを埋めようと思います。

アイデアは、ATMが決定不能であること、つまりTM Hがないこと、つまり、別のTMMとこのTMMへの他の入力wが入力として与えられると、TMMが入力wを受け入れるかどうかを決定できることを示したいということです。 。

そのようなTMHが存在しないことを示すために、ASSUMPTIONをそのようなマシンHが存在するようにします。少なくとも十分な幻想があれば、それはあまりにも不合理な推測ではないように思われるかもしれません。

次のアイデアは、そのようなTM Hの存在が、私たちの議論を矛盾に導く結果を推測することによってです。したがって、そのようなTMHが存在する可能性があるという最初の仮定が間違っているに違いありません。つまり、上記の仕様に従ったTMHは存在しません。

トリッキーな部分に移りましょう。TMHが存在すると仮定したので、このTM Mに任意のTMMと任意の入力wを入力すると、Mが受け入れるかどうかを決定できます。マシンM自体は、入力wをM自体に入力します。任意の入力を使用する可能性があると仮定しました。

すでに上で述べたように、別のマシンへの入力として任意のマシンをフィードするというアイデアは、簡単に達成できるようには思えないので、最初のTMのテープに2番目のTMの説明をエンコードしようとします。

一見すると、テープ上の任意のTMをエンコードできるかどうかは明確に見えないかもしれませんが、実際には可能です。これを達成するための可能な計画の1つは、数学者のKurtGödelにちなんで名付けられたGödelisierungの名前です。

エンコーディング自体は、ゲーデル数とも呼ばれます。

入力としてMへの任意のTMMおよび任意の入力wの記述が与えられた場合、Mがwを受け入れるかどうかを決定するという、TM Hを考えると、前述の自由を使用して、TMMの記述をそれ自体への入力として使用します。

したがって、入力としてTM Mの記述が与えられたときに、入力としてそれ自体の記述に取り組んでいるTMMが受け入れるかどうかを決定するTMH'を構築します。

うまくいけば、上記のTM Hの仮定から始めると、「禁止された」移動は行われていません。新しく構築されたTM H'を使用してTMDを構築する場合は、実行しません。入力としてのTMMは、マシンH'とは反対の出力を返すだけです。

この新しいTMDは、入力としてANY TM Mの説明が与えられた場合、Mが入力として独自の説明を受け入れない場合は>を受け入れ、TMMが入力として独自の説明を受け入れる場合は>拒否します。

ご覧のとおり、Dへの入力として任意の（a）TM Mをフィードする自由がまだあります。したがって、自由をもう一度使用して、TMD自体の説明を入力として使用することを禁止することはできません。

私たちの構造によれば、Dは入力として任意のTM Mで動作するため、それ自体で動作できる必要があります。

しかし、まさにここにひねりがあります。実際のところ、入力としての独自の記述に基づいてDを実行した結果を判断するには、可能性があります。Dは受け入れるか拒否します。

次に、両方のケースを調べてみましょう。

Dがそれ自体の記述を私たちの構造による入力として受け入れる場合、これはDが拒否しなければならないことを意味します。逆もまた同様です。自身の説明を入力として受け入れたのはTMH'であり、構造内でそれを反転したことを思い出してください。

したがって、Dがそれを受け入れた場合にのみ、Dが入力としての自身の記述を拒否しなければならないという奇妙な事実に私たちを導きます。

これは明らかに可能ではないので、私たちが構築で行ったエラーの原因を見つける必要があります。私たちが再び作り上げた道全体をたどると、これは、ATMが決定可能であるという私たちの仮定によって暗示される、Mがwを受け入れる場合、任意のTMMおよび任意の入力wを決定できるTMHがあったという最初の推論につながります。

于 2013-02-10T03:06:23.477 に答える