一般问题似乎难以解决。这是此问题的版本的显着限制。
如何确定函数的相等性?
假设我们有
函数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 =en.wikipedia/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.
更多推荐
两个函数是否相等?
发布评论