Czy komputery mogą wszystko?

16.09.2009 - Krzysztof Dryś
TrudnośćTrudnośćTrudność

Co zrobić, jeżeli ręczne sprawdzanie jest za wolne?

W ten sposób Andrzejowi udało się sprawdzić dwa programy. Niestety, zostało ich jeszcze 998! Ręczne przeglądanie każdego z nich zajęłoby wiele czasu. Co gorsza, Andrzej przypuszczał (i słusznie!), że Janek specjalnie skomplikował kod części programów tak, by trudno było dociec, czy programy zapętlają się, czy nie.

Nic dziwnego, że Andrzej postanowił zautomatyzować sprawdzanie zadań. W tym celu napisał następujący program:

1
2
3
4
5
6
 Wczytaj napis s,
 Wczytaj napis p,
 Jeżeli s jest kodem programu, który zwraca dla napisu p jakiś wynik:
   Wypisz: poprawne,
  W przeciwnym wypadku
   Wypisz: niepoprawne.

Na przykład, jeżeli jako s wpisze się kod programu Staszka, jako p słowo "abrakadabra", to program Andrzeja odpowie: niepoprawne. Jeżeli natomiast jako s wpisze się kod programu Staszka, a jako p jakiekolwiek inne słowo niż "abrakadabra", to program Andrzeja odpowie: poprawne.

Jak jest realizowany krok 3? W tej chwili nie wiemy. Ale załóżmy, że Andrzejowi udało się napisać program, który decyduje, czy s jest kodem programu, który zwraca dla napisu p jakiś wynik.

I wszystko byłoby dobrze, gdyby nie to, że Janek bardzo chciał wygrać zakład. Tak bardzo, że gotów był posunąć się do czynów ściganych przez prawo. Aby śledzić postęp Andrzeja, sobie wiadomym sposobem, włamał się na jego komputer i wykradł jego kod. Na tej podstawie stworzył następujący program:

1
2
3
4
5
6
7
8
 Wczytaj napis p,
 Zapisz w zmiennej s kod tego programu, //Tego, czyli Trzeciego programu Janka właśnie!
 Uruchom program Andrzeja na napisach s i p,
 Jeżeli program Andrzeja wypisze poprawne:
 Dopóki 1 == 1
   Nic nie rób,
 Jeżeli program Andrzeja wypisze niepoprawne
   Wypisz niepoprawne

Na koniec Janek podmienił kod powyższego programu na kod tego, który Andrzej rzeczywiście chciał sprawdzić jako trzeci.

Następny dzień Andrzej zaczął od dalszego sprawdzania programów. Szczerze mówiąc, nie przypuszczał, że zajmie mu to aż tyle czasu. No, ale na szczęście napisał swój program, który powinien przyspieszyć pracę. Uruchomił go i dał mu do wczytania najpierw Trzeci program Janka, a potem napis "abrakadabra".

Jaki wynik uzyskał Andzej?

Spróbujmy razem odpowiedzieć na to pytanie. Rzut oka na program Andrzeja pokazuje, że mógł on uzyskać tylko jeden z dwóch wyników: poprawne albo niepoprawne.

Załóżmy, że uzyskał wynik poprawne. Oznacza to, że Trzeci program Janka uruchomiony na napisie "abrakadabra" zwraca jakiś wynik. Ale to oznacza, że program Andrzeja uruchomiony na Trzecim programie Janka i napisie "abrakadabra" zwraca wynik niepoprawne. A to jest sprzeczność! Czyli Andrzej nie mógł uzyskać wyniku poprawne.

Nie zostaje nam nic innego, niż przyjąć, że uzyskał wynik niepoprawne. Oznacza to, że Trzeci program Janka uruchomiony na napisie "abrakadabra" nie zwraca żadnego wyniku. Ale to oznacza, że program Andrzeja uruchomiony na Trzecim programie Janka i napisie "abrakadabra" zwraca wynik poprawne. Osiągnęliśmy sprzeczność, świadczącą o tym, że Andrzej nie mógł uzyskać wyniku niepoprawne.

Czy zauważyliście, że właśnie stało się coś dziwnego? Okazało się, że program Andrzeja nie może dać ani odpowiedzi poprawne, ani niepoprawne. Ale to oznacza, że nie może nic odpowiedzieć!

Spotkanie ze sprzecznością

Jak to możliwe? Otóż przydarzyło się nam coś, co dosyć często przydarza się matematykom – osiągnęliśmy sprzeczność. Trochę wcześniej założyliśmy, że Andrzej napisał program, który umie odpowiadać na pytanie:

Czy program s, po wpisaniu napisu p zatrzymuje się, czy też się zapętla?

Potem pokazaliśmy, na przykładzie Michała, jak z takiego programu zbudować inny. Na koniec zaś wykorzystaliśmy program Michała, żeby pokazać sprzeczność i udowodnić tym samym, że Andrzej nie mógł napisać swojego programu.

Już wiemy dlaczego kompilator nie ostrzega mnie, że program, który piszę może się zapętlić! Dlatego, że nie istnieje program, który sprawdza, czy inny program, dla pewnych danych wejściowych zapętla się, czy nie. To oznacza, że automatyczne szukanie błędów (a przynajmniej zapętleń) jest niemożliwe! Ta niemożliwość jest ograniczeniem nałożonym przez matematykę na komputery. Jest to problem, z którym nie umie poradzić sobie żaden program.

Trochę szkoda, że jest tak, a nie inaczej, prawda? Miło byłoby, żeby coś sprawdzało automatycznie nasz kod. Niestety, jest to niemożliwe. Później zobaczymy, jakie jeszcze problemy są nie do rozwiązania za pomocą komputera.

4.4
Twoja ocena: Brak Ocena: 4.4 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com