Can an algorithm analyze the behaviour of a function and say if another function does exactly the same?

Question

Can an algorithm analyze the behaviour of a function and say if another function does exactly the same? For example, I have a function that clean input data but I need to know if another function does the same thing in another way, using different code.

There exist such algorithm? Is this an undecidable problem?

Answer 1

Yes, it is undecideable.

The reduction is simple, given an instance of halting problem (f,x) build a new function f' that does not stop for x. Produce (f,f',x) as input to the new algorithm.

Intuitively, if such a machine exists, you just solved halting problem because you'll be able to detect that f and f' have the same behavior, but you know that f' is in an infinite loop, so - so does f.

As a side note, if you are looking for an algorithm that checks ALL inputs, and not a single input - this is even harder, and this problem is not even in RE

Answer 2

It is indeed undecidable.

It's at least as difficult as the halting problem.

Given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.

Part of determining whether 2 functions do the same for any given input would be to determine whether both actually halt for their respective inputs.