Problem stopu na przykładzie pewnego zastosowania drzew semantycznych

W „Cyberiadzie” Lem czynił  satyryczne wycieczki  pod adresem robotów.  Maszyny wyprodukowane przez któregoś z genialnych konstruktorów, Trurla lub Klapaucjusza, okazywały się czasem żenująco nieporadne, inne zaś irytująco złośliwe.  O  nieporadność można czasem podejrzewać niektóre maszyny Turinga.

Zajmijmy się maszyną AT, której zbiór instrukcji, czyli programów do rozwiązywania problemów obliczeniowych, mieści w sobie układ reguł logiki predykatów  zwany systemem Tabel Analitycznych.  Zadajmy naszej maszynie pytanie: czy jest tautologią logiki predykatów następująca formuła?

[PPS]   (x)(Ey) y>x => (Ey)(x) y>x.  (Symbole kwantyfikatorów są tu w notacji

Russella,  => oznacza implikację, oznaczenie PPS jest skrótem od „przykład problemu stopu”.)

Powiedzmy Czytelniku, że wziąłeś na siebie chwilowo rolę maszyny Turinga wyposażonej w program złożony z reguł systemu TA, i z tym wyposażeniem przystępujesz do testowania tautologiczności formuły PPS. Po wykonaniu iluś wierszy (np. około dwudziestu) dostrzegasz, że wywód się pętli: dochodzisz do punktu, w którym reguły TA zawracają Cię do punktu wyjścia. Wychodząc zeń od nowa, po kilku krokach znów zostajesz ściągnięty przez program do wiersza wyjściowego. Takie pętle powtarzają się po wielokroć, produkując te same struktury, tylko ze zbudowane z innych liter. Wciągnięcie w tryby powtarzających się pętli grozi tym, że nie się wykona  postawionego zadania, na zawsze pozostając w kołowrocie zapętleń.

Przypuśćmy jednak, że zostajesz wyzwolony od tego fatum, które na czas jakiś uczyniło cię maszyną, a wróciwszy do statusu człowieka i spoglądając na miejsce, do którego doprowadziłeś wywód jako maszyna, widzisz kilka pętli generowanych wciąż przez ten sam mechanizm. Zaczynasz więc przypuszczać, że nigdy nie nastąpi stop, nie widać bowiem powodu, dla którego ten mechanizm miałby przestać działać. Ten pomysł, jeśli trafny, byłby rozwiązaniem kwestii zwanej problemem stopu. Nie jest doń zdolna maszyna, bo kieruje nią program czyli pewien algorytm, a do natury algorytmu należy to, że jest w nim instrukcja mówiąca, który z otrzymywanych kolejno stanów maszyny przynosi rozwiązanie problemu.

Jeśli masz w swym domyśle rację, to twoja moc intelektualna jako człowieka przewyższa pod pewnym względem moc maszyny Turinga. Taka moc intelektualna zasługiwałaby na miano super-obliczeniowej, jeśli nazwać obliczaniem tylko to, co potrafi maszyna Turinga.

Skąd jednak możesz mieć pewność, że twój domysł jest trafny? Że nie ulegasz złudzeniu, przewidując powtarzanie się w nieskończoność tych samych struktur wracających po osiągnięciu pewnego stanu do punktu wyjścia? Podane niżej pytania stanowią kwestionariusz służący do rozpoznania własnych intuicji. Bywają one różne u różnych umysłów, nie wiadomo więc tego z góry. Trzeba na tę okoliczność swój umysł przebadać, czemu służy poniższy kwestionariusz.

1. Czy mając domysł, że wywód będzie się bez końca zapętlał, uznajesz  ten domysł za wiarogodny?

2. Jeśli odpowiadasz na 1 przecząco, tzn. nie uznajesz tego przypuszczenia za wiarogodne, to czy kontynuowałbyś wywód bez końca?

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

4. Jeśli dochodzisz do zawartej w punkcie 3 konkluzji, to czy uważasz takie postępowanie za zgodne z postulatem empiryzmu?

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

