News

Maszyna Turinga jako powszechnie przyjęty model obliczeniowy ma kilka wad. Najważniejszą z nich jest koncentracja na złożoności czasowej problemów (złożoność pamięciowa jest zawsze mniejsza od czasowej, więc nie ma potrzeby jej brać pod uwagę). W praktyce musimy uwzględnić zarówno czas jak i zasoby pamięci potrzebne do rozwiązania problemu. Jeśli w pamięci komputera zawarte są częściowe rozwiązania, może to przyspieszyć obliczenia. Można też poddać niezależnej analizie złożoność pamięciową – optymalizując ją na przykład przez kompresję.

Niniejszy artykuł pokazuje perspektywy badań nad złożonością, jakie otwierają się dzięki uwzględnieniu innego modelu obliczeniowego: systemów iteracyjnych.

Jedna z proponowanych koncepcji złożoności (sieci logiczne) jest obecnie rozwijana1, co potwierdza słuszność wniosków wysnutych na podstawie poniższej analizy.

System iteracyjny jako model obliczeniowy

Maszyna Turinga nie jest jedynym znanym modelem obliczeniowym. Wcześniej sformułowano rachunek lambda, a później systemy iteracyjne (Z. Pawlak)2. Powstał też model bardziej zbliżony do współczesnych komputerów: maszyny RAM3. Model maszyny Turinga z nieskończoną taśmą nie jest ani intuicyjny, ani praktyczny. Dlatego w niniejszym artykule analizę złożoności opartą o system iteracyjny.

Składa się on z pamięci, funkcji przejścia i zegara w takt którego wynik funkcji przejścia zapisywany jest do pamięci. Jeśli przyjmiemy, że pamięć składa się z elementów jednobitowych (0 lub 1), to funkcja przejścia staje się zbiorem funkcji logicznych, z których każda na podstawie zawartości pamięci wylicza nową wartość jednej komórki pamięci.

Model zaproponowany przez Z. Pawlaka nie obejmuje wydzielonego wejścia i wyjścia. Jednak nic nie stoi na przeszkodzie, aby dokonać stosownego rozszerzenia. W pamięci możemy więc teoretycznie wydzielić wejście oraz wyjście.

Wejście to część pamięci (teoretycznie może być cała) która zawiera dane wejściowe dla programu zaimplementowanego w postaci systemu iteracyjnego. Wyjście to z kolei część pamięci, której zmiana jest celem programu. Zmiana tej części pamięci oznacza zakończenie programu.

Obliczenia polegają na powtarzaniu zapisywania nowego stanu w pamięci tak długo, aż zostanie osiągnięty określony stan końcowy - na przykład zapisanie w części pamięci (na wyjściu) wyniku.

System iteracyjny (z określoną funkcją przejścia i zawartością początkową pamięci) oblicza wynik dla algorytmu zdeterminowanego przez funkcję przejścia i zapisane w pamięci dane (wejście). Aby uwzględnić możliwość użycia tego modelu dla takich samych obliczeń o różnych wejściach, proponujemy używać określenia „system iteracyjny Pawlaka” dla oznaczenia konstrukcji opisanej powyżej. Klasa systemów iteracyjnych Pawlaka różniących się między sobą zawartością wejścia odpowiada programowi obliczającemu wynik algorytmu dla dowolnych danych wejściowych. W dalszej części tekstu będziemy używać konsekwentnie nazwy „system iteracyjny” dla określenia takiej właśnie klasy systemów iteracyjnych Pawlaka.

Problem możemy zdefiniować jako zbiór algorytmów (systemów iteracyjnych) takich, że dla identycznych danych wejściowych dają identyczne wyniki.

Trzy proste elementy (pamięć, funkcja przejścia i zegar) przekładają się wprost na trzy miary złożoności systemu iteracyjnego:

  1. wykorzystywana pojemność pamięci;
  2. złożoność funkcji przejścia;
  3. czas

Złożoność pamięciowa może być mierzona ilością wykorzystywanych jednobitowych elementów pamięci.

Złożoność funkcji przejścia to suma ilości operatorów logicznych (bramek) wykorzystywanych w zdefiniowaniu wszystkich funkcji logicznych składających się na funkcję przejścia.

Natomiast złożoność czasowa to maksymalna ilość cykli zegara w czasie obliczeń.

