LECTORIUM CALCULEMUS

WITOLD MARCISZEWSKI Wykłady: WSAP im. Stanisława Staszica: 2007/2008 Filozofia Umysłu i Sztucznej Inteligencji

4. Odkrycie potęgi algorytmu (Al-Chwarizmi) i jej ograniczeń (Gödel, Turing)

Reguły, dyrektywy, normy, przepisy, wskazówki, recepty, czy jak to jeszcze nazwać, towarzyszą naszemu postępowaniu, określając je na każdym kroku. Cokolwiek robię, robię według jakichś reguł; tworząc ten tekst, stosuję się do dyrektyw ortografii, gramatyki, stylistyki, komunikacji z czytelnikiem, programowania tekstu w języku HTML, posługiwania się klawiaturą itd. Łatwo zauważyć, że reguły różnią się stopniem dokładności. Zależnie od tego, dostajemy więcej lub mniej informacji, jak postępować. Na jednym krańcu są zalecenia tak ogólnikowe i niejasne, jak "czyń dobrze", "unikaj zła"; mamy też inne, nieco dokładniejsze, jak "zastanów się przed decyzją" (przysłowiowe "trzy razy pomyśl potem zrób"). Są wreszcie takie, które ów postulat dokładności, a więc informacyjności maksymalnej, spełniają w stopniu najwyższym. Te ostatnie nazywają się algorytmami (skąd taka osobliwa nazwa, mowa będzie niebawem). Gdy wykonuję jakieś zadanie, czyli (co na jedno wychodzi) rozwiązuję jakiś problem, korzystam z pewnego zestawu reguł, stosując je w przepisanej kolejności (smażąc jajecznicę, wpierw rozbijam jajko i potem rzucam je na patelnię, a nie odwrotnie). Zastanówmy się, jakie warunki powinien spełnić taki zestaw, żeby awansować do rangi algorytmu. Oto lista jego chwalebnych własności. CECHY ALGORYTMU Opis zalecanego postępowania podzielony jest na możliwie najmniejsze czynności czyli najmniejsze kroki, a wymienia się je bez jakichkolwiek opuszczeń. To znaczy, niczego się nie pozostawia domyślności czy pomysłowości wykonawcy. Nie pojawiają się więc zalecenia w rodzaju "dodaj soli i pieprzu do smaku", ale będzie dokladnie powiedziane ile dać gramów, czy ułamków grama, jednego i drugiego. Kroki wyliczone są w tej kolejności, w jakiej mają być wykonywane. Opis każdego kroku wymienia jedynie cechy fizyczne obiektu, na którym wykonywana jest dana czynność. Np. algorytm arytmetyczny nie mówi o liczbach, bo te są jestestwami ze świata abstrakcji, lecz o cyfrach, czyli wytworzonych fizycznie, np. ołówkiem na papierze, reprezentacjach liczb. Nie odwołuje się też algorym do czynności myślowych, a więc ze świata psychicznego. Nie są przeto algorytmami Kartezjuszowe reguły rozwiązywania problemów w rodzaju: "Należy się zastanawiać tylko nad tym, co możemy ująć jasną i oczywistą intuicją" (Reguła III w Prawidłach do kierowania umysłem). Kartezjusz nawet ostrzegał przed posługiwaniem się algorytmami (wysnuwając te przestrogi ze swych założeń filozoficznych na temat umysłu i ciała); był w tym względzie przeciwieństwem Leibniza, który w algorytmach pokładał nadzieję na przyszły wspaniały rozwój nauki (co wyrażał w haśle Calculemus!). Ostatni krok daje zawsze niezawodnie rozwiązanie problemu z tej klasy zagadnień, do których rozwiązywania dany algorytm jest przeznaczony. Wyrazistym przykładem są algorytmy arytmetyczne, każdy dla innej klasy działań, a w obrębie danej klasy zdolny do rozwiązywania nieskończenie wielu problemów. Charakterystyka algorytmu w tych czterech punktach umożliwia odróżnienie procedury i programu (komputerowego). Procedurą nazwiemy postępowanie opisane w 1-3, ale nie koniecznie spełniające warunek 4, tj. niezawodności (procedury są tym, co wykonują maszyny Turinga, z których jedne rozwiązują zadany problem, inne zaś nie). Program jest to algorytm zapisany w jakimś języku maszynowym, w szczególności w notacji binarnej, w której jedynce i zeru odpowiadają różne stany fizyczne (jak impuls elektryczny i jego brak). Jest więc program takim algorytmem, w którym punkt 3 dotyczy stanów fizycznych maszyny jako symboli reprezentujących liczby. Słownik i składnia języków maszynowych różnią się odpowiednio do konstrukcji danego typu komputera. Można to sobie wyobrazić tak, że w jednym języku polecenie "drukuj" ma postać "01", a w innym "10" (oczywiście, jest to przykład skrajnie uproszczony, naprawdę takich symboli będą w jednym poleceniu krocie). Żeby podsumować rzecz jednym zdaniem, przytoczmy definicję algorytmu spotykaną w pojęciach bardziej popularnych, mniej dokładną, lecz za to krótką: Algorytm to zbiór dobrze zdefiniowanych kroków prowadzących do wykonania pewnego zadania (rozwiązania problemu). Punkty 1, 2 i 3 powyżej precyzują, na czym polega dobre zdefiniowanie kroków. Dla zachowania porządku w naszym myśleniu o algorytmach, trzeba mieć na uwadze pewną wieloznaczność tego terminu, z której jednak nie należy czynić mu zarzutu; jest to bowiem wieloznaczność zachowująca się w sposób systematyczny, łatwa do rozpoznania dzięki kontekstowi, a związana z tą zaletą, że wystarczy jeden termin zamiast kilku. Gdy się powiada, "idźmy na kolację" i "kolacja na stole", nie wnioskujemy z tych dwóch zdań, że jest to zachęta do wejścia na stół ("idźmy na to, co na stole"). Wiadomo z kontekstu, że pierwsze oznacza pewne postępowanie, mianowicie czynność spożywania tego, o czym mówi drugie. W terminie "algorytm" splatają się trzy sensy: pewnego rodzaju postępowanie, a więc zbiór kolejnych kroków czyli czyności; przepis na takie postępowanie (charakteryzują go punkty 1-4); abstrakcyjny obiekt matematyczny. Jeśli algorytm dotyczy obliczeń, to opis postępowania, które składa się z czynności obliczeniowych jest zarazem opisem funkcji arytmetycznych (dodawania etc.) czyniących to postępowania prawomocnym; nazywamy więc również algorytmem zbiór takich funkcji, a te są obiektami abstrakcyjnymi, podobnie jak liczby. Historia algorytmu ma wielu bohaterów, w tym Euklidesa, który zasługuje na szczególną uwagę, ale trudno poświęcić mu ją w tym miejscu. Poznamy tu trzy spośród głównych w tej historii postaci (w kolejności ich portretów otwierających obecną stronę).

