两个函数是否相等？ [英] Are two functions equal?

问题描述

一般问题似乎难以解决。这是此问题的版本的显着限制。

---

如何确定函数的相等性？

假设我们有

 函数f（）{
 //黑盒代码。 
} 
 
函数g（）{
 //黑盒代码。 
} 
  

我们对函数进行数学定义。

如果对于域中的所有x，f（x）=== g（x），则f === g

• 我们如何处理域？


• 我们如何判断 f === g

按源代码检查是愚蠢的，因为

  function f（i）{
 return i％2; 
} 
 
函数g（i）{
 var returnVal = i％2; 
 return returnVal; 
} 
  

这些都是微不足道的例子，但你可以想象更复杂的函数是平等的，但不是源平等。

你可以假设 f 和 g 没有我们关心的副作用。

---

正如@Pointy所说，最好限制域。而不是让等式函数尝试和猜测域，等式函数的用户应该提供一个域。

在没有定义域名的情况下询问两个函数是否相等是没有意义的。

简单的我们可以假设域的问题是所有整数的集合或其子集，所以我们需要一个函数：

  function equal（f，g，domain）{
 
} 
  

该领域是不相关的，可以使问题尽可能容易。您还可以假设 f 和 g 在整数域上运行良好，不会崩溃& burn。 / p>

您可以假设 f 和 g halt！ / p>

再次@Pointy指出非确定性函数的一个很好的例子

如果我们限制 f & g 是确定性的。

解决方案

href =http://en.wikipedia.org/wiki/Rice%27s_theorem>赖斯定理：

可计算性理论，Rice的
定理说明，对于部分
函数的任何
非平凡属性，没有一般和
有效方法来决定
算法使用该属性计算部分函数
。

如果将函数的范围限制为有限，使用暴力强制来验证∀x：f（x）= g（x）是否可行，但这是不可能的。

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

解决方案

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.

这篇关于两个函数是否相等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！