Jeśli jesteś zaznajomiony z weryfikacją programu, prawdopodobnie wolisz przeczytać pytanie przed tłem . Jeśli nie jesteś zaznajomiony z weryfikacją programu, być może nadal będziesz w stanie odpowiedzieć na to pytanie, ale prawdopodobnie wolisz najpierw przeczytać tło .
tło
Często mówi się, że sprawdzenie częściowej poprawności jest nierozstrzygalne. Dla celów dyskusji wybierzmy jeden bardzo konkretny sposób, aby to stwierdzenie było precyzyjne, w stylu Floyda - Hoare. Flowgraph jest digrafu z wybitnym początkowego węzła , z których wszystkie węzły są osiągalne. Program jest flowgraph którego węzły są polecenia. Istnieją trzy typy założeń komend (1), które zakładają q , (2) twierdzenia potwierdzają q i (3) przypisania v: = e. Tutaj q jest formułą fol (logika pierwszego rzędu), e jest terminem fol, a v jest zmienną.
Mówimy, że program jest częściowo poprawny, gdy istnieje sposób na adnotację każdego węzła x warunkiem wstępnym a (x) i warunkiem dodatkowym b (x), tak że (1) warunek początkowy węzła jest prawidłowy, (2) { a (x) } x { b (x) } obowiązuje dla wszystkich poleceń x , a (3) ( b (x) oznacza, że (y) ) jest ważne dla wszystkich krawędzi od x do y . Tutaj tróje Hoare są zdefiniowane następująco:
- { p } assert q { r } oznacza, że ( p oznacza ( q i r )) jest prawidłowe
- { p } zakładamy, że q { r } oznacza, że (( p i q ) oznacza, że r ) jest poprawny
- { S } v: = E { R } oznacza, że (( P z E zastąpiono v ) wynika, R ) jest ważna
Oto falisty argument, dlaczego sprawdzenie tej częściowej poprawności jest nierozstrzygalne: Po wypełnieniu niektórych a (x) i niektórych b (x) należy sprawdzić, czy niektóre formuły fol są poprawne, a to jest nierozstrzygalne.
Typowym sposobem zakodowania zakończenia w częściowej poprawności jest dodanie pewnych specjalnych stwierdzeń, które zasadniczo mówią „od ostatniego wykonania mnie postęp był postępujący w kierunku zakończenia”. Te asercje postępu muszą być umieszczone w taki sposób, aby wszystkie nieskończone spacery po schemacie blokowym (rozpoczynające się w węźle początkowym) zawierały nieskończenie wiele asercji postępu. Mówiąc ściślej, powiedzmy, że asercje postępu mają zawsze formę aser u < v , gdzie u i v są dodatnimi liczbami całkowitymi, są poprzedzone przypisaniem u : = f , a po nich następuje przypisanie v : = u . Tutaj f jest afunkcja wariantu , u to jej bieżąca wartość, a v to jej poprzednia wartość. Teraz, gdy mówimy o „dodatnich liczbach całkowitych” i porównujemy je, musimy upewnić się, że dostępna jest nieco więcej niż folia: powiedzmy, że arytmetyka Peano jest dostępna. (Nie podoba mi się ten wybór. Możesz zignorować, jeśli jest to wygodne.) Oczywiście, f może korzystać z innych funkcji i stałych wymienionych w programie. (Zauważ, że dodanie założeń na początku programu jest równoważne z wprowadzeniem nielogicznych aksjomatów.)
Teraz, jeśli program z zapewnieniami postępu jest nadal częściowo poprawny, to wiemy, że oryginalny program się kończy.
Pytanie
Biorąc pod uwagę program kończący, wydaje się, że wymyślenie różnych funkcji dla asercji postępu jest trudne. Ale jak ciężko? (Wiem, że nawet przy powyższym ogromnym tle nadal pozostawiłem to pytanie trochę otwarte lub źle zdefiniowane, w zależności od tego, jak chcesz na nie spojrzeć.)
Innymi słowy: szukam odniesienia, które sformalizuje problem sprowadzenia terminacji do częściowej poprawności, a następnie powie coś o jego złożoności. Odpowiedź, która robi to wszystko, byłaby oczywiście mile widziana.