問題タブ [halting-problem]

ループで使用System.currentTimeMillis()するJavaの次のコードセグメントを見てみましょう。for

上記のコードでは、final long型変数はシステムによって維持される現在のミリ秒を保持します。これは、ループが無限ループに陥っていても、Javaのデータ型のサイズCURRENT_MILLISよりも常に小さくなります。どのように？(MAX_VAL)longfor

コレクション内の値が異なる場合、このアルゴリズム (疑似コード) は終了しますか?

配列の最後にいる場合は、最初からやり直すと想定していることに注意してください。

好奇心から、私は次の方法を書くようになりました：

なぜJavaでこれを書くことができるのでしょうか？このメソッドは何も返さずObject、結果としてStackOverflow Error。

ここには SO に関する多くの関連する質問がありますが、それらはすべて、任意のアルゴリズムの複雑さを計算するプログラムを作成することについて質問しています (これは明らかに判断できません)。入力に対して次の制限を設けます。

1. アルゴリズムは終了します
2. アルゴリズムは純粋に機能的です

問題は、静的解析を通じてそのようなアルゴリズムの時間計算量を計算するプログラムを作成できるかということです。入力アルゴリズムが終了しない場合、プログラムの動作は未定義です (クラッシュするか、嘘を返すか、終了に失敗する可能性があります)。

すべての agda プログラムが終了する場所がいくつか述べられています。ただし、次のような関数を作成できます。

シンタックス ハイライターは気に入らないようですが、コンパイル エラーはありません。

の正規形を計算すると、stall 0になります0。の結果を計算するとstall 1、Emacs は終了しないループのように見える状態でハングします。

これはバグですか？それとも、Agda は永久に実行されることがありますか? それとももっと微妙なことが起こっていますか？

停止問題は、あるプログラムが別のプログラムの出力を予測すること、またはプログラムが終了するかどうかを予測することは不可能であると述べています。

それは私に考えさせました... ヒューリスティックベースのスキャナーは、特定の実行可能プログラムの命令が「ウイルスに似ている」かどうかをどのように判断しますか?

したがって、入力 x を持つチューリング マシン M が停止するかどうかを判断するユニバーサル チューリング マシン U があります。ソリューションは疑似コードで提示する必要があります。

誰かが私を少し助けてくれますか? 誰が解決すればいいですか?

FindBugs特定のプログラム/コードベースで無限に終わることのないループを検出できるというツールがあります。

これFindBugsは、コードを分析することで、プログラムが終了するかどうかを検出できることを意味します。停止問題は、次のことを定義する問題です。

任意のコンピュータ プログラムの説明を与えられて、そのプログラムが実行を終了するか、永久に実行し続けるかを決定します。

これは、停止問題が解決されたこと、または停止問題のサブセットが解決されたことを意味するのでしょうか?