Identify similar functions

Question

I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and for each input $i$, $f(i) = g(i)$. Moreover, the two functions $f$ and $g$ could be implemented in a completely different way, e.g. different algorithms that solve the same problem.

In my opinion, clone detection could be useful, but I cannot compare both tokens or ASTs since the implementations are completely different. A semantic comparison could be a possible solution, but are there other techniques that I can use?

Answer 1

The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer. Therefore, you'll need to make some tradeoffs. That will depend on the specifics of your particular application, so it's hard to recommend a particular technique without knowing how you plan to use it.