Hvad er forskellen mellem total korrekthed og delvis korrekthed?


Svar 1:

En total korrekthedsspecifikation er også en delvis korrekthedsspecifikation. Delvis korrekthed er svagere, fordi den har brug for den ekstra hjælp fra 'S ophører' for at komme til konklusionen: R holder i den endelige tilstand.

For en delvis korrekthedsspecifikation {Q} S {R} kan du få følgende oplysninger: Givet en starttilstand, der tilfredsstiller Q, kan S muligvis afslutte eller ikke. Hvis S ophører, efter S's henrettelse, vil du nå en endelig tilstand, der tilfredsstiller R. Hvis ikke, er R ubrugelig, da der ikke er nogen endelig tilstand.

For eksempel:

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

Det er en delvis korrekthedsspecifikation. Hvis y er initialiseret med et antal, der er lig med eller større end 0, afsluttes S, og efter det er x 0, mens hvis y starter med et negativt tal, vil S sløjfe for evigt, og da det ikke afsluttes, vil du ikke nå en tilstand ' efter S 'henrettelse'.

Faktisk kan R være noget, hvis S er en dødsløjfe. For enhver Q og R:

{Q}
mens (sandt):
    y = y - 1
{R}

er altid en delvis korrekthedsspecifikation.

Hvis Q ikke er stærk nok, kan du ikke garantere S's opsigelse, hvad så ikke desto mindre grund til staten efter S 'henrettelse. I dette tilfælde kan du manuelt tilføje en betingelse: S slutter. Med Q og det kan resonnementet fortsætte.

For total korrekthedsspecifikation {Q} S {R} er Q stærk nok til at garantere S's ophør, så du kan konkludere, at S vil afslutte, og den endelige tilstand tilfredsstiller R.

For eksempel:

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

er en total korrekthedsspecifikation.

BTW: Jeg er ikke sikker på, om svaret er korrekt, fordi spørgsmålet er mærket med politisk korrekthed. Mens definitionen i spørgsmålet ser nøjagtigt den samme ud som i datalogi.