لماذا لا يمكن إثبات البرامج؟
https://stackoverflow.com/questions/476959
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لماذا لا يمكن إثبات برنامج كمبيوتر مثلما يمكن إثبات العبارة الرياضية؟يتم بناء الدليل الرياضي على براهين أخرى، والتي يتم بناؤها من المزيد من البراهين وصولاً إلى البديهيات - تلك الحقائق التي نعتبرها حقائق بديهية.
لا يبدو أن برامج الكمبيوتر لديها مثل هذا الهيكل.إذا كنت تكتب برنامج كمبيوتر، فكيف يمكنك أن تأخذ الأعمال السابقة المثبتة وتستخدمها لإظهار حقيقة برنامجك؟لا يمكنك ذلك لأنه لا يوجد شيء.علاوة على ذلك، ما هي بديهيات البرمجة؟الحقائق الذرية جدا في هذا المجال؟
ليس لدي إجابات جيدة على ما ورد أعلاه.لكن يبدو أنه لا يمكن إثبات البرمجيات لأنها فن وليست علمًا.كيف تثبت بيكاسو؟
المحلول
وبرامج .
التحقق الرسمي البرامج هو ضخمة منطقة البحث. (انظر، على سبيل المثال، المجموعة في جامعة كارنيجي ميلون ).
وقد تم التحققوالعديد من البرامج المعقدة؛ على سبيل المثال، انظر هذا نواة مكتوب في هاسكل .
نصائح أخرى
والبرامج <م> لا يمكن على الاطلاق أن ثبت أن تكون صحيحة. برامج رديء من الصعب إثباته. للقيام بذلك حتى بشكل معقول، لديك لتطوير البرنامج وجنبا إلى جنب واقية.
ولا يمكنك <م> أتمتة الدليل بسبب مشكلة وقف. يمكنك، ومع ذلك، تثبت بعد ظروف وشروط مسبقة من أي بيان التعسفي، أو سلسلة من البيانات يدويا.
ويجب أن تقرأ والانضباط البرمجة .
وبعد ذلك، يجب قراءة جريس " علم البرمجة .
وبعد ذلك عليك أن تعرف كيفية إثبات برامج صحيحة.
ومجرد تعليق صغير لأولئك الذين تربوا عدم اكتمال - أنها ليست الحال بالنسبة ل<م> جميع أنظمة البديهي، فقط <م> قوية بما فيه الكفاية منها
.وبعبارة أخرى، أثبت غودل أن النظام البديهي قوية بما يكفي لوصف نفسها ستكون بالضرورة غير مكتملة. هذا لا يعني أنه لن تكون مجدية ومع ذلك، وكما فعل آخرون ربطت ل، بذلت محاولات مختلفة في بروفات البرنامج.
والمشكلة المزدوجة (كتابة برامج للتحقق البراهين) هي أيضا مثيرة للاهتمام للغاية.
يمكنك في الواقع كتابة برامج صحيحة يمكن إثباتها.قامت شركة مايكروسوفت، على سبيل المثال، بإنشاء امتداد للغة C# يسمى المواصفات# والذي يتضمن مُثبت نظرية آلي.بالنسبة لجافا، هناك إيسك/java.أنا متأكد من أن هناك العديد من الأمثلة هناك.
(يحرر:يبدو أن المواصفات # لم تعد قيد التطوير، ولكن ستصبح أدوات العقد جزءًا من .NET 4.0)
أرى بعض الملصقات تلوح باليد حول مشكلة التوقف أو نظريات عدم الاكتمال والتي من المفترض أن تمنع التحقق التلقائي من البرامج.وهذا بالطبع ليس صحيحا؛هذه القضايا تخبرنا فقط أنه كذلك من الممكن كتابة برامج لا يمكن إثبات صحتها أو خطأها.وهذا لا يمنعنا من بناء البرامج التي نكون صحيح يمكن إثباته.
تظهر مشكلة التوقف فقط أن هناك برامج لا يمكن التحقق منها.السؤال الأكثر إثارة للاهتمام والأكثر عملية هو ما هي فئة البرامج يستطيع يتم التحقق منها رسميًا.ربما يمكن (نظريًا) التحقق من كل برنامج يهتم به أي شخص. ومن الناحية العملية، حتى الآن، تم إثبات صحة البرامج الصغيرة جدًا فقط.
إذا كنت مهتمًا حقًا بالموضوع، فاسمح لي أولاً أن أوصيك بـ "علم البرمجة" لديفيد جريس، وهو عمل تمهيدي كلاسيكي حول هذا الموضوع.
في الواقع من الممكن إثبات صحة البرامج إلى حد ما.يمكنك كتابة الشروط المسبقة والشروط اللاحقة ثم إثبات أنه في حالة استيفاء الحالة للشروط المسبقة، فإن الحالة الناتجة بعد التنفيذ ستفي بالشروط اللاحقة.
لكن الأمر الأكثر صعوبة هو الحلقات.بالنسبة لهذه، تحتاج بالإضافة إلى ذلك إلى العثور على حلقة ثابتة ولإظهار الإنهاء الصحيح، تحتاج إلى العثور على دالة الحد الأعلى على أقصى عدد ممكن من التكرارات المتبقية بعد كل حلقة.يجب أيضًا أن تكون قادرًا على إظهار أن هذا يتناقص بمقدار مرة واحدة على الأقل بعد كل تكرار خلال الحلقة.
بمجرد حصولك على كل هذا لبرنامج ما، يصبح الدليل ميكانيكيًا.لكن لسوء الحظ، لا توجد طريقة لاشتقاق الدوال الثابتة والمرتبطة تلقائيًا للحلقات.يكفي الحدس البشري في الحالات التافهة ذات الحلقات الصغيرة، لكن من الناحية الواقعية، سرعان ما تصبح البرامج المعقدة مستعصية على الحل.
أولا، لماذا أنت تقول "برامج فإنه لا يثبت"؟
وماذا تقصد ب "البرامج" على أية حال؟
إذا ببرامج كنت يعني خوارزميات لا تعلمون في كروسكال؟ ديكسترا؟ MST؟ وزم؟ بحث ثنائي؟ تصنيف دمجي؟ موانئ دبي؟ كل هذه الأشياء لها النماذج الرياضية التي تصف تصرفاتهم.
وصفها. الرياضيات لا يفسر لماذا من الأشياء ببساطة يرسم صورة لكيفية القيام بذلك. لا أستطيع أن أثبت لك أن الشمس سوف ترتفع غدا على الشرق ولكن يمكنني أن تظهر البيانات حيث تم القيام هذا الشيء في الماضي.
وقال لك: "إذا كنت كتابة برنامج كمبيوتر، كيف يتم ذلك يمكنك أن تأخذ أعمال ثبت السابقة واستخدامها لإظهار الحقيقة من برنامجك؟ لا يمكن لأن أيا جود"
وانتظر؟ لا يمكنك؟ http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis
وأنا لا يمكن أن تظهر لك "الحقيقة" I برنامج بقدر ما لا يمكن أن تظهر لك "الحقيقة" على اللغة. كلاهما تمثيل فهمنا التجريبية من العالم. ليس على "الحقيقة". وضع كل رطانة جانبا I يمكن أن تثبت لك رياضيا أن algorith تصنيف دمجي وفرز العناصر في قائمة مع O (nlogn) الأداء، أن ديكسترا سوف تجد أقصر مسار على رسم بياني المرجح، أو أن خوارزمية إقليدس سوف تجد لك أعظم القاسم المشترك بين رقمين. "الحقيقة في برنامجي" في هذه الحالة الأخيرة ربما أنني سوف تجد لك القاسم المشترك الأكبر بين رقمين، لا تظن؟
ومع معادلة تكرار أستطيع أن تحدد لك كيف يعمل برنامج فيبوناتشي الخاص بك.
والآن، هو برمجة الكمبيوتر فنا؟ أنا متأكد أعتقد أنه هو. بقدر الرياضيات.
وأنا لا تأتي من خلفية رياضية، فاغفر جهلي، ولكن ماذا "يثبت برنامج" يعني؟ ماذا يثبت؟ صحة؟ صحة هي المواصفات التي البرنامج يجب التحقق من أن تكون "صحيحة". ولكن هذه المواصفات هو قرر من قبل الإنسان، وكيف يمكنك التحقق من أن هذه المواصفات صحيحة؟
لرأيي، هناك أخطاء في البرنامج لأن البشر لديهم صعوبات التعبير عما يريدون حقا. http://www.processdevelopers.com/images/PM_Build_Swing.gif
وهكذا ما الذي يثبت؟ الخلل الناجم عن عدم الاهتمام؟
وعلاوة على ذلك، ما هي بديهيات البرمجة؟ الحقائق الذرية جدا من هذا المجال؟
ولقد TA'ed والبرمجة بالطبع يسمى عقد بناء (بالطبع زيارة: HTTP: // www.daimi.au.dk/KBP2/ ). هنا ما يمكن استقراء من الدورة (وغيرها من الدورات لقد اتخذت)
وعليك أن رسميا (رياضيا) تحديد دلالات لغتك. دعونا نفكر في لغة برمجة بسيطة. واحد يحتوي على المتغيرات العالمية فقط، [إينتس]، صفائف كثافة العمليات، والحساب، إذا، ثم، آخر، في حين، وتعيين وتفعل شيئا [ربما يمكنك استخدام مجموعة فرعية من أي لغة السائدة بأنها "تنفيذ" من هذه].
وهناك دولة التنفيذ سيكون على قائمة من أزواج (اسم متغير، قيمة متغير). قراءة "{Q1} {S1 Q2}" ب "بيان تنفيذ S1 يأخذك من Q1 دولة التنفيذ لQ2 الدولة".
وعندئذ "if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}" احد بديهية. وهذا هو، إذا S1 بيان يأخذك من Q1 الدولة لQ2، وبيان S2 يأخذك من Q2 في Q3، ثم "S1، S2". (S1 تليها S2) يأخذك من Q1 الدولة لQ3 الدولة
وسيتم "if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}" بديهية أخرى.
والآن، وقليلا من الصقل: لQN في {} الصورة سيكون في الواقع التصريحات حول الدول، لا تنص على أنفسهم
. لنفترض أن M (من، A1، A2) هو بيان الذي يقوم دمج اثنين من صفائف فرزها وتخزن النتيجة في الخارج، وأن جميع الكلمات يمكنني استخدامها في المثال التالي وأعرب رسميا (رياضيا). ثم "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}" والمطالبة ثا M تطبق خوارزمية الدمج بشكل صحيح.
ويمكن للمرء أن محاولة إثبات ذلك عن طريق استخدام بديهيات أعلاه (ربما تكون هناك حاجة لعدد قليل من الآخرين. أنت من المحتمل أن تحتاج حلقة واحدة).
وآمل أن يكون هذا يوضح قليلا ما تثبت برامج صحيحة قد تبدو. والثقة لي: أنه يأخذ <م> الكثير العمل، حتى بالنسبة للخوارزميات التي تبدو بسيطة، ليثبت لهم صحيح. وأنا أعلم، وأنا أقرأ الكثير من المحاولات، -)
[إذا كنت تقرأ هذا: <م> الخاص بك كان يدا في الدقة، كل تلك الأخرى التي تسبب لي الصداع، -)]
بالطبع يمكنهم ذلك، كما نشر آخرون.
يعد إثبات صحة روتين فرعي صغير جدًا تمرينًا جيدًا يجب على كل طالب جامعي في برنامج درجة متعلق بالبرمجة أن يكون عليه مطلوب لكى يفعل.يمنحك نظرة ثاقبة للتفكير في كيفية جعل التعليمات البرمجية الخاصة بك واضحة وقابلة للمراجعة والصيانة بسهولة.
ومع ذلك، في العالم الحقيقي هو ذو استخدام عملي محدود.
أولاً، مثلما تحتوي البرامج على أخطاء، كذلك تحتوي البراهين الرياضية.كيف يمكن إثبات أن الدليل الرياضي صحيح حقًا ولا يحتوي على أي أخطاء؟لا يمكنك.وعلى سبيل المثال، تم اكتشاف أخطاء في أي عدد من البراهين الرياضية المنشورة، أحيانًا بعد سنوات.
ثانياً، لا يمكنك إثبات صحة برنامج ما دون أن يكون لديك تعريف مسبق لا لبس فيه لما يفترض أن يفعله البرنامج.لكن أي تعريف لا لبس فيه لما يفترض أن يفعله البرنامج هو برنامج.(على الرغم من أنه قد يكون برنامجًا بنوع من لغة المواصفات التي لا يوجد لديك مترجم لها.) لذلك، قبل أن تتمكن من إثبات صحة البرنامج، يجب أن يكون لديك أولاً برنامج آخر مكافئ ومعروف مسبقًا ليكون صحيحا.لذا فإن QED هو الأمر برمته.
أوصي بتتبع الكلاسيكية "لا رصاصة فضية"مقالة كتبها بروكس.
وثيريس الكثير من الأبحاث في هذا المجال .. كما قال آخرون، ويبني داخل لغة البرنامج هي معقدة، وهذا يحصل فقط أسوأ من ذلك، عند محاولة التحقق من صحة أو إثبات لأي مدخلات معينة.
ومع ذلك، العديد من اللغات تسمح للمواصفات، على ما المدخلات مقبولة (شروط مسبقة)، وأيضا السماح لتحديد النتيجة النهائية (الظروف آخر).
وتشملوهذه اللغات: B، B الحدث، آدا، فورتران
.وبطبيعة الحال، هناك العديد من الأدوات التي تم تصميمها لمساعدتنا في إثبات خصائص معينة حول البرامج. على سبيل المثال، لإثبات حرية الجمود، يمكن للمرء أن ازمة البرنامج من خلال SPIN.
وهناك أيضا العديد من الأدوات الى ان هناك مساعدة لنا أيضا الكشف عن أخطاء المنطق. ويمكن القيام بذلك عن طريق تحليل ثابت (goanna، satabs) أو التنفيذ الفعلي للقانون (valgrind جنو؟).
ولكن، ليست هناك أداة واحدة مما يتيح حقا واحدة لإثبات برنامج كامل، من البداية (مواصفات) وتنفيذ ونشر. طريقة B يقترب، ولكن التحقق من تنفيذها جدا ضعيف جدا. (فإنه يفترض أن البشر هم infalible في ترجمة speicficaiton إلى implmentation).
وكملاحظة جانبية، عند استخدام الأسلوب B، فسوف تجد نفسك في كثير من الأحيان بناء البراهين المعقدة من البديهيات أصغر. (ونفس الشيء ينطبق على غيرها من البروفر نظرية exhasustive).
وما في وسعهم. قضيت الكثير والكثير من ساعات كطالبة جامعية القيام البراهين صحة البرنامج.
والسبب انها ليست عملية على المستوى الكلي هو أن كتابة دليل على وجود برنامج يميل إلى أن يكون أصعب بكثير من كتابة البرنامج. أيضا، المبرمجين اليوم تميل إلى بناء أنظمة، وليس كتابة وظائف أو البرامج.
وعلى النطاق الصغير، وأحيانا تفعل ذلك عقليا لوظائف الفردية، وتميل إلى تنظيم قانون بلدي لجعلها سهلة للتحقق.
وهناك مقال شهير حول برنامج مكوك الفضاء. يفعلون البراهين، أو شيء ما يعادلها. انها مكلفة وتستغرق وقتا طويلا للغاية. قد يكون هذا المستوى من التحقق من الضروري بالنسبة لهم، ولكن عن أي نوع من المستهلك أو شركة البرمجيات التجارية، مع التقنيات الحالية، وستحصل على الغداء يؤكل من قبل منافس الذي يسلم حلا 99.9٪ بواقع 1٪ من التكلفة. لا أحد سوف تدفع 5000 $ لمكتب MS هذا هامشي أكثر استقرارا.
إذا كنت تبحث عن الثقة، فإن البديل عن إثبات البرامج هو اختبارها.هذا أسهل للفهم ويمكن أن يكون آليًا.كما يسمح أيضًا بفئة البرامج التي لا يمكن إثباتها رياضيًا، كما هو موضح أعلاه.
قبل كل شيء، لا يوجد دليل بديل عن اجتياز اختبارات القبول:*
فقط لأن البرنامج يفعل ما يقول أنه يفعله، لا يعني أنه يفعل ما يريده المستخدم أن يفعله.
إلا إذا يمكنك إثبات أن ما تقوله إنها تفعله هو ما يقول المستخدم إنه يريده.
- والذي عليك بعد ذلك إثباته هو ما يفعلونه اريد حقا, ، لأنهم، كونهم مستخدمين، فمن المؤكد أنهم لا يعرفون ما يريدون.إلخ.اختزال إلى حد العبث.
*ناهيك عن اختبارات الوحدة والتغطية والوظيفة والتكامل وجميع أنواع الاختبارات الأخرى.
نأمل أن يساعدك هذا في طريقك.
وليس فقط يمكن أن تثبت البرامج، يمكنك أن تدع جهاز الكمبيوتر الخاص بك بناء البرامج من البراهين. انظر كوك . لذلك لم يكن لدينا حتى ما يدعو للقلق بشأن احتمال بعد أن ارتكب خطأ في التطبيق الخاص بك.
نظريات غودل في على الرغم ... ماذا سيكون نقطة ؟ ما التبسيط "الحقائق" تريد أن تثبت؟ ماذا كنت تريد أن تجنيها من تلك الحقائق؟ بينما أنا قد أكل هذه الكلمات ... حيث التطبيق العملي؟
ويمكن أن يثبت البرامج. انها هادئة السهل إذا كنت اكتبها في اللغة مثل على سبيل المثال ستاندرد ML نيو جيرسي (SML / NJ).
وبيانكم واسع حتى انها لاصطياد الكثير من الأسماك.
وخلاصة القول هو: هل يستطيع بالتأكيد أن يثبت بعض البرامج صحيحة. كل البرامج يمكن أن <م> لا يثبت الصحيح.
إليك مثالا تافها التي، واعتبارها لكم، هو بالضبط نفس النوع من دليل على أن دمرت نظرية نكسة في اليوم: جعل البرنامج الذي يمكن تحديد ما إذا كان في حد ذاته هو الصحيح، وإذا وجد أنه هو صحيح، وإعطاء إجابة غير صحيحة.
وهذه هي نظرية غودل واضح وبسيط.
ولكن هذا ليس عسيرا للغاية، لأننا يمكن أن تثبت العديد من البرامج.
لنفترض لغة وظيفية بحتة (أي هاسكل).يمكن أخذ الآثار الجانبية في الاعتبار بشكل واضح تمامًا في مثل هذه اللغات.
يتطلب إثبات أن البرنامج ينتج النتيجة الصحيحة تحديد ما يلي:
- المراسلات بين أنواع البيانات والمجموعات الرياضية
- المراسلات بين دوال هاسكل والدوال الرياضية
- مجموعة من البديهيات تحدد الوظائف المسموح لك ببنائها من الآخرين، والبناء المقابل لها على الجانب الرياضي.
تسمى هذه المجموعة من المواصفات دلالات الدلالة.أنها تسمح لك بإثبات السبب وراء البرامج التي تستخدم الرياضيات.
والخبر السار هو أن "بنية البرامج" (النقطة 3 أعلاه) و"بنية المجموعات الرياضية" متشابهتان تمامًا (الكلمة الطنانة هي توبوس, ، أو فئة ديكارتية مغلقة)، لذا 1/ سيتم بسهولة نقل البراهين التي تقوم بها على الجانب الرياضي إلى إنشاءات برمجية 2/ من السهل إثبات أن البرامج التي تكتبها صحيحة رياضيًا.
وتقرأ على مشكلة وقف (وهي عبارة عن صعوبة إثبات شيء ما بسيط ما إذا كان يكمل البرنامج أم لا). في الأساس يرتبط المشكلة إلى نظرية عدم اكتمال جوديل.
يمكن إثبات بعض أجزاء البرامج.على سبيل المثال، مترجم C# الذي يتحقق بشكل ثابت ويضمن سلامة النوع، في حالة نجاح التجميع.لكنني أظن أن جوهر سؤالك هو إثبات أن البرنامج يعمل بشكل صحيح.يمكن إثبات صحة العديد من الخوارزميات (ولا أجرؤ على قول معظمها)، لكن ربما لا يمكن إثبات صحة البرنامج بأكمله بشكل ثابت للأسباب التالية:
- يتطلب التحقق اجتياز جميع الفروع الممكنة (الاستدعاءات، وifs، والمقاطعات)، والتي تحتوي في كود البرنامج المتقدم على تعقيد زمني فائق المكعب (وبالتالي لن تكتمل أبدًا خلال فترة زمنية معقولة).
- بعض تقنيات البرمجة، سواء من خلال صنع المكونات أو استخدام الانعكاس، تجعل من المستحيل التنبؤ بشكل ثابت بتنفيذ التعليمات البرمجية (أي تنفيذ التعليمات البرمجية).أنت لا تعرف كيف سيستخدم مبرمج آخر مكتبتك، ويواجه المترجم صعوبة في التنبؤ بكيفية استدعاء الانعكاس في المستهلك للوظيفة.
وتلك مجرد بعض ...
إذا كان للبرنامج هدف محدد جيدًا وافتراضات أولية (تجاهل غودل...) فيمكن إثباته.أوجد جميع الأعداد الأولية x لـ 6<=x<=10، إجابتك هي 7 ويمكن إثبات ذلك.كتبت أ البرنامج الذي يلعب NIM (أول برنامج بايثون كتبته على الإطلاق) ومن الناحية النظرية يفوز الكمبيوتر دائمًا بعد أن تقع اللعبة في حالة يمكن للكمبيوتر أن يفوز فيها.لم أتمكن من إثبات صحة ذلك، ولكنه صحيح (رياضيًا عن طريق إثبات مجموع ثنائي رقمي) أعتقد ما لم أرتكب خطأً في الكود.هل ارتكبت خطأ، لا على محمل الجد، هل يمكن لأحد أن يقول لي إذا كان هذا البرنامج قابلاً للهزيمة؟
هناك بعض النظريات الرياضية التي تم "إثباتها" باستخدام كود الكمبيوتر مثل نظرية الألوان الأربعة.لكن هناك اعتراضات، لأنه كما قلت هل يمكنك إثبات البرنامج؟
علاوة على ذلك، ما هي بديهيات البرمجة؟الحقائق الذرية جدا في هذا المجال؟
هل رموز التشغيل "الحقائق الذرية"؟على سبيل المثال عند رؤية...
mov ax,1
...ألا يمكن للمبرمج أن يؤكد كأمر بديهي أنه، باستثناء مشكلة في الأجهزة، بعد تنفيذ هذا البيان، وحدة المعالجة المركزية ax سيحتوي التسجيل الآن 1?
إذا كنت تكتب برنامج كمبيوتر، فكيف يمكنك أن تأخذ الأعمال السابقة المثبتة وتستخدمها لإظهار حقيقة برنامجك؟
قد يكون "العمل السابق" هو بيئة وقت التشغيل التي يعمل فيها البرنامج الجديد.
ويمكن إثبات البرنامج الجديد:وبصرف النظر عن الأدلة الرسمية، يمكن إثبات ذلك "بالتفتيش" وبأشكال مختلفة من "الاختبار" (بما في ذلك "اختبار القبول").
كيف تثبت بيكاسو؟
إذا كانت البرمجيات أشبه بالتصميم الصناعي أو الهندسة أكثر من كونها فنًا، فقد يكون السؤال الأفضل هو "كيف يمكن إثبات وجود جسر أو طائرة؟"
وتثبت برنامج الصحيح يمكن أن يتم إلا بالنسبة لمواصفات البرنامج؛ فمن الممكن ولكنها باهظة الثمن / تستغرق وقتا طويلا
وبعض النظم حالة تنتج برامج أكثر قابلية لالبراهين من غيرها - ولكن مرة أخرى، وهذا يعتمد على دلالات الرسمية للمواصفات ...
و... وهكذا كيف يمكنك إثبات مواصفات الصحيح؟ حق! مع مزيد من المواصفات!
قرأت قليلا عن هذا، ولكن هناك مشكلتان.
أولاً، لا يمكنك إثبات شيء مجرد يسمى الصحة.يمكنك، إذا تم إعداد الأمور بشكل صحيح، إثبات أن النظامين الرسميين متكافئان.يمكنك إثبات أن البرنامج ينفذ مجموعة من المواصفات، ومن الأسهل القيام بذلك عن طريق إنشاء الدليل والبرنامج بشكل متوازٍ تقريبًا.ولذلك، يجب أن تكون المواصفات مفصلة بما فيه الكفاية لتوفير ما يمكن إثباته، و وبالتالي فإن المواصفات هي برنامج فعال.تصبح مشكلة كتابة برنامج لتحقيق غرض ما مشكلة كتابة مواصفات تفصيلية رسمية لبرنامج لتلبية غرض ما، وهذا ليس بالضرورة خطوة إلى الأمام.
ثانيا، البرامج معقدة.وكذلك أدلة الصواب.إذا كان بإمكانك ارتكاب خطأ أثناء كتابة برنامج ما، فمن المؤكد أنه يمكنك إثبات ذلك.أخبرني ديكسترا وجريس، بشكل أساسي، أنه إذا كنت عالم رياضيات مثاليًا، فيمكنني أن أصبح مبرمجًا جيدًا.القيمة هنا هي أن الإثبات والبرمجة هما عمليتان فكريتان مختلفتان إلى حد ما، وعلى الأقل في تجربتي، أرتكب أنواعًا مختلفة من الأخطاء.
في تجربتي، إثبات البرامج ليس عديم الفائدة.عندما أحاول القيام بشيء يمكنني وصفه رسميًا، فإن إثبات صحة التنفيذ يزيل الكثير من الأخطاء التي يصعب العثور عليها، ويترك في المقام الأول الأخطاء الغبية، والتي يمكنني اكتشافها بسهولة في الاختبار.في المشروع الذي يجب أن ينتج تعليمات برمجية خالية من الأخطاء، يمكن أن يكون مساعدًا مفيدًا.إنها ليست مناسبة لكل التطبيقات، وهي بالتأكيد ليست حلاً سحريًا.
وكما أشار آخرون، يمكن بالفعل أن يثبت (بعض) البرامج.
ومشكلة واحدة في ممارسة ذلك هو أن تحتاج أولا <م> شيء (أي افتراض أو نظرية) التي تريد أن تثبت. وذلك لإثبات شيء عن برنامج تحتاج أولا إلى وصف رسمي لما يجب أن تفعله (مثل قبل وبعد الشروط).
وبعبارة أخرى، تحتاج إلى مواصفات رسمية من البرنامج. ولكن الحصول حتى معقولة (أقل بكثير رسمية صارمة) مواصفات تعد بالفعل واحدة من اصعب الامور في مجال تطوير البرمجيات. ولذلك فمن عموما من الصعب جدا إثبات <م> اهتمام الأشياء عن برنامج (في العالم الحقيقي).
ولكن هناك بعض الأشياء التي يمكن أن تكون (وكان) رسميا أكثر سهولة (وثبت). إذا كنت تستطيع على الأقل إثبات أن البرنامج لن تحطم، وهذا بالفعل شيء: -)
وراجع للشغل، وبعض تحذيرات مترجم / أخطاء هي في الأساس (بسيطة) البراهين حول البرنامج. على سبيل المثال، فإن مترجم جافا تثبت أنك أبدا الوصول إلى متغير غير مهيأ في التعليمات البرمجية (وإلا فإنه سوف تعطيك خطأ المترجم).
لم أقرأ جميع الإجابات، لكن من وجهة نظري، إثبات البرامج لا معنى له، ولهذا السبب لا أحد يفعل ذلك.
إذا كان لديك مشروع صغير/متوسط نسبيًا (على سبيل المثال، 10 آلاف سطر من التعليمات البرمجية)، فمن المحتمل أن يكون الدليل أيضًا 10 آلاف سطر، إن لم يكن أطول.
فكر في الأمر، إذا كان من الممكن أن يحتوي البرنامج على أخطاء، فقد يحتوي الدليل أيضًا على "أخطاء".ربما ستحتاج إلى دليل على الإثبات!
شيء آخر يجب أخذه في الاعتبار، هو أن البرامج رسمية ودقيقة للغاية.لا يمكنك أن تكون أكثر صرامة ورسمية، لأن كود البرنامج يجب أن يتم تنفيذه بواسطة آلة غبية للغاية.
بينما سيتم قراءة البراهين من قبل البشر، فهي تميل إلى أن تكون أقل صرامة من الكود الفعلي.
الشيء الوحيد الذي تريد إثباته هو الخوارزميات منخفضة المستوى التي تعمل على هياكل بيانات محددة (على سبيل المثال.الفرز السريع، والإدراج في شجرة ثنائية، وما إلى ذلك).
هذه الأشياء معقدة إلى حد ما، وليس من الواضح على الفور سبب نجاحها و/أو ما إذا كانت ستعمل دائمًا.إنها أيضًا اللبنات الأساسية لجميع البرامج الأخرى.
وركزت معظم الإجابات على هذه الممارسة وهذا موافق: في الواقع كنت لا يهتمون التدقيق الرسمي. ولكن ما هو في النظرية؟
يمكن إثباتوالبرامج مثلما بيان الرياضي يمكن. ولكن ليس بالمعنى يعني لك! في أي إطار قوية كافية، هناك تصريحات الرياضية (والبرامج) التي لا يمكن إثباتها! انظر هنا
والكثير من الضوضاء هنا، ولكن انا ذاهب الى الصراخ في مهب الريح على أية حال ...
و"إثبات صحيح" لديها معان مختلفة في سياقات مختلفة. في النظم الرسمية و "إثبات صحيح" يعني أن صيغة يمكن استخلاصها من الآخر ثبت (أو البديهي ) الصيغ. "يثبت صحيحة" في البرمجة معارض ببساطة كود ليكون معادلا لمواصفات رسمية. ولكن كيف يمكن إثبات المواصفات الرسمية الصحيحة؟ للأسف، لا توجد وسيلة لإظهار المواصفات أن تكون خالية من الشوائب أو حل أي مشكلة في العالم الحقيقي أخرى من خلال الاختبار.
وفقط بلدي 2 سنت، إضافة إلى الاشياء المثيرة للاهتمام بالفعل هناك.
ومن جميع البرامج التي لا يمكن إثباتها، وأكثرها شيوعا هي تلك أداء IO (بعض التفاعل unpredictible مع العالم أو المستخدمين). حتى البراهين الآلي في بعض الأحيان مجرد ننسى أن برامج "ثبت" "تعمل على بعض الأجهزة الفعلي، وليس واحدة مثالية وصفها النموذج.
في الجانب الآخر البراهين الرياضيات لا يعيرون اي اهتمام الكثير من دول العالم. سؤال متكرر مع الرياضيات هو ما اذا كان يصف أي شيء حقيقي. يقام في كل مرة شيئا جديدا مثل أرقام خيالية أو واخترع مسافة غير الإقليدية. ثم نسي السؤال عن هذه النظريات الجديدة هي تلك الأدوات الجيدة. مثل برنامج جيد، وأنها تعمل فقط.
