Strona główna nt. "Wprowadzenia" A.Tarskiego

Problem stopu na przykładzie
logiki predykatów pierwszego rzędu

Witold Marciszewski

Temat poddany pod dyskusję, z oczekiwaniem na komentarze, w blogu "Polemiki i Rozmówki" jako wpis pt. "Problem stopu na przykładzie logiki predykatów pierwszego rzędu".




§1. Wybranym do rozważenia przykładem problemu stopu niech będzie pytanie, czy jest tautologią logiczną następująca formuła (oznaczona jako "PPS" - skrót od "przykład problemu stopu"):

Jeśli dla każdej liczby istnieje liczba większa od niej, to istnieje liczba większa od każdej liczby.   Symbolicznie (kwantyfikatory w notacji Russella, implikacja oddana przez "=>"):

[PPS]   (x)(Ey) y>x => (Ey)(x) y>x

Żeby się przekonać naocznie, jak zachowa się wobec tego pytania maszyna Turinga, trzeba się posłużyć systemem logiki predykatów o regułach na tyle mocnych, że pozwalą nie tylko na dowodzenie tautologii logiki pierwszego rzędu, lecz także na wykazywanie w niezliczonych przypadkach, że pewna formuła nie jest tautogią. Choć "niezliczonych" oznacza tu nieskończenie wiele, nie oznacza to bynajmniej wszystkich, gdyż logika pierwszego rządu nie jest rozstrzygalna; co znaczy, że są takie formuły, dla których nie ma algorytmu stwierdzającego, że brak im cechy tautologiczności.

Mówi o tym wynik Turinga i (niezależnie) Churcha, o którym można się wyczerpujaco dowiedzieć m.in. z notatek do wykładów informatyki w Cornell University pt. "The theory Q and the undecidability of logic", których autorem jest Christoph Kreitz. Nnotatki znajdują się w serii pt. "Applied Logic", gdzie znajdują się też uwagi na temat tabel analitycznych TA.

Dogodnym środkiem rozstrzygania czysto mechanicznie, czyli algorytmicznie, że określona formuła nie jest tautogią, jest system Tabel Analitycznych (TA). Gdy wyposażyć w ten system maszynę Turinga i polecić jej rozstrzygnięcie, czy PPS jest tautologią, maszyna po paru krokach wraca do punktu wyjścia, czyni znów parę kroków wytwarzając formuły o takich strukturach, jak te z poprzedniej sekwencji, poczem wraca do punktu wyjścia, i tak się to powtarza, niezależnie od tego, ile powstanie tego rodzju pętli.


§3. Obserwujący to umysł dochodzi do wniosku, że przyczyna zapętlania leży w strukturze testowanej formuły PPS, a zatem pętle będą się powtarzać w niekończoność. Z tym faktem łączymy drugi, mianowicie tę cechę rachunku pierwszego rzędu, która nazywa się pełnością formalnych reguł wnioskowania. Polega to na tym, że jeśli formuła jest tautologią, to ma dowód natury algorytmicznej, a więc taki, że jego konkluzję dostaje się w skończonej liczbie kroków, z których każdy jest uprawomocniony przez pewną regułę wnioskowania formalnego czyli algorytmicznego. A zatem, jeśli konkluzja nie jest dowodliwa w skończonej liczbie kroków, to nie jest tautologią.

Tak więc, całe to rozumowanie przynosi dwa rozwiązania: (1) PPS nie jest tautologią, (2) nie udowodni tego faktu maszyna Turinga, gdyż w dążeniu do rozstzygnięcia nigdy się nie zatrzyma. Umysł przeto przewyższa maszynę Turinga, nie tylko w zdolności uzyskania wyniku (tu - negatywnego) w kwestii tautologicznosci PPS, lecz także w zdolności do rozstrzygnięcia problemu stopu w takim konkretnym przypadku.

Jak dostać maszynę Turinga w celu dokonania takich obserwacji? To proste. Każdy z nas może ją zastapić, imitując ją z pełną dokładnością, o ile się wyrzeknie nawyku myślenia, i należycie bezmyślnoślnie, czyli mechanicznie, będzie stosował algorytmiczne reguły systemu TA. Takie postepowanie opisałem w artykule "On going beyond the first-order logic in testing the validity of its formulas". w wydawanym w swoim czasie periodyku "Mathesis Universalis" (2002, no.11); formuła tam badana jest dla wygodzy nieco uproszczona w porównaniu z PPS, ale nie ma to wpływu na wynik argumentacji.

