限制功能上的功能相等

Question

我已經發布了一個關於功能equality的問題。它很快得出結論認爲，一般功能平等是一個非常難以解決的問題，可能在數學上是不可證實的。

我想存根一個功能

function equal(f, g, domain) { 

} 

f & g是一個參數停機功能。他們的論點是一個自然數。這些函數將返回一個布爾值。

如果沒有域名通過，那麼你可能會認爲域名默認爲全部自然數。

domain的結構對於equal功能來說是最方便的。

另一個重要的事實是f & g是確定性的。並將一致地返回f(n)相同的布爾值m。

你可以假設f和g總是返回只要他們的投入是domain

的問題中不亂扔由於錯誤任何異常或崩潰是語言無關的，問計的實現功能equal。我不確定是否適合這個地方。

f & g沒有副作用。而domain不一定是有限的。

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; 
} 

注意，這裏假設域是有限的。

如果該域不是有限的，Rice's theorem防止這樣的算法從現有：

如果我們讓f和g是實現和F和G是數學函數這些實現計算的值，那麼它的賴斯定理說，不可能確定f是否計算G或g計算F，因爲這些是實現的非平凡屬性。請參閱my answer to the previous question。

Answer 3

根據您的使用情況，您可能可以對f & g做一些假設。也許在你的情況下，它們在特定的條件下可以解決。

在其他情況下，我可能會推薦的唯一東西是模糊測試，抽象語法樹或其他表示。