2つの複雑なプログラムを証明するのは何が同等ですか？

Question

2つのプログラムが等価であることを証明したいと思っていた（可能であれば、 のどちらか、またはそうでない場合は非公式にのいずれか）。より具体的には、Cで実装されているHTTPサーバなど、比較的複雑なものがあると、Node.js / JavaScriptに実装されているとしています。 「これら2つは効果的に同じである」と言うという点で私は何ができるでしょうか？私のオプションは何ですか？可能なことは何ですか？不可能なものは何ですか？

私はプログラムの等価性を証明することを検討してから少し経ちました（私は現在このを読むことはまだ読めません、そしてそれは平等小切手や基本的なループのような非常に単純なプログラムに焦点を合わせているように見えますが、私 '堅牢なHTTPサーバについて尋ねる。

本質的に（私は想像しています）「JSとCのこれら2つのプログラムは同じことをしています」と言いたいです。 「は同じことをしています」は明らかに曖昧ですが、同時にそれは何か特有のことを意味します。どちらのシステムでも観察可能な結果は一般的に同じです。を与えるか、を撮影します。だからそれは証明のようなものですが、 Perfect 証明ではありません。それは部分的な証明か何かのようなものです。

私は私のプログラムについて言うことができるようになりたいです "これらの2つの実装はすべての目的と目的に同等です"。私はおそらく、パフォーマンスと入出力の振る舞いについて測定可能な保証または観察を提供することから始めて、そしていくつかのテストを書くこと、そして...私はかなり覚えていない、どういうわけかシステムについてのステートメントを作成します。あるいは、「どちらの言語で機能しているHTTPサーバーは Axiom 」であると考えているだけです。それはそれを単純化するでしょう:)それは互いに同じことをすると仮定します。しかし、それは気持ちいいです。

ここで私の選択肢は何ですか？理論的にこれを取ることができますか？私はそれが何年もかかると罰金がかかっているならば、私はこれがどのくらいの期間かかるかを心配していません。 「これら2つのプログラムのCとJSは同等のもの」というステートメントを作成するという点で可能なものを知りたいのですが、より厳密で釘付けされています。どのようなテクニック/理論/研究方向を調べることができますか？

今私はを仮定していると仮定して、それらは暗黙的に等しいと仮定して、私のコードがC関数またはJS関数を呼び出すことを可能にし、〜全体的な効果が同じであることを知っています（漠然とした、私は知っています、それを停止する方法がわからない）。可能であれば、数学やモデルの確認やプログラムシミュレーションまたはプログラムシミュレーション、または何かを適用したいと思います。）

スペクトルのもう一方の端には、3 > 2がCとJSの両方に等しいことが証明されています。私はこのシンプルなケースで何をすべきかさえしたことさえしましたか？フルHTTPサーバーへの方法でわずかに複雑になると、C内の文字列をコピーすることはJavaScriptと非常に異なりますが、比較的簡単なことです。 2つの言語間でそれらの「操作」と同等のものを証明し始めるのはどこにありますか。あるいは「証明」していない場合は、それらが同等であることを「状態」、いくつかのバックアップ証拠か何かで、私はDunno。

ここはあまりありませんが、この図です。基本的にやろうとしていることです。

より広いレベルでは、問題はこれに似ているようです....私はメダリオンを手に入れたいとします。私は店に行って1つ買うことができます、または私はそれを印刷することができます。 「アルゴリズム」（店舗、または3D印刷）の両方が互いに異なりますが、効果的に同じです。これらは、これらが等価 （私の想像力が提供するものから）と同等のものであることを証明するための簡単な方法はありませんが、目的の結果は同じです。どのようにして（ここでも）これを厳格なものと述べますか？

Answer 1

正式な分析今日は通常、モジュールまたは単位レベルで行われます。残念ながら、正式な分析が可能かどうかを予測することを可能にする一般的なメトリックを認識していません。構造的に非常に簡単なコードのみが、最大100万のLOCまたは環式の複雑さでも正式に分析することができます。

ここでは、2つのプログラムのいずれかのコードは完全な形式な分析には明らかに複雑すぎる：

• モデル検査は機能しません。
• 完全な（BI-）シミュレーションも機能しません。

だから私が知っている最高の実用的な解決策は、モデルベースのテストです。それは証明ではないが、依然として正式な方法を使用することができる。それは最終的に執筆災害を排除し、手動で書かれたテストケースを維持します。

p.S.：

この場合に行うことができるステップの短いリスト：

• 2つのプログラムの抽象モデルが作成されます。これはすべての重要な詳細を省略する3番目の実装です。抽象化は、このモデルが再び正式に分析されるのに十分単純であるという利点を有する。モデルアナライザがバイトコードを分析するかどうかのような任意の言語で実装できます。
• 抽象モデルは通過することができます。テストスイートでは、条件適用範囲に達します。このステップは、モデルベースのテストツールを使用して行われます。
• 最後にこれらのテストケースは2つのプログラムでテストされ、抽象モデルが2つのプログラム実装をシミュレートできるかどうかがチェックされます。
• このシミュレーション関係はもちろん等価性の証明ではありません。
• 抽象化は、私たちのテストで考慮されたものと省略されたものが何であるか、非常にきれいな仕様です。
• 推奨することができる2つのモデルベースのテストツール：Microsoft Spec Explorer、Conformiq Designer

Answer 2

プログラム等価性を証明するための書籍測量技術全体を書くことができます。この答えは非常に短い出発点のようなものです：

理論的には、あなたがチューリングマシンとしてあなたのプログラムについて考えるならば、すべての希望が失われます - 2つのTMSが同じ言語を持っていることを証明します（つまり、それらは意味的に同等のものです）ことはできません（実際には、それは再 $ \ cup $ コア）にはありません。

まだ理論的には、メモリの状態をマシンの一部として含めることで、PSFAのためのプログラム等価性（NLでは解決可能）、およびNFASのためのプログラム等価性が非常に単純であり、それはPSPACEの完全なものである。 。このアプローチの問題は、状態空間が大きくなることです（たとえば、100ビットのメモリしかない場合は、少なくともSPAN CLASS="Math-Container"> $ 2 ^ {100} $ 州）、これは不合理です。

理論的境界をクリアしたので、運用上の意味論を定義する方法を含む、これらのトピックに対処する巨大な作業機関があります。

基本的には、これは正式な検証、および取得できるキーワードだけです。あなたは始めました：

• モデルチェック
• ビシミュレーション
• 抽象化 - 洗練
• 定理証明者（例えば、COQ）

実際には、多くの企業が規定を正式に検証していることに注意してください。ハードウェアの場合、これは一般的な慣習であり、開発の重要な段階です。ソフトウェアのために、巨大な複雑さは、コードのわずかなビットだけが正式に証明されていることを意味し、決して全体のプログラム（まだ、少なくとも）ではなく。