給定一個用C++編寫的程序P，我可以編寫一個算法來查找程序P是否實現了特定的算法？有沒有解決這個問題的算法。這個問題是否可以解決？是否可以編寫一個驗證程序來檢查給定的程序是否實現了給定的算法？
例如我要求一個人實現快速排序算法，現在如果我想確保該人實際實現了快速排序算法。這個人實際上可以實現一些其他的排序算法，它會產生正確的輸出並通過所有的測試用例（黑盒測試）。我可以做的一個方法是查看源代碼。我想避免這種手動的工作，並想編寫一個可以完成這項工作的程序。問題是「這可能嗎？」。
從Rice's Theorem，你甚至不能通過檢查代碼來判斷一段代碼是否是一個排序函數。當然，您可以通過運行這些輸入並檢查結果來確定它是否具有排序某些有限輸入的效果。
通過檢查排序期間正在排序的數組，檢查目標算法的特徵不變量，您可能可以爲給定目標排序算法的特定情況做些事情。例如，遞歸快速排序實現中的每個調用都會導致子數組變爲排序。
============================================== ===================
繼續從評論，我建議看看Ahmad Taherkhani's home page。他一直在這方面進行研究，包括2012年關於該主題的論文。
謝謝，真的有幫助。我想知道如果我們使用一些實現算法的示例程序，然後嘗試對程序進行分類，它是否會起作用。就像他們在機器學習問題中一樣。 – Aryaveer 2013-02-25 13:50:20
@Aaveaveer這樣做的關鍵是找到可以從文本中提取的特徵，使特徵空間中靠近的點表示相似的算法。我做了一些網絡搜索，並找到了[識別排序算法的靜態程序分析]（www.cs.hut.fi/~ahmad/mastersthesis.pdf）。這是2008年的一篇論文，但可能是引用搜索找到最新技術狀態的有用起點。 – 2013-02-25 16:40:59
我在想，並且仍然在考慮堆棧/堆檢查（假設您針對優化的解決方案進行了測試）。
您可以檢查會縮短結果的時間複雜度和整體內存複雜度。即使對於合併和快速排序的時間：O（n lg n）也是如此。你可以用內存分配區分它們，因爲它們是N，Lg（n）。
你也可以檢查原始陣列干擾等等，但這不是決定性的重量。
如何讓某人使用抽象接口進行一些低級操作，如訪問元素和交換。然後向它們傳遞一個具體對象，確保調用者以快速排序的方式調用這些操作。 – 2013-02-24 15:12:23