Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs
No.  That's undecidable.  Suppose the first program is

return 42


and the second program is

if (f(x) halts)
    return 0
else
    return 42


where x is the input.

Do these two programs yield the same output, for all possible inputs?  That depends whether f always halts on all inputs.  And that is exactly the halting problem, which we know is not decidable.  It's easy to see that, as a consequence, this problem can't be decidable either (if it were, you could decide the halting problem).