私は最近、問題の矛盾を止める問題を見つけました。 校正では、チューリングマシンにプログラムのコピーと入力のコピーを供給して、そのプログラムが入力で停止するかどうかを判断する必要があります。矛盾では、なぜそれがプログラムとインプットとしてのプログラムでなければならないのでしょうか？混乱して聞こえる場合は申し訳ありません。私は単純にプログラムとランダムな入力をマシンに送り、同じ結論に達することができます。"haltingproblem"矛盾の証
誰でも私にその理由を教えてもらえますか？私が考えなかった具体的な理由はありますか？
まず、私は校正自体に戻ってきてください。
HALT_TMは
決定不能である任意のマシンは、文字列の形式をとる記述されていると仮定する。 HALT_TM = {<M, w>| M is a TM and M halts on input w}、およびA_TM = {<M,w>| M is a TM and accepts w}とします。ここで私はA_TMが決定不能であることを知っていると仮定しています（証明は対角化で行い、チューリングマシンよりも多くの言語があり、特定のTMだけが1つの言語を決定するので、いくつかの言語は決定されません）。
矛盾して、HALT_TMが決定可能であると仮定します。つまり、この言語にはデシリアのDが処分されます。それでを決める機械Mを作ることができます。 Dは、リジェクト、そうでない場合はw上M'を実行する場合、入力<M',w>
D
<M', w>で、
Mは、次の処理を行い（
Dが拒否していなかったので、それは我々が知っている、停止するまで！）
M'が受け入れる場合は受け入れ、拒否する場合は拒否します。あなたが実際には必ずしも<M>自体、Mに有効な任意のマシン記述M'を養う：があり、私たちは今、あなたの質問の核心は、当社の仮定
ユニバーサルチューリング機械
と矛盾を参照してください。 TMと「プログラム」は実際には同等であることを覚えておいてください。詳細はanswerをご覧ください。同じ回答を引用すると、「チューリングマシンはアルゴリズムの正式なアナログです」です。 Turing Machineの強力な機能の1つは、文字列としてエンコードでき、別のチューリングマシン（「Universal Turing Machine」と呼ばれます）がそれらを実行できるようにすることです。与えられたマシンはアルゴリズムなので、実際にあなたの "トップレベル" TMプログラムとあなたの選択の入力を与えていることがわかります。