制限機能に関する機能の一致

Question

機能equalityについての質問を既に投稿しました。それはすぐに一般的な関数の平等は非常に難しい問題であり、数学的に分かりやすいと結論づけました。私は機能

function equal(f, g, domain) { 

} 

f & gをスタブしたい

は一つの引数を取る停止機能です。彼らの議論は自然数である。これらの関数はブール値を返します。

ドメインが渡されない場合、ドメインはすべての自然数にデフォルト設定されているとみなされます。

domainの構造は、equal機能にとって最も便利なものです。

もう1つの重要な事実は、f & gが確定的であることです。 f(n)に対して同じブール値mを一貫して返します。

あなたがfとgはいつも戻っている限り、その入力がdomain

質問内にあるとしてエラーにより任意の例外やクラッシュを投げていないことを仮定してもよいが、言語に依存しないとの実施を求めていますequal機能です。私はそれがもうこれ以上正しい場所であるかどうかはわかりません。

f & gは、副作用がない。 domainは有限である必要はありません。

Answer 1

これはまだできません。

いくつかの有限数の入力に対して両方の関数をテストし、それらの入力で等価であることを確認することができます。それらがいずれの入力に対しても等しくない場合、2つの関数は同一ではない。あなたがテストしたすべてのケースで同等であれば、それらが同じ機能であるという合理的な機会がありますが、あなたは完全に確信することはできません。

一般に、ドメインが小さい場合を除き、可能なすべての入力をテストすることは実行不可能です。ドメインが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は、これらの実装は、それがライスのだ、の値を計算する数学的な関数である場合

：ドメインが有限でない場合

は、Rice's theoremは、既存のようなアルゴリズムを防止します定理は、fがGを計算するかgがFを計算するかを決定することは不可能であると述べているが、これは実装の重要な特性ではないからである。

詳細については、my answer to the previous questionを参照してください。

Answer 3

あなたのユースケースによっては、f & gに関するいくつかの前提を行うことができます。たぶん、あなたのケースでは、それは特定の条件の下でそれを解決するかもしれないものを適用します。

他のケースでは、唯一推奨するものは、ファジーテスト、抽象構文木または他の表現です。