0

別のプログラムをチェックするプログラムが存在できない理由について、論理的なアランチューリングの説明を見つけようとしています。

計算コースで学んだことを覚えていますが、今は解決策を見つけることができず、職場の誰かに説明する必要があります。

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

4

4 に答える 4

3

停止問題を探しています。

アラン・チューリングは 1936 年に、考えられるすべてのプログラムと入力のペアに対して停止問題を解決する一般的なアルゴリズムは存在しないことを証明しました。停止問題は、チューリング マシンでは決定不能であると言います。

于 2010-04-28T21:58:59.000 に答える
2

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

しかし、基本的に、十分に複雑なプログラムが停止可能かどうかを判断するには、そのプログラムを実行して実行パスをトレースする必要があります。つまり、別のプログラムを実行している 1 つのプログラムに戻ることになり、そのプログラムが停止しなければ、それを監視しているプログラムも停止しません。

それは、円周率の桁を計算するようなものです-- 止まりますか? 計算上の問題に悩まされているのとは対照的に、実行時に無限であるとどのように言えますか? その特定の問題が無限であることはわかっていますが、同様の他の問題はそれほど証明されていません。

于 2010-04-28T22:00:46.487 に答える
2

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

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

このメソッドが実際に を返すことはありnullませんが、型チェッカーはこれを認識できません。しかし、もっとスマートな型システムを作ることはできないのでしょうか?

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

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

停止問題infiniteComputationのため、型チェッカーは false を返すかどうかをチェックできません。

関連するもう1つの定理はライスの定理です。これはおそらく、停止問題よりも質問の内容に近いものです。

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

于 2010-04-28T22:16:52.407 に答える
0

バイロンの答えは、重要な情報を示しているはずです。余談ですが、特定のプログラムをチェックするプログラムを作成できます。持てないのは、任意のプログラムの正しさをチェックするプログラムです。

于 2010-04-28T22:02:03.663 に答える