プログラミングに関連する停止の問題について人々が尋ねるときはいつでも、人々は「ループを 1 つ追加するだけで、プログラムが停止することになり、タスクを自動化できなくなります」と答えます。
理にかなっています。プログラムに無限ループがある場合、プログラムの実行中に、プログラムがまだ入力を処理しているのか、それとも無限ループしているだけなのかを知る方法はありません。
しかし、これには直観に反するものもあります。ソース コードを入力として受け取る停止型問題解決プログラムを作成していたとしたらどうでしょう。rascher@localhost$ ./haltingSolver source.c
私のコード (source.c) が次のようになっている場合:
for (;;) { /* infinite loop */ }
私のプログラムがこれを見るのはかなり簡単なようです。「ループを見て、条件を見てください。条件がリテラルのみに基づいており、変数がない場合、ループの結果は常にわかります。変数がある場合 (たとえば、while (x < 10))、これらの変数は常に変更されます。そうでない場合は、ループの結果が常にわかります。」
確かに、これらのチェックは簡単ではありません (ポインター演算の計算など) が、不可能ではないようです。例えば：
int x = 0
while (x < 10) {}
検出できました。とともに - 自明ではありませんが:
int x = 0
while (x < 10)
{
x++;
if (x == 10)
{
x = 0
}
}
では、ユーザー入力についてはどうでしょうか。それがキッカーであり、プログラムを予測不能にするものです。
int x = 0;
while (x < 10)
{
scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}
これで私のプログラムは、「ユーザーが 10 以上を入力すると、プログラムは停止します。それ以外のすべての入力では、再びループします」と言うことができます。
つまり、何百もの入力があっても、プログラムが停止する条件をリストできるはずです。実際、私がプログラムを書くときは、必ず誰かがプログラムを終了できるようにしています! 結果として得られる条件のリストを簡単に作成できると言っているわけではありませんが、不可能ではないように思えます。ユーザーからの入力を取得し、それらを使用してポインターインデックスを計算することもできますが、それはプログラムが確実に終了するように条件の数を追加するだけであり、それらを列挙することを不可能にするわけではありません.
では、停止の問題とは正確には何ですか？無限ループを検出する問題を書くことができないという考えについて、私が理解していないことは何ですか? または、なぜ「ループ」がそのようなよく引用される例なのですか?
アップデート
では、質問を少し変えさせてください。コンピューターに適用される停止問題とは何ですか? そして、いくつかのコメントに返信します。
多くの人が、プログラムは「任意の入力」を処理できなければならないと言っています。しかし、コンピューターでは、任意の入力はありません。1 バイトのデータのみを入力すると、可能な入力は 2^8 しかありません。したがって、例として：
int c = getchar()
switch (c) {
case 'q':
/* quit the program */
}
突然、すべての可能性を説明しました。cビットパターンが 0x71 の場合、1 つのことを行います。他のすべてのパターンでは、別のことを行います。リソースは有限であるため、任意の文字列入力を受け入れるプログラムでさえ、実際には「任意」ではありません。つまり、「任意」の理論が適用されますが、実際には正確に 1 対 1 ではありません。
人々が引用した他の例は次のとおりです。
while (n != 1)
if (n & 1 == 1)
n = 3 * n + 1;
else
n /= 2;
n が 32 ビットの整数である場合は、これが停止するかどうかを視覚的に判断できます。
この編集は何も求めていないと思いますが、私が見た中で最も説得力のある例は次のとおりです。
プログラムの停止を判断するための魔法のプログラム/メソッドがあるとします。
public bool DeterminesHalt(string filename, string[] args){
//runs whatever program you tell it do, passing any args
//returns true if the program halts, false if it doesn't
}
さて、次のような小さなコードを書いたとしましょう...
public static void Main(string[] args){
string filename = Console.ReadLine(); //read in file to run from user
if(DeterminesHalt(filename, args))
for(;;);
else
return;
}
したがって、この例では、魔法の停止方法とは正反対のことを行うプログラムを書くことができます。特定のプログラムが停止すると何らかの形で判断した場合、無限ループに飛び込みます。それ以外の場合、プログラムが無限ループにあると判断した場合は、プログラムを終了します。
繰り返しになりますが、意図的に無限ループを含むプログラムを作成すると... 「停止問題を解決する」というのはちょっと意味がありませんね。