別のプログラムをチェックするプログラムがない理由

Question

私は、別のプログラムをチェックするプログラムが存在できない理由を論理的に説明しようとしています。

私たちは計算コースで学んだことを覚えていますが、今では解決策を見つけることができません。私の仕事でそれを誰かに説明する必要があります。

手伝ってくれてありがとう。

Answer 1

「別のプログラムのチェック」は非常に広いです。実際、プログラムのいくつかの機能 できる Javaプログラムタイプのチェックかどうかなど、チェックしてください。ただし、Javaプログラムのタイプチェックは、次のような実行時にタイプエラーを実際に生成することのないプログラムも拒否します。

int foo() {
    if (true) return 5;
    else return null;
}

この方法は実際に戻ることはありません null, 、しかし、タイプチェッカーはこれを見ることができません。しかし、よりスマートなタイプのシステムを作ることはできませんでしたか？

残念ながら、答えはノーです。次のプログラムを検討してください。

int bar() {
    if (infiniteComputation()) return 5;
    else return null;
}

タイプチェッカーは確認できません infiniteComputation のために、偽りを返します 停止の問題.

別の関連定理はです ご飯の定理, 、これはおそらく、あなたの質問が停止の問題よりも近いものに近いものです。

定理は、正確にチェックできるプログラムプロパティがないことのみを述べていることを指摘する価値がありますが、実用的な目的のためにそのようなチェックを十分に近似することはまだ可能です。 1つの例はタイプシステムです。上のスニペットのように、いくつかの「正しい」プログラムが拒否されることを受け入れます。コンパイラは、多くの場合に死んだコードを排除することもできますが、で行うことは不可能です 毎日 場合。

Answer 2

あなたはを探しています 停止の問題.

Alan Turingは、1936年に、可能なすべてのプログラム入力ペアの停止問題を解決するための一般的なアルゴリズムが存在できないことを証明しました。私たちは、停止の問題はチューリングマシンよりも容認できないと言います。

Answer 3

あります ウィキペディア これに関するエントリ...

しかし、基本的に、十分に複雑なプログラムが停止可能かどうかを判断するには、実行パスを追跡するためにそれを実行する必要があります。つまり、別のプログラムを実行しているプログラムに戻り、そのプログラムが停止しない場合、それを監視しているプログラムも停止しません。

数字をPIに計算するようなものです - 停止しますか？いくつかの計算上の問題に苦しむのではなく、ランタイムの無限であるとどのように言えますか？その特定の問題は無限であることを知っていますが、類似した他の問題はそれほど証明されていません。

Answer 4

バイロンの答えは、重要な情報を指摘する必要があります。余談ですが、特定のプログラムをチェックするプログラムを作成できます。あなたが持っていないのは、任意のプログラムを正しいことをチェックするプログラムです。