Hva er forskjellen mellom total korrekthet og delvis korrekthet?


Svar 1:

En total korrekthetsspesifikasjon er også en delvis korrekthetsspesifikasjon. Delvis korrekthet er svakere fordi den trenger den ekstra hjelpen fra 'S slutter' for å komme til konklusjonen: R holder i den endelige tilstanden.

For en spesifikasjon av delvis korrekthet {Q} S {R}, kan du få følgende informasjon: Gitt en starttilstand som tilfredsstiller Q, kan S avslutte eller ikke. Hvis S avslutter, etter S 'henrettelse, vil du nå en endelig tilstand som tilfredsstiller R. Hvis ikke, er R ubrukelig siden det ikke er noen endelig tilstand.

For eksempel:

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

Det er en delvis korrekthetsspesifikasjon. Hvis y er initialisert med et antall som er lik eller større enn 0, vil S avslutte, og etter det er x 0. Selv om y starter med et negativt tall, vil S sløyfe for alltid, og siden det ikke avsluttes, vil du ikke nå en tilstand ' etter S henrettelse '.

Faktisk kan R være hva som helst hvis S er en dødsløyfe. For eksempel for alle Q og R:

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

er alltid en delvis korrekthetsspesifikasjon.

Hvis Q ikke er sterk nok, kan du ikke garantere S oppsigelse, enn si grunn til staten etter Ss henrettelse. I dette tilfellet kan du manuelt legge til en betingelse: S slutter. Med Q og det kan resonnementet fortsette.

For total korrekthetsspesifikasjon {Q} S {R}, er Q sterk nok til å garantere S oppsigelse, slik at du kan konkludere med at S vil avslutte og den endelige tilstanden tilfredsstiller R.

For eksempel:

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

er en total korrekthetsspesifikasjon.

BTW: Jeg er ikke sikker på om svaret er riktig fordi spørsmålet er merket med politisk korrekthet. Mens definisjonen i spørsmålet ser nøyaktig den samme ut som i informatikk.