無限ループの検出
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/04/17 09:59 UTC 版)
無限ループは、通常、プログラマが原因を突き止めることができると簡単に考える者もいる[要出典]ようだが、次のような例を考えればそうでないことがわかる(簡単のため、数値は無限に大きな値を扱えるものとする)。 入力として、正の整数であるnをとる。 nが偶数の場合、nを2で割る。 そうでなければ、nを3倍して、さらに1を加える。 nが1なら終了する。 ステップ2に戻る。 上記はごく簡単なプログラムであるが、たとえば最初のnを27とすると、途中でnは最大9232となる。そして、このプログラムがどんなnに対しても終了するか、あるいはあるnで始めると無限ループとなってしまうかという問題はコラッツの問題と呼ばれ、2014年時点で未解決の問題である。 理論上、プログラムが停止するのか動き続けるのかを「どんなプログラムに対しても」「有限の時間内で」「必ず決定できる」ことを全て満たす方法は無い。これは停止問題の決定不能性からの結論である。
※この「無限ループの検出」の解説は、「無限ループ」の解説の一部です。
「無限ループの検出」を含む「無限ループ」の記事については、「無限ループ」の概要を参照ください。
- 無限ループの検出のページへのリンク