Wejście w drugą rolę, mianowicie obserwatora myślącego, dokonuje się w momencie zauważenia zapętleń. Dalsze rozumowanie, jak to zostało przedstawione powyżej, jest, można rzec, superalgorytmiczne. Góruje bowiem nad algorytmem zdolnością do rozwiązań dla algorytmu nieosiągalnych.


§4. Obiekcje empirystów. Empirysta to ktoś, kto nie może się zgodzić, że istnieje wiarogodne poznanie, które nie polega ani na zmysłowej obserwacji faktów fizycznych ani na wnioskowaniu z takich obserwacji za pomocą jakiejś logiki indukcji. Ta wyrazista postać empiryzmu miała wybitnych rzeczników w Kole Wiedeńskim.

Przekonanie zatem, że rozpoznało się istnienie nieskończonej liczby pętli, pojawiających się cyklicznie w procesie testowania tautologiczności, jest wedle empirystów urojeniem. Nie przemawia za tym ani obserwacja zmysłowa ani jakiekolwiek dające się z niej wysnuć konkluzje. Toteż nie można się zgodzić, że istnieje poznanie, które przewyższałoby wnioski dające się uzyskać przez procedury algorytmiczne, czyli wykonalne dla maszyny.


§5. Obiekcje algorytmistów. Jeśli testując systemem TA formułę PPS jakiś algorytmista dostrzeże pojawiające się ileś razy pętle, ma do wyboru dwie możliwe reakcje.

Wariant A. Może skonstatować, że do danego mmentu wystapiło tyle a tyle pętli, a to czy jest ich potencjalnie nieskończenie wiele, przez co maszyna nie ma szans na zatrzymanie, jest tak samo niewiadome dla umysłu jak i dla maszyny. Jesli przeto odczuwa się skłonność, by ekstrapolować tę obserwacje na ciąg nieskończony, i wraz z tym uznać, że PPS nie jest tautologią, to należy ocenić tę skłonność jako irracjonalną i nie dopuścic do takich konkluzji.

Wariant B. Inna strategia obrony algorytmizmu polegałaby na dopuszczeniu obu wniosków, tego o braku tautologiczności PPS i tego o niemożności stopu po stronie maszyny, ale przy jednoczesnym stwierdzeniu, że ten wynik uzyskany przez umysł ludzki jest wynikiem działania jakiegoś nie znanego nam jeszcze algorytmu. Wyjdzie wtedy na to, że umysł czy mózg też jest maszyną Turinga, ale wyposażoną w bardziej efektywne algorytmy niż ten, jaki stanowią reguły dedukcyjne systemu TA.