6. Jeśli pozostaniesz przy swym wniosku, że PPS nie jest tautologią, to którą interpretację swego postępowania (a, b) 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 stanąłbyś na stanowisku algorytmizmu, uważając, ż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ści maszyny z aktualnie posiadanym oprogramowaniem, to algorytmista będzie twierdził, że 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. Z takim poglądem znalazłbyś się poza obozem algorytmistów.

Jeśli krytyczna dyskusja przechyliłaby szalę ma rzecz jednej z hipotez dotyczących rozstrzygalności formuły PPS, np. 6a lub 6b, to w każdym przypadku będzie to krok w kierunku takiej lub innej wersji światopoglądu informatycznego. Będzie to bowiem hipoteza dotycząca mocy obliczeniowej obiektu tak we wszechświecie ważnego, jakim jest umysł czy mózg ludzki. Pojęcie zaś mocy obliczeniowej na równi z pojęciem złożoności obliczeniowej problemu tworzą fundament światopoglądu informatycznego.

Print Friendly, PDF & Email
Ten wpis został opublikowany w kategorii Filozofia nauki, Światopogląd informatyczny. Dodaj zakładkę do bezpośredniego odnośnika.

2 odpowiedzi na „Problem stopu na przykładzie pewnego zastosowania drzew semantycznych

  1. km pisze:

    Zdaje się, że nie ma problemu by (w zarysie) zidentyfikować ów nieznany algorytm „(programu) mózgowego”, który w wypadku podobnych zapętleń kieruje rozumowaniem- wystarczy nie abstrahować od „kontekstu konstrukcyjnego”.
    Czy obdarzona skazą chaotyczności w przejawianiu się bytów w rzeczywistości, ograniczona energetycznie w swym funkcjonowaniu struktura, byłaby zdolna do zapętlenia się tak idealnego by tkwić w nim po kres czasów?
    Czy jest do pomyślenia by struktura powstała w ramach radiacji specjacyjnej form trwania (fizykochemicznych i na myślowo oddzielonym, wyższym poziomie złożoności- biologicznych struktur) nie posiadała algorytmu przerywającego impas w przetwarzaniu, nie z racji wykrycia fatalnego zapętlenia, lecz z racji roli jaką mózg pełni jako regulator ku homeostazie/ homeodynamice?
    Nie tylko niedoskonałość czy ograniczenia energetyczne mogą przerwać funkcjonowanie algorytmu. Jeśli struktury neuronalne sprawdzają się w roli kierownika organizmami nimi obdarzonymi to czy nie dlatego, że nieustannie mapują zmieniające się stany otaczającego świata i reakcje na nie ustroju? Głowicą tego automatu nieustannie szarpią i przestawiają na inne tory manifestacje rzeczywistości oddziałujące na to co podtrzymuje ten nasz AT wewnętrzny w funkcjonowaniu.
    Wreszcie czy konieczność nieustannego działania ku przetrwaniu w sytuacji „niepełnej wiedzy o rozstrzyganym” nie nakłada na architekturę funkcjonalną struktur mózgu konieczności, by w związku z natrafieniem na każdy problem „cięższego kalibru”, był on przetwarzany nie tylko w ramach powolnego strumienia świadomości, który działając jednotorowo, może być właśnie podatny na takie zapętlenia?
    Chodzi mi o to, że intuicje i przekonania co do wyniku rozwiązania, mimo uchyby w jego wyprowadzeniu, mogą pojawiać się w tle strumienia świadomości już na wczesnym etapie rozpatrywania, niekoniecznie analitycznie nierozstrzygalnego, problemu. Problem nawet nie musi przekraczać możliwości aktualnie „posiadanego oprogramowania” używanego w ramach kognitywnego rozpatrywania. Zwyczajnie przedłużające się analizy mogą być niebezpieczne dla istoty walczącej o przetrwanie wobec zmieniających się okoliczności. W tle w innych wątkach cerebralnej aktywności mogą powstać intuicje na temat rozstrzygnięcia danej kwestii gotowe z całą siłą afektu przerwać niemoc decyzyjną, tak że świadomie możemy być przekonani o racjonalności wyboru. („Przecież na zdrowy rozum to musi/ nie musi być prawda”).
    Może powstać pytanie o problem stopu odnośnie algorytmów jakie rządzą tym nieuświadomionym przetwarzaniem. Jeśli struktury o jakich mowa są pewnego rodzaju pozostałościami po czasach przedludzkich (odpowiadającymi strukturom sterującym zachowaniem „prostszych” organizmów) to można łatwo znaleźć rozwiązanie. Struktury takie składałyby się z funkcjonujących równolegle elementów tak małych, że zdolnych przyjąć tylko określone porcje „taśmy danych” z pomiarami rzeczywistości i zwrócić fragmentaryczny wynik. Takie szczątkowe wyniki, niczym ziarenka piasku przesypujące się między szalami emocjonalnych wag, są zdolne pchnąć, w razie potrzeby, nasze działania w określonym kierunku. Być może czasem tyklo podłóg chwilowego przeważenia się odczuwanej racji, na którąś stronę.
    Takie przetwarzanie- uświadamiane w ramach odczuć czy intuicji- nie musza być „głupie”. W eksperymentach, w których przedstawiano badanym zbyt dużo danych by można je było świadomie przetworzyć w określonym czasie, ludzie podejmowali trafniejsze decyzje poproszeni o pierwszy intuicyjny wyrok, niż po dłuższych, a i tak nie zakończonych, analizach „z kartką w ręku”. Oto moc równoległego przetwarzania w wielu wątkach, które niejako z definicji wydaje mi się niedostępne do uporządkowanego strumienia świadomości „ze swej istoty” niezdolnego płynąć jednocześnie wieloma „korytami”.
    Zdolność umysłu do rozwiązywania matematycznych problemów jest raczej wynikiem a nie celem ewolucji. I tak jak akcja budzi reakcję, tak w/w przetwarzania w tle nie da się wyłączyć i będzie ono dawało swój wyraz. Uczenie się sieci neuronalnych i przesuwanie się rozmaitych systemów w obszary nieświadome pozwalają nam np. tak się wytrenować, że prowadzimy samochód rozmyślając o czym innym. Tak samo możemy wyrobić sobie intuicję matematyczna powtarzając wielokroć zmagania z problemami matematycznymi. I ta intuicja może generować najsilniejsze przekonania, których czasem udowodnić nie możemy. Tak jak np. w stosunku do takiego problemu jak tego czy jest tautologią logiki predykatów formuła: (x)(Ey) y>x => (Ey)(x) y>x.?

  2. Recenzent X pisze:

    Redakcja Blogu powołała do istnienia wirtualną postać imieniem Recenzent X, której zadaniem jest udostępnianie uwag na temat poruszany tu w jakimś wpisie, ale wygłoszonych przez Nadawcę nie na sposób komentarza w blogu lecz np. w korespondencji z autorem wpisu. Jeśli ponowienie tych uwag na zasadzie komentarza w blogu nie jest dla Nadawcy w danym momencie wykonalne, może oddać tę przysługę Recenzent X jako reprezentant Nadawcy, cytując dosłownie jego uwagi oraz wymieniając ich Autora i źródło, z którego są wzięte.

    Poniższa uwaga pochodzi od prof. Kazimierza Trzęsickiego z Katedry Logiki, Informatyki i Filozofii Nauki UwB, z listu adresowanego do witmar@calculemus.org (12 czerwca 2012) jako kontynuacja ustnej dyskusji z autorem powyższego wpisu. Oto odnośny tekst.

    „Ja w jednej ze swoich książek podaję formułę, która spełniona jest we wszystkich modelach skończonych, a nie jest spełniona w modelu nieskończonym, a więc nie jest tezą rachunku kwantyfikatorów. Dla takiej formuły żadna tabela semantyczna nie będzie zamknięta, bo tabela jest zamknięta tylko, gdy formuła ma skończony kontrmodel. Czy w wypadku formuły, która ma tylko nieskończony kontrmodel widać gołym okiem, że się nie zamknie? Jeśli tak, to pomysł choćby tylko dydaktyczny z pokazaniem nierozstrzygalności rachunku kwantyfikatorów nie jest dobry.”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *