チューリングマシンの停止は何ですか？

Question

私は決定性には新しいです。私は問題を止めるという問題を止めたが、実際に何を意味しているのかは分からなかった。私はすでに説明をしています。

誰でも私に何か音の説明や少なくともいくつかの詳細を教えてもらえますか？多くの助けになるでしょうか？

Answer 1

チューリングマシンは、プログラムを実行できる理論的なコンピュータの一種と考えることができます。チューリングマシンのプログラムは、一連の状態とこれらの状態の間の遷移からなります。チューリングマシンで実行されているプログラムは、テープと呼ばれる単一の入力ソースにアクセスできます。テープには、プログラムが処理できる文字列（空の場合もあります）があります。チューリングマシンのすべてのプログラムは、return true（停止受け入れ）、return false（停止拒否）、またはreturn何も全く失敗します。。あなたの定義に応じて、マシンがthrowに例外（クラッシュ）する可能性もあります。一般にクラッシュは、try { /*crash*/ } catch (Exception) { return false; }のようなものであると考えられ、クラッシュが停止拒絶を意味する。

停止問題は、その後、あなたはtrueまたはfalse（停止-受け入れるか中止・拒否を返す入力チューリングマシンと入力のいくつかの文字列のための別のプログラムであるチューリングマシン、プログラムを書くことができるかどうかであります）与えられた入力が停止してプログラムが停止し、それ以外の場合はfalseを返します（つまり、プログラムが停止しない場合）。

答えは、チューリングマシン用の一般的なプログラムは存在しないということが分かります。存在したとします。M与えられた入力mとiは、mがiで停止し、それ以外の場合は拒否します。

1. Mが入力i上N停止と言っていたとします

   N(i) 
   1. if M(N, i) then loop forever; 
   2. otherwise return true 
   

   今N上M作品がいるかどうかを続行：私たちは、具体的Mをだますために設計された別のプログラムを作ることができます。その後、Nは永遠にループし、Mは間違っています。

2. Mには、に永久にループするNがあるとします。その後、Nはtrueを返し、停止するので、Mは間違っています。いずれの場合も

、Mは、私たちのNのための間違った答えを思い付く、と我々はそれが停止問題を存在し、解決していること以外にMに関する仮定をしないので、私たちは安全という機械はその解き締結することができます停止問題が存在します。

（Mを直接参照しないことが望ましい場合には、MをプログラムとしてNに入力することができます）。