ما يذهب إلى إثبات اثنين من برامج معقدة تعادل?

Question

أقول أردت أن أثبت أن اثنين من البرامج ما يعادل (إما بدقة إذا كان ذلك ممكنا ، أو بشكل غير رسمي إن لم يكن).وبشكل أكثر تحديدا ، ويقول لدي شيء المعقدة نسبيا مثل ملقم HTTP تنفيذها في ج و واحد تنفيذها في عقدة.js/جافا سكريبت.ماذا يمكنني أن أفعل حيث يقول "هذان بشكل فعال نفسه"?ما هي الخيارات المتاحة ؟ ما هو الممكن ؟ ما هو غير ممكن ؟

لقد مر بعض الوقت منذ أن كنت قد بحثت في إثبات برنامج معادلة (أنا حاليا مرتبط هذا, ولكن لا أستطيع قراءتها بعد هاها, و يبدو أنها تركز على غاية برامج بسيطة مثل المساواة الشيكات أو الأساسية الحلقات ، بينما أنا أسأل عن القوي HTTP server).

أساسا (أتخيل) أريد أن أقول "اثنين من هذه البرامج في JS و ج تفعل الشيء نفسه".أن "تفعل الشيء نفسه"من الواضح غامضة ، ولكن في نفس الوقت هذا يعني شيئا محددا.أي يمكن ملاحظتها الختامية على أي نظام هو عموما نفس ، أو.لذا هو مثل دليل ، ولكن دون أن تكون مثالية برهان.انها جزئية دليل أو شيء من هذا.

وأود أن تكون قادرة على القول من برامج "هذان تطبيقات مساوية لجميع النوايا والمقاصد".ربما أود أن تبدأ من خلال توفير للقياس ضمانات أو ملاحظات حول أداء الإدخال/الإخراج السلوك ، ومن ثم كتابة بعض الاختبارات ، ...أنا لا أتذكر تماما ، بطريقة أو بأخرى الإدلاء ببيانات حول النظام.أم يجب أن يكون التفكير أن "أداء HTTP server في أي لغة هو اكسيوم".التي من شأنها تبسيط ذلك :) مجرد افتراض أنه يفعل نفس الشيء مثل واحد آخر.ولكن هذا الالتفاف تشعر به.

أتساءل ما هي الخيارات المتاحة لي هنا ؟ إلى أي مدى يمكن أن أغتنم هذه النظرية ؟ أنا لا أهتم كم من الوقت سوف يستغرق هذا التنفيذ أو تحديد ، إذا كان يستغرق سنوات ، ما يرام.أود فقط أن أعرف ما هو ممكن من حيث جعل البيان "اثنين من هذه البرامج في C و JS هي ما يعادل" أكثر صرامة و مسمر.ما هي التقنيات/نظريات/بحث-الاتجاهات يمكن أن أنظر في جعل ذلك ممكنا ؟

الآن أنا فقط على افتراض وهم متساوون ضمنا ، مما يسمح قانون بلدي استدعاء أي الدالة C أو JS وظيفة مع العلم أن ~التأثير الكلي~ هو نفسه (غامضة, أعرف, لا أعرف كيف يعلقون عليه).أود أن تطبيق بعض الرياضيات أو نموذج فحص أو برنامج محاكاة أو شيء من هذا لدرجة أنني يمكن أن تجعل من أكثر صلابة ، إذا أمكن :)

في الطرف الآخر من الطيف هو إثبات أن 3 > 2 تعادل في كل من C و JS.ما أنا من المفترض القيام به في هذه اللعبة بسيطة القضية ؟ جعل ذلك قليلا أكثر تعقيدا على انها وسيلة كامل HTTP server, نسخ سلسلة في ج يختلف جدا في جافا سكريبت, لكنه شيء بسيط نسبيا.أين يمكنني حتى تبدأ في إثبات هذه "العمليات" تعادل بين اللغات ؟ أو إذا لم "يثبت" ، ثم "الدولة" أنهم ما يعادلها ، مع بعض الدعم الأدلة أو شيئا لا أدري.

هنا ليس كثيرا, ولكن هذا المخطط هو ما أنا في الأساس تحاول أن تفعل:

على مستوى أوسع ، ويبدو أن مشكلة مشابهة لهذه....ويقول كنت ترغب في الحصول على ميدالية.أنا يمكن أن تذهب إما المتجر وشراء واحدة أو يمكنني 3D طباعة واحد.كل من "خوارزميات" (الذهاب إلى المتجر أو 3D printing) هي طريقة مختلفة عن بعضها البعض ، لكنها فعليا نفسه.لن تكون هناك طريقة مباشرة إلى الخطوة الحكمة لإثبات هذه هي المعادلة عمليا (من ما مخيلتي توفر) لكن واضح النهاية النتيجة هي نفسها.كيف (هنا) هذه الدولة مع الصرامة?

