Vad är skillnaden mellan total korrekthet och partiell korrekthet?


Svar 1:

En total riktighetsspecifikation är också en partiell korrekthetsspecifikation. Partiell korrekthet är svagare eftersom den behöver ytterligare hjälp av 'S upphör' för att komma till slutsatsen: R håller i slutläget.

För en partiell korrekthetsspecifikation {Q} S {R} kan du få följande information: Med tanke på ett startläge som uppfyller Q kan S avsluta eller inte. Om S avslutar, efter S: s körning, kommer du att nå ett slutligt tillstånd som uppfyller R. Om inte, är R värdelös eftersom det inte finns något slutligt tillstånd.

Till exempel:

{X == 10}
medan (y! = 0):
    y = y - 1
x = 0
{X == 0}

Det är en partiell korrekthetsspecifikation. Om y initieras med ett antal som är lika eller större än 0, kommer S att avsluta och efter det är x 0. Medan om y börjar med ett negativt tal, kommer S att slinga för evigt och eftersom det inte avslutas kommer du inte att nå ett tillstånd ' efter S: s avrättning.

I själva verket kan R vara vad som helst om S är en dead-loop. Till exempel för alla Q och R:

{Q}
medan (sant):
    y = y - 1
{R}

är alltid en partiell korrekthetsspecifikation.

Om Q inte är tillräckligt stark kan du inte garantera S: s uppsägning, än mindre anledning till staten efter S: s avrättning. I det här fallet kan du manuellt lägga till ett villkor: S upphör. Med Q och det kan resonemanget fortsätta.

För total korrekthetsspecifikation {Q} S {R} är Q tillräckligt stark för att garantera S: s uppsägning, så du kan dra slutsatsen att S kommer att avsluta och det slutliga tillståndet uppfyller R.

Till exempel:

{x == 10}
medan (x! = 0):
    x = x - 1
{x == 0}

är en total riktighetsspecifikation.

BTW: Jag är inte säker på om svaret är korrekt eftersom frågan är taggad med politisk korrekthet. Även om definitionen i frågan ser exakt ut som i datavetenskap.