Is it possible to write a verifier that checks whether this program implements this algorithm?

Question

Given a program P written in C ++, can I write an algorithm that will find if 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 a fast sorting algorithm, and now, if I want to make sure that a person has actually implemented a quick sort algorithm. A person can actually implement some other sorting algorithm, and he will produce the correct output and transfer all the test files (black box testing). One way to do this is to study the source code. I want to avoid this manual effort and want to write a program that can do the job. Question: "Is it possible?".

Answer 1

From Rice Theor , you can't even decide at all whether a piece of code is a sorting function or not while studying the code. You can, of course, find out if it has a sorting effect for some finite set of inputs by running it with these inputs and examining the results.

Perhaps you can do something for the specific case of this target sorting algorithm by examining the array that is sorted during sorting, checking the invariants specific to the target algorithm. For example, each call in recursive quicksort will sort the subarray.

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

Following the comments, I suggest looking at the home page of Ahmad Taherkhani . He continued research in this area, including a 2012 article on this topic.

Answer 2

I was thinking and still thinking about stack / heap checks (given that you are testing and optimized solutions).
You can check the complexity of time and the overall complexity of the memory, which will narrow the results. even for Time: O (n lg n) for merging and quick sorting. you can allocate them with memory allocation, since they are N, Lg (n) in order.
you can also check what the original violation of the array is ... etc, but that is not critical.