Function equality on restricted functions

Question

I already posted a question about function equality. It quickly concluded that general function equality is an incredibly hard problem and might be mathematically disprovable.

I would like to stub up a function

function equal(f, g, domain) {

}

f & g are halting functions that take one argument. Their argument is an natural number. These functions will return a boolean.

If no domain is passed then you may assume the domain defaults to all natural numbers.

The structure of domain is whatever is most convenient for the equal function.

Another important fact is that f & g are deterministic. and will consistantly return the same boolean m for f(n).

You may assume that f and g always return and don't throw any exceptions or crash due to errors as long as their input is within the domain

The question is language-agnostic and Asking for an implementation of the equal function. i'm not certain whether SO is the right place for this anymore.

f & g have no side-effects. and the domain does not have to be finite.

score 3 · Accepted Answer · answered Jan 30 '11 at 17:19

It's still not possible.

You could test both functions for some finite number of inputs and check them for equality on those inputs. If they are unequal for any input then the two functions are not identical. If they are equal in every case you tested then there is a reasonable chance that they are the same function, but you can't be completely certain.

In general it is infeasible to test every possible input unless the domain is small. If the domain is a 32 bit integer and your function is quite fast to evaluate then it might be feasible to check every possible input.

For some value of "feasible". 2*4.3 billion numbers will for sure take more than a few minutes (and that's a modest guess because I don't feel like trying it) even with the identity function in C (assuming of course the compiler doesn't completely eliminate the loops), and a lot more for functions that are longer than those 2, 3 CPU instructions. — , Jan 30 '11 at 17:42

score 2 · Answer 2 · edited May 23 '17 at 12:26

I believe the following to be the best you can do without doing static analysis on the source code:

function equal(f, g, domain) {
    var n;
    for (n in domain) {
        if (f(domain[n]) != g(domain[n])) return false;
    }
    return true;
}

Note that this assumes the domain to be finite.

If the domain is not finite, Rice's theorem prevents such an algorithm from existing:

If we let f and g be the implementations and F and G be the mathematical functions these implementations calculate the values of, then it's Rice's theorem says that it's impossible to determine if f calculates G or g calculates F, as these are non-trivial properties of the implementations.

For further detail, see my answer to the previous question.

@Raynos: Then you can't determine equality. A proof using Rice's theorem is outlined above. — Sebastian Paaske Tørholm, Jan 31 '11 at 08:50

score 0 · Answer 3 · answered Aug 11 '11 at 10:58

Depending on your use-case, you might be able to do some assumptions about f & g . Maybe in your case, they apply under specific conditions what might make it solvable.

In other cases, the only thing what I might recommend is fuzzy testing , on Abstract Syntax Tree or other representation.

Function equality on restricted functions

3 Answers3

Linked