Czy komputery mogą wszystko?

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

O tym, czego nie umieją (i nigdy nie będą umiały!) zrobić komputery. I o tym, co się kryje na styku światów informatyki i matematyki.

Czy da się automatycznie szukać błędów?

Na pewno nie raz zdarzyło się Wam zirytować przez błąd w jakimś programie. Gdy edytor tekstu na którym pracowaliśmy przez ostatnie pół godziny wyłączy się bez ostrzeżenia w kierunku komputera paść mogą najgorsze przekleństwa. Jasne, programiści, jak wszyscy ludzie, popełniają błędy. Ale dlaczego nikt nie napisze programu, który ich wszystkich szuka? Dlaczego, gdy kompiluję program napisany w C++, kompilator nie krzyczy na mnie: "Uwaga! Jeżeli wejściem tego programu będzie 1, to się on zapętli i nigdy nie skończy!"? Postaramy się poszukać odpowiedzi na pytania!

Ryzykowany zakład

W tych poszukiwaniach pomoże nam Andrzej. Andrzej spędza dużo czasu przed komputerem. Nie ma co ukrywać, zdecydowanie za dużo gra w World of Warcraft. Ale sporo czasu poświęca też na naukę programowania. Nawet zdobył opinię najlepszego informatyka na osiedlu.

Obok Andrzeja mieszka Janek. Janek jest trochę młodszy, ale bardzo ambitny. Od jakiegoś czasu uczy się programować. Przyświeca mu przy tym jeden cel - chce pokazać wszystkim, że jest lepszym informatykiem od Andrzeja. W tym celu zaproponował mu zakład na następujących warunkach:

1. Janek dostarczy dostarczy Andrzejowi kod źródłowy 1000 różnych programów. 2. Andrzej wygra zakład, jeżeli uda mu się powiedzieć, który z tych programów po wpisaniu "abrakadabra" zapętla się, a który zwraca wynik. 3. Jeżeli dla któregoś z programów Andrzej pomyli się, zakład wygra Janek.

Co znaczy, że program się zapętlił? Oznacza to, że jest w takim stanie, że nigdy nie zakończy obliczeń i nigdy nie zwróci wyniku. Zazwyczaj chcemy, żeby nasze programy się nie zapętlały. Ale zdarza się, że wolimy, żeby niektóre (np. systemy operacyjne) nigdy się nie kończyły. Może to zaskakujące, ale chcemy, żeby Linux się zapętlał!

Problem wydaje się łatwy, prawda? Andrzej też tak myślał i dlatego przyjął zakład. Następnego dnia rano odebrał od Janka maila. W załączniku do niego było obiecanych 1000 programów.

Podstęp Janka

Andrzej wybrał pierwszy z brzegu program, skompilował go, uruchomił, wpisał "abrakadabra" i zaczął czekać... Po 10 minutach znudziło mu się czekanie. Już miał uznać, że ten program się zapętla, gdy wiedziony nagłym przeczuciem postanowił popatrzeć na jego kod. Zobaczył coś takiego:

1
2
3
4
 Wczytaj napis s
 Dla i = 1...1 000 000 000 000 000
   Nic nie rób
 Zlicz literki 'a' w s i wypisz wynik.

Ten program się nie zapętla! On tylko działa bardzo długo! Co więcej, Janek zamiast 1000 000 000 000 000 mógł wstawić inną, dowolnie większą liczbę.

Do Andrzeja zaczęło powoli dochodzić, że nie będzie tak łatwo wygrać tego zakładu. Bogatszy o tę myśl przeszedł do drugiego programu. Tym razem, przed uruchamianiem czegokolwiek, Andrzej postanowił popatrzeć na kod. Wyglądał on tak:

1
2
3
4
 Wczytaj napis s
 Dopóki s == "abrakadabra"
  Nic nie rób,
 Zlicz literki 'a' w s i wypisz wynik.

Tutaj sprawa była jasna. Dlaczego? Otóż dlatego, że jeżeli użytkownik wpisze "abrakadabra", to program nigdy nie zwróci wyniku! Utknie w pętli w kroku 2 i nigdy nie przejdzie do kroku 4.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com