loops - コンパイラは無限ループ状態を検出できますか?

Question

カスタム言語用のコンパイラを構築しています。プログラムを実行せずに、コンパイラが無限ループ状態を検出することは可能ですか?

もしそうなら、どうすればそれを実装できますか？

Answer 1

いくつかの無限ループを検出できる場合もありますが、一般に、考えられるすべての無限ループを検出することはできません (カスタム言語が一般的なループ構造を排除するように特別に設計されている場合を除きます)。http://en.wikipedia.org/wiki/Halting_problemを参照してください。