Czy komputery mogą wszystko?

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

Alan Turing

Powyższa teoria została stworzona przez Alana Turinga przed Drugą Wojną Światową. Jej celem jest pokazanie, że komputery są w pewien sposób ograniczone. Aby dokładniej to ograniczenie zbadać, spróbujemy przyjrzeć się mu w bardziej formalny sposób.

alternative text Turing zajmował się nie tylko czysto teoretyczną informatyką. W czasie Drugiej Wojny Światowej pracował w zespole, którego zadaniem było łamanie niemieckich szyfrów. Na zdjęciu widać replikę maszyny deszyfrującej zaprojektowanej przez niego.

Numerowanie programów

Wyobraźmy sobie, że ktoś ponumerował wszystkie programy napisane w c++ (albo dowolnym innym języku programowania). Jak można to zrobić? Na przykład – najpierw ustawiamy leksykograficznie (tzn. jak w słowniku) wszystkie programy, składające się z 200 znaków lub mniej. Potem ustawiamy wszystkie programy mające więcej niż 200 ale mniej niż 400 znaków. I tak dalej – w ten sposób każdy program dostanie swój numer.

Jak to działa? wyobraźmy sobie, że mamy program, który ma 350 znaków i chcemy wiedzieć, jaki dostał numer. Załóżmy, że jest 1000 programów krótszych niż 200 znaków. W takim razie nasz program dostanie numer większy niż 1000. Potem patrzymy na wszystkie ciągi składające się z więcej niż 200, ale mniej niż 400 znaków zapisują poprawny program w c++. Wybieramy jest i ustawiamy leksykograficznie. W ten sposób nasz program dostanie odpowiedni numer!

Ograniczymy się do programów, które czytają jedną lub dwie liczby naturalne i jako wynik zwracają również liczbę naturalną. Niech $ P(j) $ oznacza program, który dostał numer $ j $. Jeżeli $ P(j) $ po wczytania 10 zwraca 11, to zapiszemy to tak: $ h_{P(j)}(10) = 11 $. Jeżeli natomiast $ P(j) $ po wczytaniu 9 zapętla się, to zapiszemy to tak: $ h_{P(j)}(9) = \bot $.

Symbol $ \bot $ po polsku czyta się: pinezka.W informatyce służy on między innymi do oznaczania sytuacji oznaczających niepowodzenie programu. Tutaj mówimy, że program zwrócił pinezkę mając na myśli to, że się zapętlił.

Programy i funkcje

W ten sposób program $ P_j $ definiuje funkcję matematyczną $ h_{P(j)} : \mathbb{N}\rightarrow \mathbb{N} \cup \{ \bot \} $ Taki zapis oznacza, że argumentami funkcji $ h_{P(j)} $ są liczby naturalne, a wartościami liczby naturalne i "zapętlanie się". Wartość funkcji $ h_{P(j)} $ w punkcie $ x $ wynosi $ y \in \mathbb{N} $ (tzn. $ h_{P(j)}(x) = y \in \mathbb{N} $ )jeżeli program $ P(j) $ po wczytaniu liczby $ x $ zwraca liczbę $ y $. Wartość funkcji $ h_{P(j)} $ w punkcie $ x $ wynosi $ \bot $ (tzn. $ h_{P(j)}(x) = \bot $ )jeżeli program $ P(j) $ po wczytaniu liczby $ x $ zapętla się i nie zwraca żadnego wyniku.

Wiemy już, że każdemu algorytmowi odpowiada funkcja matematyczna. A czy każdej funkcji matematycznej odpowiada algorytm? Popatrzmy na funkcję:

