两个函数是否相等？

本文介绍了两个函数是否相等？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

如何确定函数的相等性？

假设我们有

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