Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 292
Raynos Avatar asked Jan 30 '11 16:01

Raynos


People also ask

Are two functions equivalent?

Section 7.2 Equality of Functions. Two functions are equal if they have the same domain and codomain and their values are the same for all elements of the domain.

What are equal functions?

Equal function is one in which both Domain and Range will be the same. Complete step by step solution: Let A and B be two sets. Now by function we mean a rule such that for ∀a∈Athere exists a unique b∈Bsuch that, f(a)=b.SO, the set A is called the Domain of fwile the set B is called the Range off.

Are two functions equal if their derivatives are equal?

Functions with equal derivatives. We can also use the MVT to conclude that if two functions have equal derivatives on an interval, then they differ by a constant. For if f/ = g/, then (f - g)/ = 0, therefore, by the preceding theorem, f - g is constant.

What makes the two function different?

The difference of two functions can be found by subtracting the two individual functions from each other. Follow these steps to effectively find the difference between two functions: Subtract the second function from the first, remembering to distribute the negative sign to each term.


1 Answers

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.

like image 198
Daniel Egeberg Avatar answered Oct 10 '22 04:10

Daniel Egeberg