是否可以编写一个验证程序来检查给定程序是否实现给定的算法？

Question

给定一个用C++编写的程序P,我可以编写一个算法来查找程序P是否实现了特定的算法吗？有没有解决这个问题的算法.这个问题可以解决吗？

例如,我要求一个人实现快速排序算法,现在如果我想确保该人实际实现了快速排序算法.该人实际上可以实现一些其他排序算法,它将产生正确的输出并通过所有测试用例(黑盒测试).我可以这样做的一种方法是查看源代码.我想避免这种手动操作,并希望编写一个可以完成这项工作的程序.问题是"这可能吗？".

Answer 1

根据Rice的定理,你甚至不能通过检查代码来决定一段代码是否是一个排序函数.当然,您可以通过使用这些输入运行并检查结果来确定它是否具有对某些有限输入进行排序的效果.

您可以通过检查排序期间正在排序的数组,检查特定于目标算法的不变量,为给定目标排序算法的特定情况执行某些操作.例如,递归快速排序实现中的每个调用都将导致子数组被排序.

================================================== ===============

继评论之后,我建议查看Ahmad Taherkhani的主页.他继续在这方面进行研究,包括2012年关于该主题的论文.