两个功能是否相同？

Question

[编辑]

一般的问题似乎难以解决.以下是此问题的严格限制版本.

---

如何确定函数的相等性？

我们可以说

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

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

我们采用函数的数学定义.所以

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

• 我们如何处理域名？
• 我们怎么能确定是否 f === g

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

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

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

显然是平等的.这些是微不足道的例子,但你可以想象更复杂的函数是相等的但不是源相等的.

您可能会认为f并且g没有我们关心的副作用.

---

[编辑]

正如@Pointy提到的那样,最好限制域名.而不是让相等函数尝试并猜测域,相等函数的用户应该提供域.

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

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

function equal (f, g, domain) {

}

域的结构是无关紧要的,可以使问题尽可能简单.您也可以假设f和g对整数域很好地行事,不死机和燃烧.

你可以假设f并g停止!

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

如果我们限制f并g确定性,那该怎么办？

Answer 1

根据莱斯的定理,这是不可能的:

在可计算性理论中,赖斯定理指出,对于部分函数的任何非平凡性质,没有通用和有效的方法来确定算法是否计算具有该属性的部分函数.

如果将函数的域限制为有限,那么您可以使用强力来验证是否fx:f(x)= g(x),但对于无限域,这是不可能的.

Answer 2

创建一种机制是不可能的,给定两个函数,总是可以确定它们是否总是返回相同的值.

这源于你试图解决的问题等同于停机问题.^{(来源 ;第4页)}

当然,您可以使用启发式方法来执行此操作,但总会出现无法确定的情况.

假设你将其缩小到停止有限域上的函数,那么快速确定仍然不是一件容易的事.如果我们假设输入位于{1,...,n}并且输出位于{1,...,m},则有m ^个可能的函数(对于每个输入,有n个可能的输出).如果你对k点进行采样,则将其缩小,并使它们的概率相等,但仍然有m ^(nk)个不同的函数.因此,您可以确定它们是否可能相当快,但要确定,您必须检查所有n个可能的输入值.

如果你想以另一种方式而不是通过采样来做,我相信你将不得不对函数的源代码进行某种静态分析,这几乎是微不足道的.

此外,如果域不是有限的,赖斯的定理会阻止这样的算法存在.