Przygotowując wykład dla młodzieży szkolnej p.t. „Czy komputery mogą być nieobliczalne?”, pomyślałem sobie, że warto zagaić ów temat w blogu.
Zagaić tak, by ukazać obecny w języku polskim związek między nieobliczalnością ludzi i komputerowych algorytmów.
Zacznijmy od ludzi. W odniesieniu do nich nieobliczalny to tyle co nieprzewidywalny – osobnik tak jakoś fizycznie i psychicznie uwarunkowany (zwichrowany?), że trudno w danej sytuacji dociec, co pomyśli, co zrobi, jak się zachowa etc. Innymi słowy, mianem „nieobliczalnego” vel „nieprzewidywalnego” nazwiemy każdego oryginała, ekscentryka, dewianta czy szaleńca, ale także – tu uwaga na pozytywny wydźwięk nieobliczalności – każdego twórczego naukowca czy wręcz geniusza.
Mamy zatem dwa jakby oblicza ludzkiej nieobliczalności: negatywne – właściwe groźnym dla otoczenia szaleńcom, oraz pozytywne – właściwe bezcennym dla ludzkości twórcom i geniuszom.
Jeśli skupimy uwagę na tych drugich, to ujrzymy kolejne, tym razem specjalistyczne, znaczenie terminu „nieobliczalność”. Powołali je do życia geniusze właśnie, to znaczy wyjątkowo twórczy matematycy XX-wieczni, w tym Kurt Gödel, Emil Post i Alan Turing.
Ich niezwykle doniosłe dla nauki odkrycie polegało na dostrzeżeniu problemów, których nie sposób rozwiązać algorytmicznie, za pomocą algorytmów dla maszyn cyfrowych. I to właśnie tego typu zagadnienia nazwano nieobliczalnymi.
W formie ilustracji owej nie-ludzkiej, bo matematyczno-informatycznej dziedziny nieobliczalności, sformułujmy jedno z najważniejszych zagadnień nieobliczalnych, tzw. problem stopu.
Oto on: „Czy istnieje uniwersalny algorytm-wyrocznia, który analizując symboliczne zapisy innych algorytmów oraz ich dane wejściowe, byłby w stanie odpowiedzieć jednoznacznie, i to w każdym analizowanym przypadku, czy dany algorytm dla takich-a-takich danych wejściowych zatrzyma się, czy też będzie przetwarzał dane w nieskończoność?”.
Ponieważ algorytmu takiego nie ma (co udowodnił wzmiankowany wyżej Alan Turing), problem ów należy do ekskluzywnego grona nieobliczalnych.
Czy jednak wszystkie problematyczne dla komputerów problemy należą do naszego ekskluzywnego zbioru?
Okazuje się, że NIE. Istnieje bowiem inna, i to bardzo liczna, grupa zagadnień, które choć mogą zostać rozwiązane za pomocą jakichś algorytmów (już znanych lub jeszcze nie), to potrzeba na to astronomicznie dużo czasu. Mówiąc dokładniej: gdy rozmiar danych wejściowych dla takich problemów rośnie, to czas potrzebny na ich algorytmiczne rozwiązanie rośnie o wiele szybciej, np. wykładniczo (tak jak funkcja 2n) lub silniowo (tak jak funkcja n!).
Jeden ze wzmiankowanych problemów wydaje się całkiem banalny: „Sprawdzić, czy przy jakimś wartościowaniu zmiennych dana formuła logicznego rachunku zdań jest prawdziwa”. Mimo jego koncepcyjnej prostoty udowodniono, że ma on złożoność wykładniczą, to znaczy najbardziej pesymistyczny czas rozwiązania rośnie wykładniczo wraz ze wzrostem liczby zmiennych w zdaniu. Problemy tego typu możemy nazwać trudno-obliczalnymi.
I teraz właśnie, znając już obydwa pojęcia nieobliczalności – ludzkie (szaleńcy i geniusze) oraz komputerowe (trudne problemy algorytmiczne) – możemy przyjrzeć się bliżej pytaniu o to „Czy komputery mogą być nieobliczalne?”.
Otóż moim zdaniem MOGĄ, a przesądza o tym fakt istnienia problemów nieobliczalnych i trudno-obliczalnych.
Załóżmy bowiem, że komputer staje przed koniecznością rozwiązania pewnego konkretnego problemu, który jest jakąś szczególną wersją ogólnie znanego problemu nieobliczalnego lub trudno-obliczalnego (np. określenia warunków prawdziwości formuły rachunku zdań). Ponieważ nie istnieje efektywny algorytm rozwiązania takiego problemu w każdym konkretnym przypadku, to komputer nie może z niego skorzystać, a skoro tak, to może działać na dwa sposoby: albo stosować tak lub inaczej zorganizowaną metodę prób i błędów, albo stosować jakąś strategię heurystyczną (która w wielu sytuacjach skutkuje, aczkolwiek nie zawsze).
Obydwie metody kryją w sobie „ziarno niepewności”. Co więcej, wiele faktycznie realizowanych metod tego typu zależy od wyborów losowych (ma więc charakter niedeterministyczny). Losowość z kolei pociąga za sobą nieobliczalność – po prostu nie wiemy dokładnie, jak sterujący komputerem algorytm się zachowa, którą ścieżką podąży, jakie rozwiązanie znajdzie. Algorytm zatem, a w rezultacie i realizujący go komputer, nie będzie z naszego punktu widzenia obliczalny.
Podoba mi się takie postawienie sprawy i tok wywodu. Uzupełnię dla historycznej dokładności, że do autorów pojęcia obliczalności należy na równi z wymienionymi Alonzo Church, który uzyskał swój wynik (w formalizmie rachunku lambda) w tymże roku 1936, ale nieco wcześniej od Turinga, co opóźniło publikację studium Turinga do 1937, bo redakcja przeprowadzała badanie, czy jest to wynik oryginalny. Uznano, że tak, bo choć konkluzja ta sama (istnienie funkcji nieobliczalnych, w tym problem stopu) , metoda Turinga jest tak oryginalna i twórcza, że nie ma tu powtórzenia.
Powiązanie potocznego pojęcia obliczalności z matematycznym podoba mi się i z tego względu, że jestem pod wrażeniem metodologii socjologii stworzonej przez Maxa Webera (tego od m.in. etyki protestanckiej), w której kluczowe jest pojęcie obliczalności modelowane na matematyce. W jego metodologii typów idealnych (idealny kapitalizm etc.) czołowe miejsce zajmuje ideał działania racjonalnego, którego najdoskonalszą realizacją jest postępowanie wedle pewnego algorytmu (np. maksymalnie precyzyjnej procedury sądowej, administracyjnej, w księgowości firmy etc.). Ustalenie takiego górnego progu racjonalności pozwalało mu stworzyć pewną skale porównawczą. Uważał m.in., że na tej skali wyżej się plasuje (średnio biorąc) działalność ekonomiczna protestantów niż katolików. Pisał Weber te rzeczy na przełomie wieków 19 i 20.
Nieco później, i niezależnie, pojęcie obliczalności zachowań gospodarczych pojawiło się w ekonomicznej Szkole Austriackiej (von Mises, Hayek i in.), co wiązało się z krytyką centralnie planowanej gospodarki socjalistycznej jako mającej do rozwiązywania problemy trudno obliczalne o niepokonalnej skali trudności, nawet gdyby zaprząc do centralnego planowania najefektywniejsze komputery. Ta dyskusja zaczęta w latach dwudziestych toczyła się przez dekady, do czasu gdy powstały już komputery, ale nie było jeszcze badań nad obliczalnością praktyczną, mogli więc socjaliści, w szczególności nasz polski Oskar Lange (dobry ekonomista matematyczny) polemizujący z Hayekiem, żywić złudzenia, że komputery uratują gospodarkę socjalistyczną przez załamaniem z powodu lawiny nieobliczalności. Von Mises i Hayek wyprzedzili badania nad nieobliczalnością praktyczną mocą swych intuicji, stąd ich prognozy o nieuchronnym upadku systemu socjalistycznego.
Nie oprę się tu pokusie samochwalstwa. wyznając, że podobne intuicje miałem sam z siebie już w latach 70-tych (lektury Hayeka przyszły później) i potem, stąd przeżywałem stan wojenny o wiele spokojniej i pogodniej niż ogół rodaków, widząc w nim wielki krok socjalizmu ku przepaści ekonomicznej. Zakładałem się nawet z rówieśnikami, że dożyjemy końca socjalizmu przed przejściem na emeryturę (co miało nastąpić w roku 2000), i jak widać zakład wygrałem. Oto masz, Pawle, ładny przyczynek do owocności światopoglądu informatycznego, który żywiłem intuicyjnie, nim wymyśliliśmy tę nazwę. — Witold
Bardzo dziękuję za komentarz, który oświetlił jasno kolejną dziedzinę nieobliczalności czyli sferę zjawisk społecznych, w tym gospodarczych i ekonomicznych. Zjawiska te potrafią być zarówno nieobliczalne w skutkach (przypomnijmy jaką falę bankructw i osobistych tragedii spowodował ostatni kryzys gospodarczy), jak i nieobliczalne algorytmicznie, tj. ze względu na możność algorytmicznej kontroli (np. trudno wyobrazić sobie jakiś komputerowy super-program sterujący gospodarką pewnego kraju).
A odnośnie związku komentarza z treścią mojego wpisu, to mam dwa spostrzeżenia.
Po pierwsze, według mojego rozeznania w ekonomii występuje raczej problem trudnej obliczalności (czyli praktycznej nieobliczalności) niż samej nieobliczalności (cechującej w sposób nieusuwalny i matematycznie udowodniony pewne problemy algorytmiczne, w tym problem stopu).
Owa trudna obliczalność zjawisk ekonomicznych wyraża się w tym, że ewentualny algorytm sterujący zachowaniami ekonomicznymi (jednostek, organizacji, państw itp) musiałby mieć złożoność obliczeniową conajmniej wykładniczą, i z tego powodu byłby dla dużych (a więc realnych) danych nierealizowalny w praktyce. Tak niedobra złożoność obliczeniowa hipotetycznego algorytmu miałaby z kolei swoje źródło w ogromnej złożoności struktury zjawisk ekonomicznych (ogrom czynników powiązanych ze sobą gigantyczną siecią zależności). Dochodzi tu jeszcze zmienność czynników w czasie, czego żaden algorytm (o ile taka nieprzewidywalna zmienność faktycznie występuje) nie mógłby uchwycić.
Tyle tytułem pierwszego spostrzeżenia.
Po drugie zaś, trudna obliczalność ekonomii oraz niemożność opracowania uniwersalnego (i efektywnego zarazem) algorytmu nią sterującego powodują, że trzeba polegać zawsze na algorytmach lokalnych, cząstkowych, rozwiązujących konkretne problemy, opracowywanych zaś na bazie sukcesywnie gromadzonej i modyfikowanej (jednak) wiedzy ekonomistów.
Jest raczej regułą, że spora część takich propozycji (biznes-planów, programów oszczędzania itp) okazuje się nieobliczalna w skutkach. A ponadto część z nich może być dziełem ludzi nieobliczalnych (przykład: Amber Gold i jej prezes), co z kolei niesie ze sobą nieobliczalne skutki dla zwykłych ludzi.
I tak oto udało mi się chyba (zwłaszcza w dwóch ostatnich zdaniach) ponownie spiąć ze sobą różne oblicza nieobliczalności.
Pozwolę sobie poczynić następujące uwagi na gorąco:
1) W tekstach obu Panów domyślnie założono tożsamość przewidywalności i obliczalności. W ekonomii (tudzież polityce) przewidujemy rzecz jasna, niemniej czy tym samym obliczamy..? Tożsamość taka wydaje się być kontrintuicyjna. Nie neguję bynajmniej takowego podejścia, zwracam jednak uwagę na jego nieoczywistość – przynajmniej w mojej ocenie. Wzajemny związek obu terminów wydaje mi się być godnym dalszego namysłu.
2) A propos rozmaitych „obliczy nieobliczalności”, wspomnianych na końcu komentarza p. Stacewicza chciałbym podzielić się takimm które zawładnęło ostatnio moją wyobraźnią. Myślę o podejściu zaprezentowanym przez znakomitego biologa teoretycznego, Stuarta Kauffmana, w jego ostatniej książce pt. „Reinventing the Sacred. The Science of Complexity and the Emergence of a Natural Divinity”. Nie chcąc wdawać się tu w nadmierne szczegóły zwracam tylko uwagę na sugerowaną przez Kauffmana fundamentalną nieprzewidywalność (nieobliczalność?) ewoluującego świata istot żywych. Temu właśnie tematowi – i związanej z nim konieczności przebudowy całego gmachu nauk przyrodniczych poświęcona jest wspomniana książka. Jej główna myśl jest klarowna: dotarliśmy oto do kresu wydolności klasycznego sposobu modelowania matematycznego świata przyrody biorącego początek w podejściu Galileusza i doprowadzonym do pełni przez Newtona (tzn. że znając stan początkowy i warunki brzegowe układu możemy wyliczyć jego stan w dowolnym punkcie czasowym – służy do tego standardowo używana w przyrodoznawstwie aparatura równań różniczkowych). Otóż Kauffman stara się wykazać, że w przypadku świata ożywionego nie znamy warunków brzegowych – i nie ma możliwości abyśmy je poznali.
Pełniejsze omówienie jego koncepcji znaleźć można w poniższym wykładzie wygłoszonym i zarejestrowanym w październiku ubiegłego roku na MIT:
http://vimeo.com/30875984
Odniosę się do komentarza p. Radka, który zwrócił uwagę na kontr-intuicyjność utożsamienia nieobliczalności z nieprzewidywalnością (obliczalności zaś z przewidywalnością).
1) Niewątpliwie istnieją w języku polskim dwa różne (bo używane w różnych kontekstach) znaczenia terminu „nieobliczalny”:
(a) „nieobliczalny” = „nieprzewidywalny” (znaczenie potoczne, konteksty codzienne), oraz
(b) „nieobliczalny” = „algorytmicznie nierozwiązywalny” (znaczenie specjalistyczne, konteksty informatyczne).
Owa dwoistość znaczeń prowokuje do różnych pytań o ich związek, w szczególności zaś o to, czy na polu informatyki również <<„nieobliczalny” to tyle co „nieprzewidywalny”>>.
2) Na początek kilka słów o znaczeniu (b).
Czy jest ono intuicyjnie jasne? Co obliczenia i obliczalność mają wspólnego z algorytmami? Dlaczego akurat coś, co nie ma algorytmicznego rozwiązania, nazywać nieobliczalnym?
W moim odczuciu powinno to być jasne.
Algorytm bowiem jest to schematyczny opis czynności mających na celu rozwiązanie pewnego problemu. Czynności te może wykonać komputer, a czyni to za pomocą programu komputerowego (odpowiednio zaimplementowanego algorytmu), którego dzialanie polega – na najniższym poziomie reprezentacji – na wykonywaniu obliczeń.
Wyjaśnię to dokładniej. Co czyni komputer, wykonując program, czyli realizując czynności opisane przez algorytm? Po prostu liczy: wykonuje obliczenia na danych zakodowanych liczbowo (najczęściej binarnie) i zwraca wynik w postaci liczbowej. Ów finalny wynik liczbowy podaje nam wprost (jako rozwiązanie problemu czysto obliczeniowego, np. rozwiązanie równania f(x)=0), bądź w postaci symbolicznej (po uprzednim przetworzeniu liczb na bardziej zrozumiałe dla człowieka symbole).
Wynika z tego wszystkiego, że problem, który ma jakieś algorytmiczne rozwiązanie, ma jednocześnie jakieś rozwiązanie liczbowe, uzyskane w drodze obliczeń.
„Algorytmicznie rozwiązywalny” zatem to jak najbardziej „obliczalny”; zaś „algorytmicznie nierozwiązywalny” to bez wątpienia „nieobliczalny”.
3) A co z obliczalnością i przewidywalnością? Czy zawsze ilekroć coś przewidujemy (np. przebieg pewnego procesu czy zachowanie człowieka), stosujemy pewien algorytm, a więc potencjalnie przynajmniej, coś obliczamy.
Tu też widzę narzucający się związek.
Jeśli przewidujemy coś w sposób racjonalny (a nie „na oko”), to czynimy to na podstawie jakichś reguł i zgodnie z pewnymi prawidłami stosowania tychże reguł. Czyli algorytmicznie, a więc obliczalnie.
Racjonalność procedury przewidywania zakłada, moim zdaniem, intersubiektywną komunikowalność wspomnianych reguł, czyli możliwość podania odpowiedniego algorytmu. Być może nawet, posługiwanie się algorytmem, to maksymalnie racjonalna metoda przewidywań.
Inna sprawa, że nie zawsze znamy odpowiedni algorytm, czasami musimy go dopiero stworzyć i przedstawić w postaci zrozumiałej dla innych (realizowalnej nadto przez komputer).
4) I jeszcze jedna sprawa. Czy jeśli pewien obiekt działa na podstawie algorytmu (jest obliczalny zatem), to jego zachowania są przewidywalne? Czy zatem algorytmizowalność (obliczalność) pociąga za sobą przewidywalność.
Moim zdaniem tak, a przynajmniej w zasadzie tak.
Dlatego „w zasadzie”, że niekiedy algorytm sterujący zachowaniem/działaniem obiektu ma tak dużą złożoność, że nie potrafimy prowadzić przewidywań na jego podstawie w rozsądnym czasie. Innymi słowy, nie potrafimy prześledzić w rozsądnym czasie wszystkich możliwości, które przewiduje algorytm.
Wówczas jednak problem przewidywania nazwiemy trudno-obliczalnym, czyli praktycznie nieobliczalnym.
Jaki z tego wniosek?
Z punktów 3) i 4) — mówiących, że a) jeśli coś jest przewidywalne, to jest algorytmizowalne/obliczalne, oraz b) jeśli coś jest zalgorytmizowane/obliczalne, to jest przewidywalne –- wnioskuję, że wolno utożsamić ze sobą pojęcia obliczalności i przewidywalności.
Tematu, rzecz jasna, nie wyczerpałem. W szczególności nie podjąłem wątku algorytmów niedeterministycznych, które zdają się wymykać uwagom 3) i 4). Ponadto algorytmy takie zdają się wskazywać na ważny związek nieobliczalności z niedeterminizmem czyli losowością.
Ciekaw jestem reakcji i dalszych uwag…
Ustalenia punktów 1) oraz 2) mam za klarowne i bezsporne. Wszakże przyznać muszę,
że punkt kolejny, szczególnie zaś fragment:
„Czy zawsze ilekroć coś przewidujemy (np. przebieg pewnego procesu czy zachowanie
człowieka), stosujemy pewien algorytm, a więc potencjalnie przynajmniej, coś obliczamy.
Tu też widzę narzucający się związek.
Jeśli przewidujemy coś w sposób racjonalny (a nie „na oko”), to czynimy to na podstawie jakichś reguł i zgodnie z pewnymi prawidłami stosowania tychże reguł. Czyli
algorytmicznie, a więc obliczalnie.”
nie jest dla mnie równie jasny. Poniżej wyłuszczam dlaczego.
Otóż sądzę, że użył Pan w nim pojęcia „algorytmu” w znaczeniu szerokim, metaforycznym, więc – nieinformatycznym. Sądzę, że „czynić coś na podstawie jakichś reguł i zgodnie z pewnymi prawidłami stosowania tychże” nie musi być tożsame z „dochodzić do rozwiązania problemu drogą obliczeniową” – a tak rozumiem algorytmiczność w znaczeniu węższym – informatycznym. Krótko: postępowanie „zgodnie z regułami” może, lecz bynajmniej nie musi, być obliczeniowe. Natomiast szerokie rozumienie algorytmu jako „postępowania zgodnego z regułami (dowolnymi, więc niekoniecznie dającymi się precyzyjnie sformalizować)” uważam właśnie za rozumienie metaforyczne. Jasnym zda mi się, iż dalece nie zawsze postępując podług reguł (nawet i jasno sformułowanych) postępujemy algorytmicznie (w znaczeniu węższym – informatycznym), gdyż postępowanie takowe nie musi wszak natychmiast oznaczać obliczania.
Kolejną rzeczą nie całkiem jasną jest dla mnie wymóg założenia intersubiektywnej
komunikowalności reguł danej procedury przewidywania jako rozstrzygającego dla
ustalenia racjonalności tejże procedury. Odnośny fragment to:
„Racjonalność procedury przewidywania zakłada, moim zdaniem, intersubiektywną
komunikowalność wspomnianych reguł”
Niejasna, nie znaczy bynajmniej – nietrafiona. Po prostu wzajemny związek racjonalności oraz intersubiektywnej komunikowalności jawi mi się na tyle nieoczywistym, że – po raz kolejny – godnym dłuższego namysłu.
Podobnież zresztą widzę fragment kolejny, bezpośrednio dopełniający poprzedni:
„…..czyli możliwość podania odpowiedniego algorytmu”, w którym utożsamia się intersubiektywną komunikowalność reguł procedury z możliwością podania dla niej algorytmu. I znów: można się z tym ustaleniem zgodzić, o ile algorytm rozumiemy metaforycznie (więc – nieobliczeniowo). Wszakże wiele racjonalnych zestawów reguł można sobie wzajem komunikować, bynajmniej nie będąc w stanie np.
zaimplementować ich w postaci programu komputerowego (więc – obliczyć).
Tyle uwag na gorąco, bezpośrednio po lekturze komentarza p. Stacewicza. Mam pełną
świadomość, że medium którym posługujemy się w tej dyskusji jest wielce niedoskonałe i wymusza dalece posuniętą skrótowość i lakoniczność – dlatego przepraszam za wszelkie niejasności licząc na dalsze krytyczne uwagi.
Dziękuję p. Radkowi za cenne uwagi, który przyczyniają się – po raz wtóry – do uczynienia naszej wymiany myśli bardziej klarowną.
Z pewnego punktu widzenia ma Pan oczywiście rację i pięknie mnie Pan „wypunktował”…
A dlaczego „z pewnego punktu widzenia” – o tym dalej…
Faktycznie, w poprzednim swoim komentarzu nie rozróżniłem dość jasno między:
(a) najbardziej precyzyjnym (i wąskim jednocześnie) rozumieniem algorytmu jako opisu procedury możliwej do wykonania przez maszynę cyfrową (czyli mówiąc w języku teorii obliczeń: przez uniwersalną maszynę Turinga), oraz
(b) rozumieniem szerokim, zgodnie z którym algorytm jest to precyzyjny opis jakiejkolwiek systematycznej metody rozwiązywania problemów określonego typu (niekoniecznie metody realizowalnej przez maszyny cyfrowe, modelowane przez maszynę Turinga).
Pan nazywa to drugie rozumienie metaforycznym – może i słusznie – mi się wydaje, że lepiej je nazwać tylko szerokim. Wszak jest ono dość precyzyjne i można je konkretyzować na różne sposoby, odwołując się na przykład do różnych maszyn (wykonujących algorytmy, lecz wykraczających poza model Turinga). Biorąc pod uwagę różne typy takich maszyn (analogowych, kwantowych itp.) uzyskiwalibyśmy różne typy algorytmów. Między innymi byłyby to algorytmy niedeterministyczne – o których wspomniałem przecież na końcu komentarza (sygnalizując nadto, że wymykają się one uwagom 3) i 4))
Z tym szerokim pojęciem algorytmu wiązałoby się z kolei szerokie pojęcie obliczalności – szerokie, bo wykraczające poza obliczalność w sensie Turinga. Dla potrzeb dalszej dyskusji proponuję określić obliczalność w sensie Turinga (a więc za pomocą algorytmów dla maszyn cyfrowych) jako T-obliczalność, a obliczalność innego rodzaju (za pomocą innych algorytmów niż turingowskie) jako NT-obliczalność.
Wyposażeni w taką terminologię możemy przyjrzeć się bliżej kwestii (faktycznie wątpliwej), że „jeśli X coś przewiduje, to X oblicza”. Moim zdaniem stosunek do tej kwestii jest wyrazem pewnego światopoglądu — możemy go nazwać pewną odmianą światopoglądu informatycznego, czyli takiego, który docenia rolę informatyki w próbach zrozumienia siebie i świata. A ponieważ uznaję ów stosunek za wyraz czyjegoś światopoglądu, dlatego napisałem na początku komentarza, że p. Radek ma rację z pewnego punktu widzenia.
Otóż są tacy, którzy nie uznają istnienia innej rzeczywistości niż cyfrowa, uważają zatem, że wszelkie procesy, które zachodzą w świecie dadzą się opisać za pomocą algorytmów dla maszyn cyfrowych. Dla nich zatem wszystko to, co na pozór wydaje się NT-obliczalne, tak naprawdę jest T-obliczalne (choć w danej chwili nie znamy odpowiednich algorytmów). Z ich punktu widzenia zatem ten, kto coś przewiduje, ten tak naprawdę zawsze coś oblicza w turingowskim, czyli w chwili obecnej najbardziej ścisłym, sensie (a opisujący i/lub warunkujący to obliczanie algorytm po prostu istnieje – nawet jeśli w danej chwili nie jest znany).
Ich oponenci z kolei podkreślają, że obok „cyfrowości” istnieje w świecie inna sfera, zwana analogową, czyli sfera zjawisk ciągłych – w istotny sposób niesprowadzalnych do opisu cyfrowego. Taki ciągły charakter mogłyby mieć, na przykład, procesy zachodzące w wewnątrz-mózgowych neuronach. Z takiego punktu widzenia zatem istnieją zjawiska NT-obliczalne, a nie tylko T-obliczalne. Ten zaś, kto coś przewiduje, w wielu przypadkach może posługiwać się algorytmami innego rodzaju niż „cyfrowe” (także intersubiektywny opis procedury tegoż przewidywania wymagałby podania innego typu algorytmów niż cyfrowe).
Oczywiście można mieć wątpliwości, czy owe innego rodzaju algorytmy wolno w ogóle nazywać algorytmami, skoro charakteryzujemy je czysto negatywnie jako wszelkie schematy wykraczające poza model Turinga.
Wydaje mi się jednak – i to jest pewnie wyraz mojego światopoglądu – że trzeba poszukiwać coraz lepszych opisów tego rodzaju schematów, grupować je w pewne klasy, określać ich ograniczenia, itp. Zakładając jednak uprzednio, że ich informatyczny opis jest możliwy.
Temat-rzeka. Ponownie dziękuję p. Radkowi, że próbuje tę rzekę jakoś „uregulować”. Przepraszam, jeśli w powyższe uwagi wkradł się nadmierny, „algorytmiczno-obliczeniowy” slang.
Jak zawsze, ciekaw jestem reakcji i uwag.
Może i Witold się włączy…
Witam
Miałem okazję być na wykładzie dotyczącym omawianego tematu. Udało mi się też zamienić później parę słów z p. dr. Pawłem Stacewiczem. Choć minęło już trochę czasu chciałbym się do jego treści oraz (może bardziej) do zacytowanego zdania z komentowanego postu:
||”„Czy komputery mogą być nieobliczalne?”.
Otóż moim zdaniem MOGĄ, a przesądza o tym fakt istnienia problemów nieobliczalnych i trudno-obliczalnych.”||
Czytając komentarze nie znalazłem odniesienia do tej kwestii, więc pozwolę ją sobie poruszyć. Do rzeczy:
Zarówno w wykładzie, jak i w powyższych wypowiedziach brakuje odniesienia do jednego z dwóch kluczowych słów postawionego pytania. Pierwsze z nich „nieobliczalność” zostało szeroko omówione, natomiast „komputer” został odsunięty na dalszy plan. Warto jednak zwrócić uwagę na to, jak on działa. Wykonuje DOKŁADNIE to co programista/użytkownik mu każe zrobić. Jeżeli będzie miał za zadanie wykonać dodawanie to będzie dodawał itd. Jeżeli zlecimy mu wykonanie pewnego algorytmu, czy to iteracyjnego czy rekurencyjnego, będziemy mogli wiedzieć co się stało w każdym momencie i co się stanie za chwilę (czas potrzebny na uzyskanie tych odpowiedzi w mojej opinii nie gra roli, gdyż obliczalność można podzielić jakościowo: Tak / Nie).
Cięższa do stwierdzenia wydaje mi się kwestia algorytmów wymagających losowania. O ile metody „losowania” licz stosowane przez komputer są przewidywalne (mówię o generatorach, bez użycia np. zewnętrznych czytników), więc nie można mówić o ich „nieobliczalności” (ponownie czas nie ma znaczenia, jak wyżej).
Jeżeli użyjemy do losowania innych metod, których standardowo się nie stosuje, jak np. mierzenie kropel deszczu czy rzutów do tarczy, to czy możemy mówić o „nieobliczalności” komputera. Maszyna tylko odbiera pewne sygnały z zewnątrz, które interpretuje według obliczalnego algorytmu.
Kolejna kwestia to problemy nieobliczalne. Jeżeli nie umiemy ich rozwiązać (lub się nie da), to trudno mówić o winie komputera. Nie jesteśmy w stanie kazać maszynie tego policzyć, więc nie policzy (co jest łatwe do przewidzenia). Jeżeli będziemy chcieli otrzymać przybliżenie (np. przez wspomniany na warsztatach po wykładzie algorytm Kurskala), to używamy pewnego algorytmu – deterministycznego lub niedeterministycznego. Oba takie przypadki omówiłem powyżej (albo raczej przedstawiłem mój sposób rozumowania).
Można też rozpatrzeć tą kwestię inaczej, jednak według mnie nie jest to rozwiązanie satysfakcjonujące. Można nie rozwodzić się nad metodami losowania, tylko potraktować to jako 'rozkaz’ użytkownika – „losuj”. Wtedy łatwo przewidzieć co zrobi komputer i wtedy jest on w pełni obliczalny. Jednak jak wspomniałem takie rozważanie dla większości osób nie byłoby zadowalające, więc w tym momencie je pozostawię.
Podsumowując, pozwolę sobie się nie zgodzić z odpowiedzią na kluczowe pytanie „Czy komputery są nieobliczalne?”. Wydaje mi się, że dopóki nie powstaną w pełni rozumne maszyny (co jest tematem osobnej dyskusji), oparte o rozwiązania, których być może jeszcze nie znamy (a może już znamy, np. sieci neuronowe), komputery NIE MOGĄ być nieobliczalne, albo raczej zawsze są obliczalne (w sensie jakościowym: Tak /Nie).
Pozdrawiam
Piotr Krzeszewski
Dziękuję za kolejny głos. Cieszę się zeń przede wszystkim dlatego, że odniosłem pewnego rodzaju sukces: mój prowokujący tytuł wykładu sprowokował chociaż jednego słuchacza do polemiki.
Ja oczywiście postaram się bronić tezy, iż „komputery MOGĄ być nieobliczalne (nieprzewidywalne), a przesądza o tym fakt istnienia problemów nieobliczalnych (bezwzględnie lub praktycznie)”. Dopowiem jeszcze, że owe MOGĄ (co być może współgra z intuicją p. Piotra) stosuje się bardziej do komputerów przyszłości niż współczesnych.
Oto i argumentacja (niekiedy powtórzona za wykładem i postami).
1) Komputery mogą być nieobliczalne w sposób fundamentalny, to znaczy istnieją pewne dotyczące ich pracy problemy, których nie można we wszystkich przypadkach szczególnych rozwiązać obliczeniowo. Są to problemy nieobliczalne (bezwzględnie). Najbardziej sugestywny z nich to omawiany już problem stopu. Jego analiza przekonuje, że żaden komputer (cyfrowy) nie potrafi przewidzieć, czy dowolny inny komputer (cyfrowy) dla dowolnych danych wejściowych zakończy pracę. W tym sensie zatem komputery są nieobliczalne – nie potrafimy komputerowo obliczyć stosunkowo prostej koncepcyjnie rzeczy: czy dla wszelkich możliwych danych wejściowych dany komputer zakończy pracę. W ten sposób nieobliczalność problemu stopu, jest jak gdyby dziedziczona przez nieobliczalne/nieprzewidywalne komputery (o których nie możemy dowiedzieć się, czy zakończą pracę).
2) Sprawa kolejna. Musimy zgodzić się, że obok problemów nieobliczalnych bezwzględnie (jak powyższy) istnieją problemy trudno-obliczalne, zwane także nieobliczalnymi praktycznie (np. problem spełnialności formuł rachunku zdań).W zasadzie (jakościowo – jak pisze p. Piotr) są one obliczalne, praktycznie jednak, przy dużych danych – nie.
Dla ich efektywnego rozwiązania przybliżonego (de facto rozwiązujemy wtedy inny problem: problem przybliżenia) stosujemy różne strategie heurystyczne. Ja będę się upierał, że jeśli są to strategie losowe (najlepiej, żeby za ich losowość odpowiadał pewien element sprzętowy; choć w typowych komputerach tak nie jest), to komputery mogą stać się nieprzewidywalne. Przyczyną tejże nieprzewidywalności byłby ślepy los, który decydowałby o niektórych przynajmniej parametrach realizowanego algorytmu.
[W tym miejscu wynika ciekawe pytanie (na które w tej chwili nie potrafię udzielić odpowiedzi): czy „prawdziwe” losowania sprzętowe, oparte o jakieś procesy fizyczne, zapewniają lepszą wydajność danego programu/komputera niż „fałszywe” losowania pseudo-losowe?]
3) I wreszcie sprawa trzecia (o której piszę w tekście „Nieobliczalność i złożoność”). Na praktyczną nieprzewidywalność komputerów może mieć wpływ kolosalna złożoność algorytmów, które powstają w drodze stopniowych kumulacji/nawarstwień różnych algorytmów cząstkowych. Owa kolosalna złożoność powoduje, że mimo bardzo szeroko zakrojonych testów, nie jesteśmy w stanie przewidzieć wszelkich możliwych reakcji systemu na wszelkie możliwe dane.
Popuszczając wodze spekulacji można wyobrazić sobie, że złożoność algorytmu testującego jest porównywalna ze złożonością algorytmu testowanego, co powoduje że algorytm testujący też trzeba testować, i tak dalej, i tak dalej… w nieskończoność.
Podsumowując zatem: choć wydaje nam się, że komputery – będące naszymi wytworami i wyposażone w opracowane przez nas oprogramowanie – muszą być w pełni przewidywalne/obliczalne, to de facto tak nie jest. Oczywiście nie we wszystkich szczególnych przypadkach – ale ogólnie tak nie jest.
Dziękuję za odpowiedź. Od razu odniosę się do trzech powyższych punktów:
1) Problem dotyczy dowolnego algorytmu i zgodzę się, że to jest problem nieobliczalny. Ale możemy rozwiązać każdy z tych problemów w szczególności (pomijam złożoność czasową i obliczeniową), znając algorytm oraz dane wprowadzone do programu. Jeżeli będziemy kazać wykonać komputerowi problem stop-u, to nie możemy oczekiwać, że odda nam odpowiedź. Zwróci nam wynik, który można przewidzieć oglądając algorym (ponowie pomijam złożoność). Każdy napisany przez człowieka algorytm można przewidzieć, ale jeśli nie jest w stanie zrobić tego maszyna, to nie świadczy o nieobliczalności. Podobnie, jeśli ja nie jestem w stanie udowodnić Wielkiego Twierdzenia Fermata, to nie znaczy, że jest ono nierozwiązywalne.
2) Oprę się na wspólnym zdaniu, że jakościowo problemy trudno-obliczalne możliwe są do obliczenia. Możliwe, że za 100 lat matematycy czy informatycy, będą w stanie policzyć te problemy w kilka miesięcy czy tygodni, a z pewnością problem nieobliczalny nie może się zmienić w obliczalny (z tego co wiem jest to pewna własność problemów/funkcji/liczb, która jest dla nich stała i udowodniona).
[Dodatkowy generator sprzętowy liczb losowych nie jest cześcią komputera (przynajmniej w moim rozumieniu), a komputer otrzymuje tylko pewne dane, które interpretuje – mając te dane i znając algorytm człowiek jest w stanie „wylosować” identyczne liczby.]
3) Odwołuje się to do poprzedniego punktu. Choć nikt z żyjących ludzi, ani działających maszyn nie jest w stanie tego zrobić, jest to możliwe na jakimś innym poziomie, który dla nas jest odległy (przynajmniej obecne). A jeżeli jest to możliwe, to jest też obliczalny (jakościowo).
Pozdrawiam
Piotr Krzeszewski
Widzę, że dyskusja się rozwija. Zatem i ja pozwolę sobie dorzucić garść własnych obserwacji.
(1) Uwaga wstępna, terminologiczno/definicyjna – otóż w precyzyjnym (matematycznym) ujęciu obliczalny, lub nie, może być algorytm, a nie komputer. Komputer jest fizyczną maszyną służącą do realizacji algorytmów (a właściwie ich implementacji w konkretnym języku programowania) i pozbawiony ich – sam w sobie – nie jest ani obliczalny, ani nieobliczalny.
(2) Czy oznacza to, że w ogóle nie ma sensu mówić o nieobliczalności komputerów? Sądzę, że jest wprost przeciwnie. Uważam, że komputer możemy uznać za nieobliczalny – i to w znaczeniu różnym od nieobliczalności algorytmu, który wykonuje. Dzieje się tak wówczas, gdy pod słowo „komputer” podstawiamy „pracujący komputer”. Wówczas na finalny efekt działania komputera ma wpływ szereg czynników innych niż własności samego algorytmu, który akurat jest obliczany. Czynniki te mogą być najrozmaitsze – od nieoczekiwanych skoków napięcia w sieci aż po wpływ wysokoenergetycznych cząstek promieniowania kosmicznego, które mogą przedostać się przez atmosferę i ingerując na poziomie kwantowym w hardware wpłynąć na finalny wynik obliczeń.
Musimy jednak pamiętać, że w takiej sytuacji mamy do czynienia z pozamatematycznym rozumieniem słowa „nieobliczalność”. W istocie byłoby to chyba trzecie rozumienie tego terminu (po matematycznym i potocznym), które można by nazwać „fizykalnym” – gdyż podkreśla kluczowe znaczenie faktu materialności maszyny komputującej i wpływu losowych zjawisk fizycznych na wynik jej pracy. Podsumowując: pracujące komputery mogą być nieobliczalne w sensie odmiennym od ewentualnej nieobliczalności algorytmu, który akurat wykonują.
(3) Kolejny problem – związany z moimi powyższymi uwagami – nie został poruszony wprost, lecz pojawił się niejako w tle rozważań p. Piotra. Jest nim kwestia pomijalności warunków fizycznych w obliczeniach. I jest to problem niezwykle ważki. W tekstach z zakresu teorii obliczalności i złożoności obliczeniowej wielokrotnie można się spotkać ze stwierdzeniami typu „problem X w zasadzie jest obliczalny” o ile tylko „pominie się czas niezbędny do dokonania obliczeń”. Zastanówmy się przez chwilę nad prawomocnością takiego podejścia do sprawy. Oczywiście mam świadomość, że jest to problem godzien osobnego artykułu i wątku na blogu, dlatego nie będę go rozwijał bardzo szczegółowo i ograniczę się do podania dwóch ogólnych powodów, które – w moim odczuciu – dyskwalifikują wspomniane podejście.
(A) Przede wszystkim należy pamiętać, że wszelkie obliczenia są ZAWSZE wykonywane przez jakiś system FIZYCZNY. Matematyczny model obliczeń (turingowski, czy jakikolwiek inny) jest tylko TEORIĄ FORMALNĄ, która sama w sobie absolutnie niczego nie komputuje. Uniwersalna Maszyna Turinga, rachunek lambda itp. konstrukcje są tylko opisami, które nie mają jakiejkolwiek wewnętrznej dynamiki – trochę jak platońskie idee, które są niezmienne i same w sobie nie działają, bo nie mogą działać. Natomiast REALNE PROCESY obliczeniowe wykonywane są zawsze przez taki czy inny układ fizyczny, który ograniczony jest prawami fizyki – i nie ma od tego ucieczki. Z tego powodu sądzę, że nie można abstrahować – mówiąc o fizycznych procesach komputacyjnych (a nie o formalnych modelach obliczeń) – od fizykalnych cech systemów liczących. Zauważmy też, że czas jest wielkością fizyczną w zasadzie nieistotną w czystej matematyce (która nie zajmuje się procesami rozciągłymi czasowo). Można więc usprawiedliwić matematyków mających tendencję co lekceważenia czynnika czasowego, gdy zajmują się modelami formalnymi obliczeń. Natomiast nie można tego uczynić, gdy zajmujemy się realnymi procesami obliczeniowymi wykonywanymi przez układy fizyczne zawsze funkcjonujące w czasie.
(B) O tym, że nie należy lekką ręką odrzucać fizycznych ograniczeń procesów obliczeniowych niech przekona następujący eksperyment umysłowy.
Jak wiadomo wydajność obliczeniowa materii fizycznej jest ograniczona. Otóż nowoczesna mechanika kwantowa pozwala nam obliczyć: a) maksymalną ilość informacji, która może zostać zapisana w jednostce masy zajmującej pewną skończoną objętość (owa zależność opatrzona została od nazwiska jej odkrywcy mianem granicy Bekensteina) oraz b) maksymalną szybkość przetwarzania informacji w jednostce czasu. Uwzględniwszy te fakty oraz uczyniwszy rozumne założenie, że ilość materii we wszechświecie oraz czas jego istnienia są skończone (pomijam tu kwestie możności istnienia innych wszechświatów postulowaną przez multiwersalną interpretację mechaniki kwantowej Everetta-Deutscha) musimy dojść do oczywistego wniosku – możliwości komputacyjne wszechświata są skończone. Z tego wynika wniosek, że istnieją problemy, których NIE DA SIĘ obliczyć przez jakikolwiek układ fizyczny. W modelu turingowskim problem obliczalny to taki, który można rozwiązać w skończonej ilości kroków. Owa ilość kroków wyraża się zawsze pewną liczbą naturalną. Z tego co napisałem powyżej wynika, że dla całego uniwersum fizycznego można wyznaczyć maksymalną ilość kroków komputacyjnych (K), które teoretycznie mogłyby być przez nie wykonane (o ile udałoby się obrócić całość materii wszechświata w tzw. „komputronium” – ultymatywny wszechświatowy megakomputer – co oczywiście jest niewykonalne). Rzecz jasna ilość ta również wyraża się liczbą naturalną (K = x). Wystarczy teraz wyobrazić sobie, że dla jakiegoś problemu obliczalnego w sensie Turinga liczba kroków komputacyjnych niezbędnych dla jego rozwiązania to n+1 i oto mamy problem najzupełniej nieobliczalny w jakimkolwiek sensie fizycznym.
Na tym poprzestaję, gdyż, jak zauważyłem powyżej, temat wymagałby osobnego potraktowania a ja i tak rozpisałem się już niepomiernie. Jeżeli jednak ktoś chciałby go kontynuować (tu, czy w osobnym wątku), to z przyjemnością wezmę udział w dyskusji.
Dyskusja faktycznie się rozwija. I to wielowątkowo.
Odpowiem na razie p. Piotrowi.
Zastanawiałem się dość długo jak to zrobić i postanowiłem, po pierwsze, skoncentrować się na jednym tylko punkcie (nie wszystko od razu – bo wtedy dyskusja staje się zbytnio hasłowa), a po drugie, podeprzeć się cytatem z książki, którą i p. Piotrowi, i innym szczerze polecam jako najlepszą pozycję z dziedziny popularyzacji informatyki (w tym zagadnień nieobliczalności), jaką czytałem. Jest to książka Davida Harela p.t. „Algorytmika. Rzecz o istocie informatyki”.
Na początek jednak kilka słów wstępu. Otóż zagadnienie nieobliczalności nie jest naprawdę zagadnieniem trywialnym, które poddaje się gładko analizom zdroworozsądkowym. Łamali sobie nad nim głowy (i pióra) prawdziwi matematyczni mocarze, jak Leibniz i Hilbert („algorytmiczni optymiści”), czy Gödel i Turing (odkrywcy faktów nastrajających raczej pesymistycznie). Właśnie odkrycia dwóch ostatnich zdają się stać w sprzeczności ze zdrowym rozsądkiem, który podpowiada: (a) jest jasno wyrażony problem, więc musi istnieć jego algorytmiczne rozwiązanie; (b) jest algorytm, który napisaliśmy my sami, więc musimy wiedzieć, jaki wynik zwróci tenże algorytm dla wszelkich danych (przecież zawsze możemy go wykonać!).
Gdzie nasz zdrowy rozsądek się załamuje? Otóż załamuje się tam, gdzie wkracza nieskończoność. Tak zresztą bywa często: dla wielu osób np. zupełnie kontrintuicyjny wydaje się fakt że nieskończona suma wyrazów szeregu harmonicznego (suma liczb typu 1/n) dąży ku nieskończoności, czyli nie istnieje, a bardzo podobna suma odwrotności kwadratów kolejnych liczb (suma liczb typu 1/n^2) istnieje. Matematycy tymczasem potrafią podać na to ścisłe dowody.
Ale do rzeczy. Przejdźmy do niezbyt jasnej intuicyjnie sprawy przewidywalności algorytmów i realizujących je komputerów. Oto cytat ze wspomnianej książki Harela:
„Jak już stwierdzono, problem stopu jest nierozstrzygalny , co oznacza, że nie sposób powiedzieć (PS: przewidzieć) w skończonym czasie, czy dany program R zatrzyma się dla danych X. W poszukiwaniu rozwiązania problemu warto po prostu przetestować program R na danych X i zobaczyć, co się dzieje. W porządku, jeśli (i tylko wtedy, gdy) program zatrzyma się, możemy powiedzieć, że odpowiedź brzmi „tak”. Trudność polega na zdecydowaniu, kiedy zakończyć czekanie i dać odpowiedź „nie”. Nie możemy poddać się w pewnym punkcie mówiąc, że ponieważ program nie zatrzymał się aż do tej chwili, nigdy się już nie zatrzyma. Być może, gdybyśmy zostawili programowi R troszeczkę więcej czasu, to zatrzymałby się. Wykonanie programu R dla danych X nie załatwia zatem sprawy, i jak stwierdzono, nic nie może załatwić sprawy, ponieważ problem jest nierozstrzygalny”.
A zatem – to już moje dopowiedzenie – działanie (i zatrzymanie się) komputera jest nieprzewidywalne, ponieważ nie możemy czekać na rozstrzygnięcie w nieskończoność.
W tej samej książce Harela jest podany bardzo ciekawy przykład prostego algorytmu, o którym nikt jeszcze nie udowodnił, że dla wszelkich możliwych danych zatrzyma się. Choć nie wiadomo, czy problem stopu tego algorytmu jest nierozstrzygalny, to warto zwrócić uwagę na „przepaść” między skrajną prostotą algorytmu i ogromną trudnością w całościowej analizie jego sposobu działania.
Oto przykład: (1) Dopóki x różne od 1 wykonuj: (1.1) jeśli x jest parzyste, wykonaj x=x/2; (1.2) jeśli x jest nieparzyste, wykonaj x=3x+1; (2) zatrzymaj się (gdy x=1).
Harel podaje, że dla wszystkich testowanych liczb algorytm zatrzymywał się, lecz być może (nie ma na to dowodu) w przypadku pewnej szczególnej wartości wejściowej x ciąg wartości pośrednich zapętli się, nie dochodząc nigdy do 1 (być może też nie zapętli się, lecz będzie zupełnie nieregularnie „krążył wokół jedynki”).
Powyższe cytaty i przykłady podałem dla celów dydaktycznych, aby zobrazować jakoś kontrintuicyjny fakt, że nie zawsze algorytm, który sami napisaliśmy i który możemy uruchomić dla każdych danych, da się zdiagnozować w skończonym czasie. Innymi słowy: gdy wkracza nieskończony czas oczekiwania, pojawia się poważna (być może: nieusuwalna w ogóle) trudność.
Spostrzegłem oczywiście, że p. Piotr napisał (trochę nieprecyzyjnie): „Każdy napisany przez człowieka algorytm można przewidzieć, ale jeśli nie jest w stanie zrobić tego maszyna, to nie świadczy o nieobliczalności”. Rozumiem, że w ten sposób p. Piotr wyraził swoje przekonanie o wyższości umysłu ludzkiego nad maszyną.
Można odpowiedzieć na to trochę wymijająco, że oczywiście „świadczy o nieobliczalności” bo obliczalność problemu definiuje się jako możliwość jego algorytmicznego rozwiązania, czyli rozwiązania przez jakąś maszynę.
Rozumiem jednak, że p. Piotrowi chodzi o inne rozumienie obliczalności – obliczalności przez ludzki umysł. Tu jednak pojawia się poważny kłopot – tym razem: filozoficzny. Skąd wiadomo bowiem, że umysł ludzki nie podlega tym samym ograniczeniom co maszyny (jeśli nawet nie cyfrowe, to może jakieś inne). Turing, na przykład, sądził, że podlega; Gödel zaś – wręcz przeciwnie. Współcześnie zaś – wciąż się nad tym dyskutuje.
Nie można zatem stwierdzać lekko, że każdy problem nierozwiązywalny przez maszynę (nierozwiązywalny mocą dowodu matematycznego), ma jakieś rozwiązanie dostępne dla umysłu ludzkiego.
Tyle (i tak wyszło bardzo dużo) na temat nieobliczalności problemów, która skutkuje nieprzewidywalnością działań komputerów.
Związek nieobliczalności z losowością (tą prawdziwą, a nie: symulowaną programistycznie) to kolejny nietrywialny temat, który zasługuje na kolejny wpis i kolejną dyskusję pod nim… Ale to w przyszłości.
Bardzo dziękuję za wszelkie uściślenia i wytłumaczenia udzielone przez p. Radka i p. Pawła Stacewicza.
Przyjmując przedstawioną definicję komputera oczywiście zgadzam się z dalszymi uwagami dotyczącymi ich nieobliczalności. Nieznane było mi też pojęcie zdolności materii do przetwarzania danych.
Zgadzam się również i dziękuję za uwagi zawarte w drugim poście. Zacytowane zdanie dotyczące porównania ludzi i komputerów nie miało w założeniu dotyczyć wyższości człowieka nad maszyną. Chciałem wskazać, że człowiek jest w stanie zrobić algorytm mając dane wejściowe i jego zapis tak, jak wykonałaby to maszyna – i dzięki temu „obliczyć” wynik. Jednak po sprecyzowniu pojęcia komputera oraz przedstawieniu (nieznanego mo wcześniej) twierdzenia Bekensteina wycofuję się z tej tezy.
Pozdrawiam i dziękuję
Piotr Krzeszewski