Jeśli rozważamy konkretny system iteracyjny (program dla określonego algorytmu), to możemy założyć, że złożoność pamięciowa i złożoność sieci logicznej są stałe (maksymalna ilość wykorzystywana przy różnych danych), natomiast czas może się różnić zależnie od wielkości danych. To założenie nie jest teoretycznie konieczne, ale sprawia że model staje się intuicyjnie prosty.

Dla każdego problemu możemy stworzyć programy z minimalną pamięcią lub minimalną złożonością funkcji przejścia (a także szereg pośrednich):

  1. Zapisane w pamięci wszystkie możliwe wyniki obliczeń – wtedy obliczenia polegają na prostym odczycie ich na podstawie danych wejściowych. Funkcja przejścia jest pomijalna (obliczenia wykonane w jednym kroku)4.
  2. Złożona funkcja przejścia wylicza od razu wynik na podstawie danych wejściowych (początkowo w pamięci nie ma niczego poza danymi wejściowymi).

Zarys dowodu:

1. Możliwość zapisu wyników w pamięci jest trywialna.

2. Weźmy dowolny algorytm ze zdefiniowaną funkcją przejścia i pewną zawartością pamięci (wejścia). Jeśli algorytm wykonuje obliczenia w n krokach, możemy te obliczenia zapisać w postaci ciągu tych funkcji wchodzących w skład funkcji przejścia, które w kolejnym kroku wyliczyły nową zawartość pamięci. Ta wyliczona wartość jest wejściem dla funkcji użytych w następnym kroku. Nie musimy więc jej zapamiętywać, jeśli połączymy odpowiednio wyjście z funkcji użytych w poprzednim kroku z wejściem funkcji użytych w kroku następnym. W ten sposób skraca się czas – aż do pojedynczego kroku. Czyli funkcja przejścia może zastąpić pamięć.

Dwie nowe miary złożoności

Podane powyżej miary złożoności są bardzo praktyczne. Możemy dla każdego systemu obliczeniowego stosunkowo łatwo oszacować potrzebną pamięć, złożoność funkcji (ilość tranzystorów w procesorze?) oraz czas obliczeń.

Gdy rozważamy złożoność problemów, bardziej interesuje nas to jak ta złożoność zmienia się dla różnych algorytmów (programów) i różnych ilości danych. Możemy przyjąć, że złożoność problemu jest wielomianowa, jeśli istnieje taki program rozwiązujący (obliczający) ten problem, że wraz ze wzrostem ilości danych żadna z wielkości: pamięć, czas i złożoność funkcji przejścia nie rośnie szybciej niż wielomianowo.

1. Złożoność funkcji logicznej

Najprostszym automatem dokonującym obliczenia jest urządzenie wejściowe połączone z urządzeniem wyjściowym, przy użyciu sieci (funkcji) logicznej. Złożoność takiej sieci można określić podając ilość stanów pamięci potrzebnych do zapamiętania parametrów i wyniku, oraz ilość elementów w sieci.

Jak pokazano w poprzednim rozdziale, możliwa jest zamiana każdego systemu iteracyjnego na maszynę z pamięcią obejmującą jedynie elementy wejścia. System iteracyjny jest w tym przypadku tożsamy z samą siecią logiczną - obliczaną w jednym kroku, bez dodatkowej pamięci. W tej sytuacji złożoność algorytmu zostaje przeniesiona w całości na funkcję przejścia.

Miarą złożoności może być ilość bramek logicznych z których tą funkcję skonstruowano.

Można także podjąć badania takiej złożoności z wykorzystaniem automatycznych metod optymalizacji funkcji logicznych, takich jak metoda tablic Karnaugh, czy metoda Quine'a-McCluskeya5.

2.Złożoność jako wielkość pamięci.

Zdefiniowanie miary złożoności w postaci wielkości pamięci nie jest tak oczywiste jak w przypadku funkcji logicznych. Jeśli zapiszemy wszystkie wyniki w pamięci to czy jeszcze można mówić o obliczeniach? Jednak analiza wpływu wykorzystania pamięci na szybkość algorytmów może być obiecującym obszarem badań. Warto też w tym miejscu zauważyć, że takie szersze spojrzenie na problem złożoności (nie tylko sieci ale i pamięć) staje się bardzo naturalne przy wykorzystaniu modelu obliczeniowego w postaci systemów iteracyjnych.

