C++ で記述されたプログラム P が与えられた場合、プログラム P が特定のアルゴリズムを実装しているかどうかを検出するアルゴリズムを記述できますか? この問題を解決するアルゴリズムはありますか。この問題は解決可能ですか?
たとえば、クイックソートアルゴリズムを実装するように人に依頼し、その人が実際にクイックソートアルゴリズムを実装したことを確認したい場合。その人は実際に他のソートアルゴリズムを実装することができ、それは正しい出力を生成し、すべてのテストケースに合格します (ブラックボックステスト)。これを行う 1 つの方法は、ソース コードを調べることです。私はこの手作業を避け、この仕事をできるプログラムを書きたいと思っています。「それは可能ですか？」という質問です。
ライスの定理から、コードを調べるだけでは、コードの一部がソート関数であるかどうかを判断することさえできません。もちろん、有限の入力セットに対してソートの効果があるかどうかは、これらの入力を使用して実行し、結果を調べることで確認できます。
特定のターゲットソートアルゴリズムの特定のケースに対して、ソート中にソートされている配列を調べ、ターゲットアルゴリズムの特徴である不変条件をチェックすることで、何かを実行できる場合があります。たとえば、再帰的なクイック ソートの実装で呼び出しを行うたびに、部分配列がソートされます。
================================================== ===============
コメントに続いて、Ahmad Taherkhani のホームページを見ることをお勧めします。彼は、このトピックに関する 2012 年の論文を含め、この分野の研究を続けています。
私は考えていましたが、スタック/ヒープチェックについても考えていました（最適化されたソリューションに対してもテストしている場合）。
時間の複雑さと全体的なメモリの複雑さを確認して、結果を絞り込むことができます。時間の場合でも：マージおよびクイックソートの場合はO（n lg n）。それらは順番にN、Lg（n）であるため、メモリ割り当てで区別できます。
元のアレイの乱れなどをチェックすることもできますが、これは決定的な重みではありません。