מה ההבדל בין נכונות מוחלטת לתקינות חלקית?
תשובה 1:
מפרט נכונות מוחלט הוא גם מפרט תקינות חלקי. התקינות החלקית חלשה מכיוון שהיא זקוקה לעזרה הנוספת של 'S מסתיים' כדי להגיע למסקנה: R מחזיק במצב הסופי.
למפרט תקינות חלקי {Q} S {R}, אתה יכול לקבל את המידע הבא: בהינתן מצב התחלתי העונה על Q, S עשויה להסתיים או לא. אם S תסתיים, לאחר הוצאתו להורג של S, תגיע למצב סופי שמספק את R. אם לא, R הוא חסר תועלת מכיוון שאין מצב סופי.
לדוגמה:
{x == 10} בזמן (y! = 0): y = y - 1 x = 0 {x == 0}
זהו מפרט תקינות חלקי. אם y מאתחל עם מספר כלשהו שווה או גדול מ- 0, S יסתיים ואחרי זה x הוא 0. בעוד שאם y מתחיל במספר שלילי, S תעבור לולאה לנצח ומכיוון שהיא לא תסתיים, לא תגיע למצב ' לאחר הוצאתו להורג של ש '.
אכן, R יכול להיות כל דבר אם S היא לולאה מתה. לדוגמה, לכל שאלה ו- R:
{ש} בעוד (נכון): y = y - 1 {R}
הוא תמיד מפרט תקינות חלקי.
אם Q אינו מספיק חזק, אינך יכול להבטיח את סיום ש ', על אחת כמה וכמה סיבה לגבי המדינה לאחר הוצאתו להורג של ש. במקרה זה אתה יכול להוסיף תנאי ידנית: S מסתיים. עם Q וזה, ההנמקה יכולה להימשך.
למפרט נכונות מוחלטת {Q} S {R}, Q הוא חזק מספיק כדי להבטיח את סיום S, כך שתוכלו להסיק ש- תסתיים והמדינה הסופית מספקת את ר.
לדוגמה:
{x == 10} בזמן (x! = 0): x = x - 1 {x == 0}
הוא מפרט מוחלט של נכונות.
BTW: אני לא בטוח אם התשובה נכונה מכיוון שהשאלה מתויגת עם התקינות הפוליטית. ואילו ההגדרה בשאלה נראית בדיוק זהה למדעי המחשב.