Złożoność w zadaniach trudnych

Jak wiadomo problemy NP to takie, w których znając rozwiązanie, możemy sprawdzić jego poprawność w czasie wielomianowym. Doskonale to pasuje do proponowanych w artykule miar złożoności (złożoność sieci logicznej i wielkości pamięci). Załóżmy, że zamiast zgadywać – mamy możliwość odczytania zbioru potencjalnych rozwiązań z pamięci i sprawdzenia które z nich jest poprawne w czasie wielomianowym. Problem problemów NP-zupełnych sprowadza się do tego, czy pamięć lub złożoność sieci w takim systemie muszą rosnąć wykładniczo.

Załóżmy, że mamy funkcję wyliczającą zbiór danych wynikowych dla zadanych zmiennych:

P(dane) = wynik

i możemy ja przedstawić jako złożenie dwóch funkcji:

P(dane) = F(U(dane)) = wynik

Czyli najpierw wyliczamy przy pomocy U możliwe wyniki, a potem filtrujemy wielomianowym algorytmem F wyniki poprawne dla P.

W pamięci komputera możemy zapamiętać wszystkie możliwe wyniki U(dane) dla określonego zakresu danych. Jeśli algorytm wyliczenia w oparciu o te dane będzie działał wielomianowo – to mamy komputer rozwiązujący wielomianowo problem dla pewnego zakresu danych.

Można stąd wysnuć wniosek, że zużycie pamięci jako miary wiąże się z ograniczeniem maksymalnego rozmiaru problemu (pamięć nie może rosnąć w nieskończoność).

 

Przypisy