Answer 1

تحليل رسمي اليوم يتم عادة على حدة أو على مستوى الوحدة.للأسف أنا لست على بينة من مقياس مشترك والذي يسمح التنبؤ إذا كان تحليل رسمي لن يكون ممكنا.فقط هيكليا رموز بسيطة جدا يمكن أن تكون حللت حتى مع LOC أو cyclomatic تعقيدات يصل إلى مليون.

في حالتك هنا قانون أي من البرنامجين هو واضح أيضا مجمع كامل الرسمي التحليل:

• نموذج تدقيق سوف لا تعمل.
• كاملة (bi-) محاكاة لن تنجح أيضا.

لذا فإن أفضل حل عملي أعرفه نموذج اختبار.في حين أنه لا دليل لا يزال الرسمية أساليب يمكن استخدامها.فإنه في نهاية المطاف يلغي الكوارث الكتابة و الحفاظ على يدويا اختبار كتابي الحالات.

P. S.:

قائمة قصيرة من الخطوات التي يمكن القيام به في هذه الحالة:

• نموذج مجردة من البرنامجين يتم إنشاؤه.هذا هو التنفيذ الثالثة والتي سيتم حذف كل التفاصيل غير مهم.التجريد لديه ميزة أن هذا النموذج هو بسيط بما فيه الكفاية مرة أخرى رسميا تحليلها.نموذج يمكن تطبيقه في أي لغة تريد إذا كان نموذج محلل يحلل رمز بايت.
• الملخص نموذج يمكن اجتيازه و على سبيل المثالشرط التغطية وصلت في اختبار جناح.هذه الخطوة يتم استخدام نموذج يستند إلى أداة اختبار.
• وأخيرا اختبار هذه الحالات يتم اختبارها على اثنين من برامج يتم فحص إذا كانت مجردة نموذج محاكاة اثنين برنامج تطبيقات.
• هذه المحاكاة العلاقة هي بالطبع ليست دليلا على التكافؤ.
• التجريد هو نظيفة جدا مواصفات ما أخذ في الاعتبار في اختبارات ما حذفت.
• اثنين القائم على نموذج اختبار الأدوات التي يمكن أن يوصى بها:مايكروسوفت المواصفات إكسبلورر ، Conformiq مصمم

Answer 2

واحد يمكن كتابة كتاب كامل المساحة تقنيات تثبت البرنامج التكافؤ.هذا الجواب هو مجرد قصيرة جدا نقطة البداية:

نظريا, إذا كنت تفكر في البرامج آلة تورنج ، ثم يتم فقدان كل أمل -- إثبات أن اثنين TMs نفس اللغة (أي هم لغويا أي ما يعادل) هو غير مقرر (في الواقع, انها ليست في إعادة$\كأس$ الأساسية).

لا يزال من الناحية النظرية ، إذا كنت تفكر في البرامج الخاصة بك محدودة أجهزة الدولة ، بما في ذلك الدول الذاكرة كجزء من الجهاز ، ثم برنامج معادلة DFAs بسيط جدا (قابلة للحل في كوم) ، NFAs انها PSPACE كاملة.المشكلة مع هذا النهج هو أن الدولة المساحة تكون كبيرة (على سبيل المثال ، إذا كان لديك فقط 100 بت من الذاكرة ، دولتكم الفضاء على الأقل $2^{100}$ الدول) ، لذلك هذا غير معقول.

الآن بعد أن وضحنا النظرية الحدود ، هناك هيئة ضخمة من العمل في معالجة هذه المواضيع ، بما في ذلك طرق تحديد التنفيذية دلالات.

في الأساس, هذا هو مجال التحقق الرسمي, فقط بعض الكلمات الرئيسية التي يمكن الحصول على أنك بدأته:

• نموذج التحقق
• Bisimulation
• التجريد - الصقل
• نظرية Provers (على سبيل المثال ، Coq)

علما أنه في الممارسة العملية ، العديد من الشركات رسميا التحقق من التعليمات البرمجية الخاصة بهم.الأجهزة, هذا هو ممارسة شائعة ، وهي مرحلة هامة في التنمية.للحصول على البرنامج الضخم تعقيد يعني سوى قطع صغيرة من التعليمات البرمجية يتم الحصول ثبت رسميا ، لم بأكمله البرامج (ليس بعد على الأقل).