ランダウの計算と停止性問題についての記事をいくつか読んだことがあります。明らかに、すべてのアルゴリズムが停止するかどうかを言うことはできません。たとえば、次のようになります。
while(System.in.readline()){
}
しかし、そのようなプログラムの大きなものは何でしょうか？定義されていないと思います。同じ理由で、停止するかどうかを判断することはできません。あなたはそれを知りません。
だから...いくつかの可能なアルゴリズムがありますが、それが停止するかどうかはわかりません。しかし、あなたが言うことができないなら、そのアルゴリズムの大物は定義上未定義です。
ここで、私の要点として、ソフトウェアの大部分を計算します。なぜあなたはそれをするプログラムを書くことができないのですか？関数であるか、定義されていないためです。
また、プログラミング言語については何も言っていません。純粋に関数型プログラミング言語はどうですか？そこで計算できますか？
では、チューリング マシンについて話しましょう (ランダム アクセス モデルを使用した同様の議論を行うこともできますが、簡単にするためにこれを採用します)。
TM の時間計算量の上限は、入力サイズに応じて TM が行う遷移数の増加率の順序について何かを示しています。具体的には、TM が入力サイズ n に対して最悪の場合に O(f(n)) であるアルゴリズムを実行すると言う場合、n > n0 に対して T(n) <= cf(n)。ここまでは順調ですね。
さて、チューリングマシンの特徴は、停止に失敗する可能性があることです。つまり、一部の入力に対して永久に実行できるということです。明らかに、ある n* > n0 に対して TM が無限のステップ数を取る場合、最後の段落で説明した条件 (有限の n0、c) を満たす f(n) はありません。つまり、任意の f に対して T(N) != O(f(n)) です。わかった; 少なくとも n0 の長さのすべての入力に対して TM が停止することを確実に言うことができた場合、n0 の一部について、私たちは家から解放されます。問題は、これは停止問題を解決することと同じです。
したがって、次のように結論付けます。TM が入力 n > n0 で停止するのに永遠にかかる場合、複雑さの上限を定義できません。さらに、固定された有限の n0 より大きいすべての入力で TM が停止するかどうかをアルゴリズムで判断することは解決不可能な問題です。