ある入力に対して有限時間内にあるプログラムが停止するかどうか判定する
チューリング機械のアルゴリズムは作成不可能だとする結論がすでに出ている。
しかしそれはチューリング機械に限っての話である。
我々か普段目にするパソコンなどの一般的な機械はチューリング機械などではなく
ノイマン型の機械である。
しかもその内部に保持できる状態は高々有限個である。よって、停止しないときは、
必ず開始から有限時間内に無限ループ状態に突入する。そして無限ループ中のあるときに現れた状態は
必ず有限時間内に再び現れる。それを検出すれば無限ループ＝停止しないと結論できる。
また、有限時間内に停止するなら、そのプログラムを順に追っていけば有限時間内に停止するか判定でき、
判定アルゴリズムもまた有限時間で停止する。
つまりこのようなアルゴリズムなら停止問題を解けるはずである。
空のリスト空間Ｌを作成＝＞①作成プログラムＡを1ステップ実行=>その状態と同一のものがＬにあるか判定し結果をＢとする|||
If(Bが真）｛
結果「停止しない」を返す。
｝else{
Ｌに現在の状態を追加し①に戻る。
}
この過程の途中、①の結果Ａが終了したとき結果「停止する」を返す｜｜｜｜
よって停止問題を解くアルゴリズムはコンピュータアーキテクチャ（しかも現在広く使われているものも）によって
は可能となることがある。
===========================＝＝＝＝＝＝＝＝
個の考えは今さっき思いついたものなのですが正しいですか？
大学でチューリングの機械でできないものはノイマン型でもできないと教わった（ようなきがするだけで間違いかもしれませんがが）
のですが。
プログラムというのは直前の状態と最初に与えられた処理手続きだけで次の状態が決定する
（オートマトンの拡張）のでたぶん間違ってはいないと思うのですが。