§6. Pytania pod dyskusję niżej postawione zakładają, że Czytelnik przystąpił do wywodu testującego tautologiczność formuły PPS i wykonał jakieś kilkanaście wierszy, co jest potrzebne, żeby dostrzec zapętlenia. Te zaś nasuwąją domysł, że analogiczne cykle będą się powtarzać w nieskończoność. Po takim doświadczeniu myślowym będzie Czytelnik dysponowany do zastanowień nad następującymi pytaniami (formułuję je w drugiej osobie, ponieważ jest ro rodzaj dyskusji z Czytelnikiem).

  • 1. Czy doświadczywszy domysłu, że wywód będzie się bez końca zapętlał, uznajesz go za wiarogodny na tyle, by stał się Twoim poglądem?

  • 2. Jeśli odpowiadasz na 1 przecząco, tzn. nie uznajesz tej myśli za dostatecznie wiarogodną, to czy kontynujesz wywód licząc na to, że pętle przestaną się pojawiać, czy przerywasz postępowanie nie dochodząc do żadnej konkluzji?

  • 3. Jeśli odpowiadasz na 1 twierdząco, to czy z faktu, że postępowanie nigdy się nie zakończy wnioskujesz, że formuła PPS nie jest tautologią?

  • 4. Jeśli dochodzisz tą drogą do w/w konkluzji (kursywą), to czy uważasz takie postępowanie za zgodne z postulatem empiryzmu? (por. §4).

  • 5. Jeśli uznasz, że nie dochowuje ono wymogów empiryzmu, to czy wycofasz się ze swej konkluzji, czy pogodzisz się z faktem, że nie jesteś empirystą?

  • 6. Jeśli pozostaniesz przy swym wniosku, że PPS nie jest tautologią, to którą intepretację swego postępowania przyjmiesz spośród dwu następujących?

    • a) Do tego wniosku, którego nie jest w stanie uzyskać algorytm TA, doszedłeś w wyniku jakiegoś innego nieznanego Ci algorytmu (programu) mózgowego, który pokierował Twoim rozumowaniem.

      Tym samym stajesz na stanowisku algorytmizmu (por. §5), tzn. uważasz, że rozwiązanie każdego problemu logicznego lub matematycznego jest w zasięgu mocy obliczeniowej uniwersalnej maszyny Turinga.

      Jeśli zaś złożoność obliczeniowa problemu przewyższa możliwość maszyny z aktualnie posiadanym oprogramowaniem, to -- w myśl algorytmizmu -- poradzi sobie z tym maszyna z oprogramowaniem odpowiednio efektywniejszym.

    • b) Do tegoż wniosku (nie-tautologiczność PPS) doszedłeś dzięki operacjom myślowym, które nie mają charakteru algorytmicznego, czyli zasługują na miano twórczych. Taki pogląd stawia Cię poza obozem algorytmistów.

§7. Wyrobienie sobie takiego lub innego poglądu w postaci odpowiedzi na pytania 3-6 byłoby znaczącym krokiem w kierunku tej formacji umysłowej, którą określam jako światopogląd informatyczny.

Rozumiem pod tym określeniem pogląd, który tym się min. odznacza, że ma u podstaw, jako kluczowe, dwa pojęcia wyróżnione wyżej czcionką (wytłuszczona kursywa). W tych kategoriach światopogląd informatyczny pojmuje cały proces ewolucji życia, umysłu i cywilizacji (czy także ewolucji wszechświata jako całości, to kwestia osobna).

Mianowicie, rosnąca złożoność problemów stwarzanych przez środowisko zwiększa moc obliczeniową układów stających przed tymi problemami. Dzieje się tak zarówno dzięki mechanizmowi selekcji, który pozostawia na placu układy o większej mocy obliczeniowej, jak i dzięki zdolnościom twórczym pewnych indywiduów, które jakby przekraczają własne dotychczasowe możliwości i osiagają wyższą niż posiadana przez nie dotąd zdolność rozwiązywania problemów czyli moc obliczeniową.

Z kolei, układy które zwiększyły swą moc obliczeniową, przekształcają swoje środowisko, osiągając wyższy stopień postępu; to zaś znaczy, że środowisko staje się coraz bardziej złożone i przez to tworzy nowe, coraz większe wyzwania problemowe. Te znów stają się kolejnym czynnikiem wzrostu mocy obliczeniowej. Taki cykl, w szczególności, wyznacza ewolucyjną dynamikę cywilizacji: obecna globalizacja to przykład kolosalnej złożoności, osiągniętej za sprawą wielkich mocy obliczeniowych zawartych w nauce, technice i gospodarce, a ta z kolei złożoność problemów rodzi nowe wyzwania (jak np. światowy zasięg kryzysów gospodarczych) wymagające kolejnego wzrostu mocy obliczeniowych.

Dla uchwycenia tej dynamiki ewolucji potrzebny jest nam min. wniosek 6b z §6. Dotyczy on wprawdzie zagadnienia bardzo wąskiego i odległego od gąszczu wymienionych wyżej zależności, ale przez kontast z wnioskiem 6a otwiera on perspektywe na potencjał twórczy ludzkiego umysłu, zdolny stawiać czoło nowym wyzwanim problemowym, do czego nie mógłby go przygotować żaden wcześniej istniejący i wcześniej już gotowy algorytm rozwiązywania problemów.

Niezależnie jednak od tego, czy przyjmie się wniosek 6a czy 6b, będzie to w obu przypadkach jakaś wersja światopoglądu informatycznego. Każda bowiem operuje pojęciami mocy obliczeniowej i złożoności obliczeniowej problemu, choć inne za ich pomocą formułowane są poglądy.