Is it possible to write a verifier that checks if a given program implements a given algorithm?

Question

Given a program P, written in C++, can I write an algorithm that find if the program P implements a particular algorithm? Is there any algorithm that solves this problem. Is this problem solvable?

For example I ask a person to implement quick sort algorithm and now if I want to make sure that the person actually implemented quick sort algorithm. The person can actually implement some other sorting algorithm and it will produce correct output and pass all testcases (black box testing). One way I can do this is look into source code. I want to avoid this manual effort and want to write a program that can do this job. The question is "Is that possible?".

Answer 1

From Rice's Theorem, you cannot even in general decide whether a piece of code is a sort function or not by examining the code. You can, of course, find out whether it has the effect of sorting for some finite set of inputs by running it with those inputs and examining the results.

You may be able to do something for the specific case of a given target sort algorithm, by examining the array that is being sorted during the sort, checking for invariants that are characteristic of the target algorithm. For example, each call in a recursive quick sort implementation will result in a subarray becoming sorted.

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

Following on from the comments, I suggest looking at Ahmad Taherkhani's home page. He has continued research in this area, including a 2012 paper on the topic.