12

[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

function f() {
    // black box code.
}

function g() {
    // black box code.
}

We take a mathematical definition of a function. So

if for all x in domain, f(x) === g(x) then f === g

  • How do we handle domains?
  • How can we otherwise determine if f === g

Checks by source code is silly because 

function f(i) {
     return i % 2;
}

function g(i) {
     var returnVal = i % 2;
     return returnVal;
}

Are obvouisly equal. These are trivial examples but you can imagine more complex functions being equal but not source-equal.

You may assume that f and g have no side effects that we care about.

[Edit]

As @Pointy mentioned it's probably best to constrain the domain. Rather then having the equality function try and guess the domain, the user of the equality function should supply a domain.

It doesn't make sense to ask whether two functions are equal without defining their domain somewhere.

To simply the problem we can assume to domain is the set of all integers or a subset of that so we need a function:

function equal (f, g, domain) {

}

The structure of the domain is irrelevant and can be made to make the problem as easy as possible. You can also assume that f and g act nicely on the domain of integers and don't crash&burn.

You may assume that f and g halt!

Again @Pointy points out a good example of non-deterministic functions

What if we limit f & g to be deterministic.

Community
  • 1
  • 1
Raynos
  • 166,823
  • 56
  • 351
  • 396
  • 2
    Well, because JavaScript allows side-effects, it's even more complicated than just checking the return value. I guess you can constrain the problem that way if you want, but I don't understand the practical value of it. – Pointy Jan 30 '11 at 16:41
  • @Pointy I was hoping to model infinite sets as functions. Then manipulate theses sets and have some kind of equality check. In this case you may assume that there are no side-effects. – Raynos Jan 30 '11 at 16:43
  • Oh OK then. It's an interesting problem; one way to approach this is to see if you can come up with a proof that it's **not** possible. – Pointy Jan 30 '11 at 16:45
  • @Pointy I rather not prove that the code I'm writing can't work. I might need to do this in LISP instead of JavaScript. – Raynos Jan 30 '11 at 16:47
  • I didn't mean that proving it would be fun :-) It just seems like it might be an interesting way to think about the problem. Is the domain for the family of functions in any way constrained? – Pointy Jan 30 '11 at 16:49
  • @Pointy I might be able to constrain it. It doesn't make sense to do an equality check without specifying a domain. So yes a domain should be supplied. A simple domain would be all integers. – Raynos Jan 30 '11 at 16:51
  • I think in the general case, you would run into the halting problem: http://en.wikipedia.org/wiki/Halting_problem If you just take two arbitrary functions and although you might know the domain, you don't know whether the functions will halt for every input to compare the output. Or I'm making it too complicated :D – Felix Kling Jan 30 '11 at 16:53
  • @FelixKling you can assume `f` & `g` halt. – Raynos Jan 30 '11 at 16:57
  • @Pointy: Henry Gordon Rice already proved that it's not possible. Take a look at Rice's theorem. It's a pretty important theorem from computability theory. – Daniel Egeberg Jan 30 '11 at 17:41

5 Answers5

14

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.

Daniel Egeberg
  • 8,359
  • 31
  • 44
  • Does this still hold if the functions are deterministic? – Raynos Jan 30 '11 at 17:51
  • can you explain how Rice's theorem is relevant. – Raynos Jan 30 '11 at 18:14
  • 1
    @Raynos Assume we're checking for the following property of `f`: for each x it returns `g(x)`. As this property is non-trivial if you don't assume `g` having any certain properties, "there is no general and effective method" to check for function equality. – polkovnikov.ph Feb 10 '14 at 14:46
8

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.(source; page 4)

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 mn 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(n-k) 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.

Community
  • 1
  • 1
Sebastian Paaske Tørholm
  • 49,493
  • 11
  • 100
  • 118
  • @SebastianP if `f` and `g` halt is the Halting problem still relevant? – Raynos Jan 30 '11 at 16:58
  • Given that they halt, the Halting problem shouldn't be an issue. There still is the issue that given a large enough domain, I don't see how you could verify that they correspond on all values. I'll write up something, it's getting a bit long for a comment. – Sebastian Paaske Tørholm Jan 30 '11 at 17:02
  • @Sebastian would limiting the output to `boolean` help? – Raynos Jan 30 '11 at 17:19
  • @Raynos: Then you'd have 2^n functions. If you should limit anything, it's the input domain. The smaller the input domain, the easier it is to check. – Sebastian Paaske Tørholm Jan 30 '11 at 17:27
  • Don't try to outsmart the Halting problem. Limiting the output to booleans doesn 't matter at all: function 1: {Brute force search for counterexamples to the Goldbach Conjecture up to 10^10^10^10^10^10. Return found/not found} ; function 2: {return false}. – hugomg Feb 17 '11 at 00:50
  • The halting problem assumes infinities that don't exist in real systems. Virtually all modern computational systems involve finite states with finite memory, and although the number of possible state mappings can be astronomical, they are still finite. Therefore, a general halting algorithm is entirely possible for real systems, although it may be subject to irreducible complexity. The algorithm is simply to define a graph of all possible states and transitions; isolated paths halt, and paths touching loops do not halt. – Triynko Dec 17 '13 at 23:25
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:

function a(n) {
  var today = new Date();
  if (today.getFullYear() === 2012 && today.getMonth() === 1 && today.getDate() === 3)
    return 0;
  return n * n;
}

That function looks a whole lot like

function b(n) { return n * n; }

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

function c(n) { return 0; }

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 ...

Pointy
  • 405,095
  • 59
  • 585
  • 614
  • That's a stupid function! I see the issue though. What if we make the functions deterministic? – Raynos Jan 30 '11 at 16:59
  • @Raynos I tried but I couldn't think of a more clever example :-) – Pointy Jan 30 '11 at 17:00
  • is it worth reposting the question severely restricting the Domain, Co-Domain and various properties of functions `f` and `g` ? – Raynos Jan 30 '11 at 17:04
  • Well it may be - this is far beyond the limits of what I know about Category Theory for me to be of much help!! – Pointy Jan 30 '11 at 17:05
2

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.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
1

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

Jeff Ames
  • 2,044
  • 13
  • 18