CODEWITHSUNDEEP
language-agnosticfunctionequality
Raynos
Raynos

Reputation: 169383

Function equality on restricted functions

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.

Upvotes: 0

Views: 327

Answers (3)

Grzegorz Wierzowiecki
Grzegorz Wierzowiecki

Reputation: 10843

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.

Upvotes: 0

Sebastian Paaske Tørholm
Sebastian Paaske Tørholm

Reputation: 50858

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.

Upvotes: 2

Mark Byers
Mark Byers

Reputation: 838116

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.

Upvotes: 3

Related Questions