Are Two Functions Equal?

[Edit] The general question seems incredibly hard to solve. Here is a significantly restricted version of this question. How do I determine equality of functions? lets say we have

Solution 1:

This is impossible according to Rice's theorem:

In computability theory, Rice's theorem states that, for any non-trivial property of partial functions, there is no general and effective method to decide whether an algorithm computes a partial function with that property.

If you restrict the domain of the functions to be finite, then you can trivially verify if ∀x: f(x) = g(x) using brute force, but this is not possible with an infinite domain.

Solution 2:

It's impossible to create a mechanism that, given two functions, always can determine if they always will return the same values.

This stems from the problem you're trying to solve being equivalent to the Halting problem.

Granted, you could make heuristics to do this, but there would always be cases where they wouldn't be able to determine it.

Assuming you narrow it down to halting functions on limited domain, it still isn't trivial to determine quickly. If we assume that input lies in {1, ..., n} and output lies in {1, ..., m}, there are m possible functions (for each input, there are n possible outputs). If you sample k points, you narrow it down, and make the probability of them being equal larger, but there are still m different functions it could be. So you could determine if it's probable that they're equal fairly quickly, but to be certain, you'd have to check all n possible input values.

If you want to do it in another way than by sampling, I do believe you'll have to do some sort of static analysis on the source code of the functions, which is all but trivial.

In addition, if the domain is not finite, Rice's theorem prevents such an algorithm from existing.

Solution 3:

Assuming you're talking about a family of JavaScript functions that are constrained to one integer argument, and which do not have visible external side-effects, I still think it's going to be generally not possible to determine equality. Consider this:

functiona(n) {
  var today = newDate();
  if (today.getFullYear() === 2012 && today.getMonth() === 1 && today.getDate() === 3)
    return0;
  return n * n;
}

That function looks a whole lot like

functionb(n) { return n * n; }

Except on 3 Feb 2012, when it will look exactly like:

functionc(n) { return0; }

If you're really talking about a practical piece of real software to perform such an analysis, and if you really don't have much control over the details of the functions to be tested, it doesn't seem possible. Perhaps you can construct a set of "rules" that the functions must follow, but even at that the prospect of determining equality without testing every value in the domain seems pretty remote.

edit — I just thought of something: what if your two functions return functions? Now, to determine whether f == g, you first have to figure out whether the functions returned by f(n) for all n are equal to the functions returned by g(n) for all n. Hmm ...

Solution 4:

There is no way to do this in general. You can test both functions for a random sample of inputs and check them for equality on those specific values, but in general it is infeasible to test every possible input.

Solution 5:

Proof verification systems like Coq and Agda may be able to do what you're looking for.