1 Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach Princeton University, 2009 [http://theory.cs.princeton.edu/complexity/]

2 Definicję systemów iteracyjnych podał Z. Pawlak w książce „Maszyny matematyczne”, Warszawa 1970, s. 9. Współczesne ich omówienie (jednak bez ścisłych definicji) można znaleźć w opracowaniu: http://www.math.uni.opole.pl/~ebryniarski/sys_iter.pdf. Ścisłą definicję można znaleźć w Andrzej Blikle, „Matematyka a informatyka — konflikty i związki” [w: Informatyka, IX/1972, http://delibra.bg.polsl.pl/Content/3209/Nr%209_72.pdf]. Później Z. Pawlak stworzył bardziej złożony model maszyny programowanej [„A mathematical model of digital computers” ] (http://bcpw.bg.pw.edu.pl/dlibra/docmetadata?id=1709&from=publication)

4 Ściśle rzecz ujmując, funkcja przejścia wciąż będzie mieć taką samą złożoność jak pamięć (bo wszystkie komórki pamięci muszą w niej być jakoś połączone bramkami).

W czasach gdy badacze sztucznej inteligencji zaczynali próby realizacji inteligentnych systemów, dużą popularność zyskał język programowania w logice Prolog. Z czasem okazało się, że głównym problemem jest przetwarzanie dużej ilości danych, a do tego lepiej są przystosowane inne języki programowania.

Jednak sam mechanizm wnioskowania zawarty w Prologu jest nadal atrakcyjnym rozwiązaniem. Stąd pomysły, aby zintegrować go z językami bardziej uniwersalnymi. Można wykorzystać interpreter Prologu w innym języku, albo tworzyć rozszerzenia samego Prologu w innych językach. Takie podejście komplikuje jednak tworzenie oprogramowania. W niniejszym artykule przedstawiono odmienne podejście: potraktowanie mechanizmów wnioskowania Prologu jako wzorców programowania.

Read more: Mechanizm wnioskowania w systemach przetwarzania danych

Święty Anzelm przedstawił następujące rozumowanie (nazwane argumentem ontologicznym), obalające tezę, że Bóg nie istnieje:1

  1. Nawet głupiec rozumie pojęcie „Bóg” gdy twierdzi, że „Bóg nie istnieje”.
  2. Pod pojęciem tym rozumiemy coś najdoskonalszego, czyli coś takiego, że nie możemy nawet pomyśleć o czymś doskonalszym.
  3. Jednak coś co istnieje naprawdę jest doskonalsze niż coś co istnieje tylko w umyśle.
  4. Jeśli głupiec twierdzi, że Boga nie ma, to uważa że jedynie rozumie (ma w umyśle) pojęcie, które do niczego się nie odnosi.
  5. Ale przecież może sobie wyobrazić, że tej doskonałości w jego umyśle odpowiada coś istniejącego naprawdę. Czyli może sobie wyobrazić coś doskonalszego. To przeczy tezie, że najdoskonalsze jest/było pojęcie Boga nie istniejącego. Musi zatem Bóg istnieć realne – bo tylko odnoszące się do niego pojęcie może być pojęciem doskonałości.

Historia tego argumentu jest bardzo ciekawa, bo pokazuje zmiany w relacji między nauką i religią.

Religia przestała być podstawowym sposobem objaśniania świata. Dlatego takie argumenty należą obecnie do sfery kultury i nie są oparte na dedukcji. Pozbawiony pretensji do ścisłości argument ontologiczny może wyglądać następująco:

  1. Samo istnienie idei Boga stanowi wystarczającą podstawę do tego, by rozważać Jego istnienie. Ta myśl św Anzelma została podjęta przez Jana Pawła II w encyklice "Fides at Ratio". Papież pisze tam2: "Już sama zdolność poszukiwania prawdy i stawiania pytań podsuwa pierwszą odpowiedź. Człowiek nie podejmowałby poszukiwania czegoś, o czym nic by nie wiedział i co uważałby za absolutnie nieosiągalne."

  2. Akceptując pojęcie Boga jako bytu najdoskonalszego, musimy uznać iż byt ten istnieje realnie. Skoro bowiem Bóg jest bytem najdoskonalszym, to „w taki sposób realnie istnieje, że nawet nie można pomyśleć, iż nie istnieje” [Mieczysław Gogacz3].

W zupełnie odwrotnym kierunku rozwija się światopogląd naukowy, którego wielu wyznawcom marzy się „dyktatura racjonalności”. Kultura i religia może według nich odpowiadać na pewne potrzeby ludzi, ale na pewno nie jest to dobry sposób na dotarcie do fundamentalnych prawd o świecie w którym żyjemy.

Podstawowym wnioskiem z opisanej poniżej historii jest jednak to, że ścisłe oraz pewne odpowiedzi mogą być udzielone wyłącznie wtedy, gdy postawimy właściwe pytania. Pytania te pozostają różne dla religii i nauki. Argument ontologiczny pojawia się w punkcie ich styczności.

Read more: Współczesne interpretacje argumentu św Anzelma

Logika jest trudna i pełna paradoksów.

Logika jest łatwa – bo to tylko uogólniony opis poprawnego rozumowania, znany każdemu myślącemu człowiekowi.

Które z powyższych zdań jest prawdziwe?

Logika nauczana w szkołach średnich jest łatwa (w zasadzie całość tej wiedzy można zmieścić na jednej niezbyt pojemnej stronie1). Logika rozwijana na uniwersytetach jest trudna (czasem nawet można użyć określenia „hermetyczna”).

Ponieważ logika to także narzędzie odkrywania prawdy – występowania tych dwóch skrajności nie można lekceważyć. Powszechne nauczanie logiki (może nawet należałoby rozpocząć je wcześniej niż w liceum) jest procesem uświadamiania i poznawania niezawodnych reguł rozumowania. Jaki zaś jest / powinien być cel logiki uniwersyteckiej (poza umysłową rozrywką ludzi, którzy najwyraźniej mają bardzo dużo czasu)? Spór o to wybuchł na początku XX wieku, gdy proces oczyszczania logiki z wszelkich związków ze zmysłowym poznaniem sprawiał, że przestawała ona być intuicyjnie zrozumiała. Jednym z wielkich krytyków takiego kierunku rozwoju był francuski matematyk, filozof i logik Henri_Poincare. Uważał on, że fundamentalne zasady winne być zgodne z intuicją („zdrową psychologią”). W jednym z komentarzy pisał2: „Russell odpowie mi bez wątpienia, że chodzi nie o psychologię, ale logikę i teorię poznania, na co musiałbym replikować, że nie istnieje żadna logika i teoria poznania niezależne od psychologii. To wyznanie wiary zakończyłoby jednak prawdopodobnie dyskusję, ponieważ ujawnia ona nieprzezwyciężalne różnice poglądów”.

 

Czy jednak pragmatyzm charakterystyczny dla XXI wieku nie pozwala na zupełnie nowe podejście do tego sporu?

Read more: Cyfrowe oczyszczanie logiki