MUHAMMAD IBN MUSA AL-CHWARIZMI działał w IX wieku w Bagdadzie, sławetnym wówczas światowym centrum cywilizacji, w Domu Nauki - ośrodku badawczym z kolosalną biblioteką. Jego przełożone na łacinę dzieło o regułach działań arytmetycznych wykonywanych w przyjętej za Hindusami notacji pozycyjnej nosiło tytuł Algorithmi de numero Indorum. "Algorithmus" (w dopełniaczu "Algorithmi") to łacińska transkrypcja imienia autora. Stąd owe reguły czyli instrukcje nazwano algorytmami. Póżniej nazwę tę rozciągnięto na wszelkie reguły mechanicznego rachowania, wreszcie - na wszelkie mechaniczne procedury systematycznego rozwiązywania problemów. Pewne stany fizyczne przekształca się w nich na inne, ściśle według instrukcji dyktujących kolejność i rodzaj przekształceń, aż dojdzie się do pewnego stanu końcowego, co jest wykonaniem postawionego zadania czyli rozwiązaniem problemu (np. upieczeniem sernika, znalezieniem pierwiastka kwadratowego z dwóch etc); stanami fizycznymi są m.in. tworzone z symboli napisy, impulsy elektryczne itd. KURT GÖDEL (zdjęcie w środku, kopia ze strony www.ias.edu/spfeatures/kurt_godel/ ), 1906-1978, doktoryzował się w roku 1929. W 1931 opublikował studium z logiki matematycznej Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I, gdzie sformułował słynne twierdzenie o niepełności (inaczej, niezupełności) arytmetyki: istnieją prawdy arytmetyczne nie dające się dowieść w sposób algorytmiczny. Wynika zeń, że nie istnieje algorytm, wedle którego można by tak zaprogramować komputer, by zdołał rozstrzygnąć wszystkie problemy matematyczne; jest to stwierdzenie o kluczowym znaczeniu dla informatyki. To przełomowe w dziejach nauki studium stanowiło w karierze Gödla podstawę jego habilitacji; po jej uzyskaniu, od 1933, objął on w Uniwersytecie Wiedeńskim stanowisko Privatdozent. W 1934 wygłosił w Princeton cykl wykładów: O zdaniach nierozstrzygalnych w sformalizowanych teoriach matematycznych. W 1938-39 ponownie pracował w Princeton, Institute for Advanced Study, gdzie zaprzyjaźnił się blisko z Einsteinem. W 1948 uzyskał obywatelstwo amerykańskie. Resztę życia spędził w Princeton jako profesor. Sednem błyskotliwego pomysłu Gödla (1931), jak wykazać niepełność arytmetyki liczb naturalnych, jest następujące odwzorowanie (zabieg poznawczy często stosowany w matematyce, i nie tylko). Logiczną relację dowodzenia, gdzie Z symbolizuje zbiór zdań stanowiących dowód zdania w (symbolicznie: D(Z,w)) odwzorowuje się w specjalnie skonstruowanej relacji arytmetycznej, którą oznaczymy przez ArD. Naturę odwzorowania jakiegoś układu w innym wyjaśnijmy na przykładzie reprezentowania pewnego terenu przez mapę; niech będzie to w skali 1:100.000. Miejscowości A i B są reprezentowane na mapie przez umowne rysunki, np. kółeczka, R(A) i R(B) odległe od siebie o jeden centymetr. Na mocy konwencji co do skali, odcinek ten odwzorowuje jeden kilometr. Gdy teraz ktoś zapyta, jaka jest odległość A od B, można odpowiedzieć na dwa sposoby, różne w formie, ale dające te samą informację: że jest to odległośc 1 km., bądź że jest to odległość 1 cm. między R(A) i R(B) na mapie w skali 1:100.000. Rodzajem odwzorowania jest również przekład tekstu na inny język, a także operacja szyfrowania tekstu. Odwzorowanie w arytmetyce operacji dowodzenia zdania w na podstawie zbioru zdań Z zaczyna się od tego, że formy (struktury) logiczne zdań określa się liczbowo pewną metodą przyjętą w szyfrowaniu tekstów za pomocą liczb. Nazywamy te liczby numerami zdań i zbiorów zdań. Oznaczmy je, odpowiednio, symbolami N(w) i N(Z). Tak jak wniosek zależy od zbioru zdań stanowiących dowód (na mocy relacji zachodzącej między strukturami zdań), tak liczba N(w) na mocy odpowiedniej relacji arytmetycznej ArD zależy od N(Z). W myśl więc zasady odwzorowania, mamy: D(Z, w) jest prawdą wtedy i tylko wtedy, gdy jest prawdą ArD(N(Z), N(w)). Lewa strona tej równoważności jest wyrażona w języku metodologicznym M (pojęcie dowodu należy do metodologii nauk), a prawa w języku arytmetycznym A. Korzystając z takich środków wyrazu, Gödel utworzył zdanie w M, które ochrzcimy imieniem "g". Mówi ono o sobie samym, że jest niedowodliwe, w sensie braku dowodu algorytmicznego w arytmetyce. Następnie odwzorował je w pewnym zdaniu języka A, tak zmyślnie konstruując to drugie, by jego strukturę określał numer N(g). Symbolicznie: [g]: ~(EZ ) D(Z, g) . . . . w języku M; N(g) ~(EN(Z) ) ArD(N(Z), N(g)) . . . . w języku A. Zdanie g przypomina te osobliwe twory językowe, które nazywamy antynomiami (stanowią one szczególnie efektowny rodzaj sprzeczności). Inaczej jednak niż słynna antynomia kłamcy, która prowadzi do sprzeczności zarówno wtedy, gdy przyjąć, że dane zdanie ("ja w tej chwili kłamię") jest prawdziwe, jak i wtedy, gdy przyjąć jego fałszywość, zdanie g rodzi sprzeczność tylko jednostronnie: jeśli przyjąć, że jest fałszywe. Gdyby było fałszywe, znaczyłoby to, że jest dowodliwe z aksjomatów arytmetyki. To jednak być nie może, bo aksjomaty te są prawdziwe, a z prawdy nigdy nie wynika fałsz; tylko gdyby aksjomaty były między sobą sprzeczne, a więc gdzieś byłby w nich fałsz, dałoby się na ich podstawie wykazać sąd o fałszywości zdania g (ze sprzeczności wynika wszystko). Zdanie g zatem mówi prawdziwie o swej niedowodliwości. Skoro tak, a tę samą prawdę wyraża, tyle że w języku A, zdanie numerowane jako N(g), to także to zdanie musi być prawdą, dotyczącą liczby N(g). Jest zaś wyrażenie pod numerem N(g) zdaniem arytmetycznym. Istnieje przeto zdanie arytmetyczne mówiące prawdę o swej niedowodliwości, a więc niedowodliwe i zarazem prawdziwe. Skoro dowód rozumie się w sensie procedury sformalizowanej (por. termin "formal" w tytule pracy Gödla i temat wykładów w Princeton), czyli algorytmicznej, to niedowodliwość zdania g oznacza brak algorytmu, który wykazałby jego prawdziwość. Wykazuje ją jednak nie-algorytmiczne rozumowanie Gödla. Tak Gödel pokazał, jakich doznaje ograniczeń moc algorytmów, podczas gdy nie podlega im moc ludzkiego umysłu. Tę samą wymowę, choć uzyskaną technicznie na innej drodze, mają wyniki Turinga. D a l e j ... rozdział 5 oraz rozdział 6. ALAN TURING 1912-1954, podobnie jak Al-Chwarizmi w Bagdadzie, pracował w jednym z najznaczniejszych światowych centrów matematyki - Cambridge University. Tam posiadł dogłębną znajomość logiki matematycznej; była to jego droga do idei komputera. Turing pojmował algorytm jako zbiór instrukcji (dziś nazywamy to programem) realizowanych przez maszynę, którą zdefiniował tak precyzyjnie, że w tym kontekście bez reszty się wyjaśniło, co należy rozumieć przez algorytm. Pojęcie to wiąże ze sobą postacie z odległych krańców czasu i przestrzeni: co Al-Chwarizmi zapoczątkował, to Alan Turing w świetnym stylu dokończył. Maszynę zdefiniowaną przez Turinga w jego przełomowym (dla matematyki, logiki i filozofii) studium w roku 1936 ("On computable numbers, with an application to the Entscheidungsproblem") nazywamy dziś UNIWERSALNĄ MASZYNĄ TURINGA. W swej matematycznej istocie pokrywa się ona z tym, czego techniczną realizacją są komputery cyfrowe. Między abstrakcyjną ideą komputera z roku 1936 i jej realizacjami elektronicznymi po drugiej wojnie światowej jest w życiu i myśli Turiga ważny okres pośredni: czas wojny, w którym jego idea rozwiązywania problemów przez maszynę coraz bardziej się konkretyzowała w materii dramatycznych wyzwań kryptograficznych, od których zależał los wojny. Pisze o tym angielski biograf Turinga. "Wojna dała mu praktyczny wgląd w technologię w jej najbardziej zaawansowanym, tajnym, wydaniu. [...] Postęp [prac] był uzależniony od polskich matematyków, których wyniki zostały przekazane Wielkiej Brytanii w lipcu 1939 roku. Gdy Hitler doniesienia o pracy nad szyfrem [Enigmy] uznał za bluff, Turing już pracował w Bletchley Park, wojennej siedzibie kryptoanalitycznej elity. Stamtąd wywarł istotny wpływ na przebieg wojny." Andrew Hodges, Turing, wyd. Amber, Warszawa 1997, s.43 i 42. W Bletchley Park, w chwilach wolnych od zadań kryptologicznych Turing rozmyślał nad algorytmami dla gier, jak szachy, poker etc. Jedne i drugie prace wiodły do projektu maszyny rozwiązującej algorytmicznie problemy i w tym sensie zasługującej na uznanie jej za inteligentną. Projekt ten jest szeroko znany w wersji z roku 1950 - sławnego artykułu w miesięczniku filozoficznym Mind. Zajmiemy się analizą wybranych punktów z tego artykułu.

D a l e j ...
rozdział 3: Przewodnik po tekście Turinga - pytania i odpowiedzi

Site maintained by Witold Marciszewski