受限函数上的函数相等

Question

我已经发布了一个关于函数相等的问题。它很快得出结论，一般函数相等是一个极其困难的问题，并且可能在数学上无法证明。

我想存根一个函数

function equal(f, g, domain) {

}

f & g 是带有一个参数的停止函数。他们的论证是一个自然数。这些函数将返回一个布尔值。

如果没有传递域，那么您可以假设域默认为所有自然数。

domain 的结构对于 equal 函数来说是最方便的。

另一个重要的事实是 f & g 是确定性的。并将始终为 f(n) 返回相同的布尔值 m。

您可以假设 f 和 g 始终返回，并且只要它们的输入位于 domain

这个问题与语言无关，并且要求实现 equal 函数。我不确定 SO 是否是合适的地方。

f & g没有副作用。并且域不必是有限的。

Answer 1

这仍然是不可能的。

您可以针对有限数量的输入测试这两个函数，并检查它们在这些输入上是否相等。如果它们对于任何输入都不相等，则这两个函数不相同。如果它们在您测试的每种情况下都相等，那么它们很可能是相同的函数，但您不能完全确定。

一般来说，除非域很小，否则测试每个可能的输入是不可行的。如果域是 32 位整数并且您的函数计算速度相当快，那么检查每个可能的输入可能是可行的。

Answer 2

我相信以下是无需对源代码进行静态分析即可完成的最佳操作：

function equal(f, g, domain) {
    var n;
    for (n in domain) {
        if (f(domain[n]) != g(domain[n])) return false;
    }
    return true;
}

请注意，这假设域是有限的。

如果域不是有限的，莱斯定理会阻止这样的算法存在：

如果我们让 f 和 g 为实现，F 和 G 是这些实现计算其值的数学函数，那么莱斯定理表明不可能确定 f 计算 G 还是 g 计算 F，因为这些是实现的非平凡属性。

有关更多详细信息，请参阅我对上一个问题的回答。

Answer 3

根据您的用例，您也许能够对 f & 做一些假设。 g .也许在你的情况下，它们在特定条件下应用可能使它可以解决。

在其他情况下，我唯一推荐的是在抽象语法树或其他表示上进行模糊测试。