$$f(j,k) = \left\{ 
\begin{array}{l l}
  1 & \quad \mbox{jeżeli $h_{P(j)}(k) \in \mathbb{N}$} \\
  0 & \quad \mbox{w przeciwnym razie}\\ 
\end{array} \right.$$
Ta funkcja przyjmuje wartość 1, jeżeli j-ty program zwraca jakiś wynik po wczytania liczby k. Jeżeli j-ty program zapętla się po wczytaniu liczby k, to funkcja f przyjmuje wartość 0. Ale już wcześniej pokazaliśmy, że nie może istnień program obliczający tę funkcję! Widzimy więc, że nie wszystkie wszystkie funkcje mogą być obliczone na komputerze!

Ciekawa funkcja obliczalna

Funkcja $ f $ nie jest obliczalna przez żaden program. Czy jest takich funkcji więcej? Tak, a zaraz zobaczymy jeszcze jedną. Teraz dla odmiany popatrzmy na funkcję bardzo podobną do $ f $, ale obliczalną.

Funkcja $ g $ jest zdefiniowana następująco $ g $:

$$g(j,k) = \left\{ 
\begin{array}{l l}
  1 & \quad \mbox{jeżeli $h_{P(j)}(k) \in \mathbb{N}$} \\
  \bot & \quad \mbox{w przeciwnym razie}\\ 
\end{array} \right.$$
Czy ta funkcja jest obliczalna? Okazuje się, że tak! Oblicza ją następujący program:

1
2
3
4
5
 Wczytaj liczbę j,
 Wczytaj liczbę k,
 Uruchom j-ty program na liczbie k
 Jeżeli ten program zwróci wynik:
   Zwróc 1

Jeżeli $ j $-ty program się zapętla na liczbie $ k $, to również program obliczający funkcję $ g $ zapętli się w kroku 3. Ciekawe, że funkcja $ g $ wygląd bardzo podobnie do $ f $, ale w przeciwieństwie do niej jest obliczalna. Widać, że problemy z funkcją $ f $ wynikały stąd, że zawsze żądaliśmy wyniku - program obliczający funkcję $ f $ nie mógł się zapętlić.

Ciekawa funkcja nieobliczalna

Spróbujmy teraz innej funkcji:

$$t(j) = \left\{ 
\begin{array}{l l}
  1 & \quad \mbox{jeżeli istnieje takie m, że $h_{P(m)}(k) \in \mathbb{N}$} \\
  0 & \quad \mbox{w przeciwnym razie}\\ 
\end{array} \right.$$
Funkcja h mówi, czy istnieją takie dane wejściowe, dla który j-ty program się nie zapętli. Załóżmy, że te funkcja jest obliczana przez algorytm B. Teraz zobaczycie fajną sztuczkę. Najpierw popatrzmy na ten program:

1
2
   Wczytaj liczbę a,
   Uruchom j-ty program na liczbie k i zwróć taki wynik, jak ten program.

< Przede wszystkim jego działanie jest niezależne od wczytanego argumentu i zawsze działa jak j-ty program na wejściu k. Stąd nazwa Stały. Co więcej, ma on w sobie zaszyte dwie stałe j i k. Kod programu zmieni się, jeżeli użyjemy innej pary liczb j, k. Dlatego nazwa musi uwzględniać te liczby. Tak więc pełna nazwa powyższego programu to: Stały(j,k). Skoro powiedzieliśmy o nim wszystko co się dało powiedzieć, to popatrzmy teraz na inny program:

1
2
3
4
 Wczytaj liczbę j,
 Wczytaj liczbę k,
 Niech l oznacza numer programu Stały(j,k)
 Uruchom program B na wejściu l i zwróć taki wynik, jak ten program.

Funkcja, którą oblicza program C

Niech $ h_C $ oznacza funkcję obliczaną przez program C. Spróbujmy powiedzieć o niej coś ciekawego. Pamiętajmy, że algorytm $ B $ oblicza funkcję $ t $. Załóżmy, że $ h_C(j,k) = 1 $. Oznacza to, że $ t(l)=1 $. Czyli istnieje takie $ m $, że $ h_{P(l)}(m) \in \mathbb{N} $. Jeżeli jednak przypomnimy sobie to co wiemy o programie Stały(j,k) to zobaczymy, że oznacza to, że dla każdego $ m $ mamy $ h_{P(l)}(m) \in N $ i równoważnie $ h_P(j)(k) \in N $. Pokazaliśmy, że jeżeli $ h_C(j,k) = 1 $ to $ h_P(j)(k) \in N $. Czyli, jeżeli dla jakiejś pary liczb $ (j,k) $ funkcja $ h_C $ przyjmuje wartość 1, to $ h_P(j)(k) \in N $. Czyli, jeżeli dla jakiejś pary liczb $ (j,k) $ funkcja $ h_C $ przyjmuje wartość 1, to $ j $-ty program nie zatrzymuje się, po wczytaniu liczby $ k $.

Podobnie, jeżeli $ h_C(j,k) = 0 $, oznacza to, że $ h_{P(j)}(k) = \bot $. Czyli, jeżeli $ h_C(j,k) = 0 $, to $ j $-ty program zapętla się, po wczytaniu liczby $ k $. Zatem program C oblicza funkcję $ t $. Ale już wcześniej pokazaliśmy, że jest to niemożliwie! Zatem znowu mamy sprzeczność! Tym razem oznacza ona, że funkcja $ t $ nie jest obliczalna. Zatem nie istnieje program, który sprawdzałby, czy istnieją dane wejściowe, dla których inny program się zapętli.

Matematyczne ograniczenia komputerów

Zobaczyliśmy dlaczego kompilator nie wyłapuje niektórych błędów - dlatego, że zwyczajnie nie może! Pokazaliśmy, że jest niemożliwe automatyczne sprawdzenie, czy program zapętli się dla konkretnych danych wejściowych oraz czy istnieją dane wejściowe, dla których się zapętli. Wszystkie te wyniki uzyskaliśmy szukając podobieństw i różnic między funkcjami matematycznymi i programami. W ten sposób pokazaliśmy, że to ograniczenie ma matematyczną naturę - da się go w sposób ścisły dowieść i nie da się go ominąć zatrudniając lepszego programistę, bądź kupując lepszy komputer.

Wszystkie zdjęcia w artykule pochodzą z wikipedii.
  • Źródło zdjęcia robota oraz informacja o licencji, na jakiej zostało opublikowane: link.
  • Źródło zdjęcia maszyny deszyfrującej oraz informacje o licencji, na jakiej zostało opublikowane: link.
4.4
Twoja ocena: Brak Ocena: 4.4 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com