Około dwóch miesięcy temu wprowadziłem do blogu – trochę na próbę, a trochę dla zabawy – nowy jakby gatunek tekstów typu „o rzeczach trudnych – na chłopski rozum”. Na dobry początek zamieściłem dialog z rolnikiem, którego chłopski rozum wniknął całkiem dobrze w niełatwy temat nieskończoności zbiorów. Żywa reakcja na tamten tekst (około 20 burzliwych miejscami komentarzy) zachęciła mnie do kontynuacji…
W kolejnym dialogu chłopa zastąpił księgowy, a zbiory ustąpiły miejsca liczbom. Konwencja jednak pozostała ta sama: rozmówca matematycznej reporterki nie za bardzo „wyznaje się” na dyskutowanym pojęciu, stopniowo jednak oswaja się z nim i próbuje przymierzyć doń swą nie-matematyczną intuicję.
W zamierzeniu autora ma to być wstęp do dyskusji z czytelnikiem, który być może zechce dowiedzieć się czegoś więcej, a być może też, dysponując większą od autora wiedzą, pewne jego wyjaśnienia skoryguje lub uzupełni…
Zapraszam do lektury – Paweł Stacewicz.
******
Z KSIĘGOWYM O LICZBACH NIEOBLICZALNYCH
(czyli o tym, czego nie mogą policzyć komputery)
W niewielkim pomieszczeniu biurowym pracuje przy komputerze młody mężczyzna. Przypatruje mu się stojąca w drzwiach młoda dziewczyna z charakterystyczną reporterską torbą na ramieniu. Gdy mężczyzna przerywa pisanie na komputerze, odzywa się doń.
– Dzień dobry. Przypatruję się Panu od dłuższej chwili i widzę, że Pan ostro liczy…
– Taka praca. A Pani, przepraszam, do kogo? Była Pani umówiona?
– A i owszem. Chyba nawet z Panem: 17.30, wywiad z księgowym o liczbach.
– Oj, faktycznie. Bardzo Panią przepraszam. Za chwilkę będę gotowy…
Odwraca się do komputera. Wpisuje pospiesznie ostatnie dane, zamyka laptop i mówi:
– W porządku, możemy zaczynać.
– W takim razie, raz jeszcze dzień dobry. Wyjaśnię na początek, że wywiad nasz ukaże się na antenie radia edukacyjnego MAT, a ma traktować o liczbach nieobliczalnych.
– Pamiętam, pamiętam… I przyznam się, że temat ten nadal brzmi dla mnie dość frapująco.
– Domyślam się, że to nie liczby Pana frapują, lecz ich ewentualna nieobliczalność?
– No tak! Na mój zdrowy księgowy rozum liczba to coś, co można obliczyć. Nie zawsze samemu, częściej za pomocą kalkulatora lub komputera, ale zawsze jakoś można…
– A z jakimi liczbami ma Pan w swoim księgowym fachu do czynienia?
– No cóż. Ze zwykłymi raczej. Przed chwilą, na przykład, sumowałem w Excelu liczby czterocyfrowe z dwoma miejscami po przecinku.
– Ale nie były to liczby naturalne?
– No nie. O ile dobrze pamiętam, liczby naturalne to 1, 2, 3, 4 itd., zawsze o jeden więcej. Bez żadnych miejsc po przecinku. Takie jakby najprostsze liczby całkowite.
– To się oczywiście zgadza. A te Pańskie „zwykłe liczby z Excela” są, rzecz jasna, bardziej skomplikowane. Jakbyśmy je nazwali?
– Czy ja wiem? Ułamki? … Liczby dziesiętne z częścią ułamkową?…
Wymierne chyba. Tak: wymierne.
– No tak. Przypomnę słuchaczom, że jakkolwiek liczby wymierne można przedstawiać w postaci dziesiętnej (np. 7/4 to 1.75), to definiuje się je jako liczby postaci „m dzielone przez n”, gdzie zarówno m, jak i n, należą do liczb całkowitych.
A teraz pytanie do Pana: czy według Pana prócz wielkości wymiernych istnieją inne jeszcze rodzaje liczb?
– No tak! Są jeszcze liczby niewymierne.
– Może jakiś przykład?
– Jasne. Na przykład Pi, czyli 3 i 14 setnych.
– A dalej?
– No właśnie. Dalej to, po pierwsze, nie pamiętam, a po drugie, pamiętam, że nie ma żadnej reguły, która pozwalałaby wypisywać kolejne cyfry.
– Dobrze Pan to ujął. Właśnie ów brak reguły powoduje, że Pi jest liczbą niewymierną, czyli taką, której nie da się przedstawić w postaci m/n.
– Aaaha. Czyli to tu pojawia się nieobliczalność … Prawdę mówiąc, trochę się rozczarowałem.
– Niech Pan się nie denerwuje. To jeszcze nie TO…
– Jak to: nie TO?
– TO jeszcze nie jest liczba nieobliczalna. Liczba Pi, a razem z nią wiele innych wielkości niewymiernych (choćby pierwiastek z dwóch) ma tę własność, że da się ją obliczyć z dowolną zadaną dokładnością.
– Tutaj się ciutkę pogubiłem. W jaki sposób można ją obliczyć z dowolną zadaną dokładnością, skoro nie znamy reguły generowania kolejnych cyfr jej rozwinięcia dziesiętnego?
– W pewnym sensie regułę znamy. Ale jest ona dana w sposób dość skomplikowany, za pomocą nieskończonego szeregu liczbowego, którego granicą jest właśnie liczba Pi. Ten szereg to jakby nieskończona suma liczb, które określamy jednolitym wzorem.
– Rozumiem. Mamy ten wzór i mamy regułę sumowania. A to wystarczy, by naszą liczbę obliczać coraz dokładniej…
– Dokładnie tak jest. A im więcej sumujemy kolejnych liczb ( tak naprawdę są to wyrazy pewnego ciągu), tym większą zyskujemy dokładność.
– Konkludując: Pi jest liczbą niewymierną, choć obliczalną.
– Powiedział Pan jak matematyk.
– Bo rzecz mnie wciąga. Domyślam się, że istnieją jakieś specjalne liczby niewymierne, których nie sposób obliczyć na podobieństwo Pi…
– Tak jest. Ich istnienie udowodnił w XX wieku Alan Turing – jeden z pierwszych i najlepszych podówczas specjalistów od maszyn liczących.
– Podał jakiś przykład?
– Nie. Lecz wykazał ściśle, że założenie o istnieniu liczb wyłącznie obliczalnych prowadzi do logicznej sprzeczności. Tym samym stało się jasne, że muszą istnieć nieuchwytne dla maszyn rodzaje liczb niewymiernych. A co więcej: musi być ich nieskończenie wiele.
– Powiedziała Pani: „nieuchwytne dla maszyn”. Ale jakich?
– Cyfrowych. Dowód Turinga dotyczy maszyn cyfrowych, a konkretniej wszelkich możliwych algorytmów, które mogą być wykonane na wszelkich możliwych maszynach cyfrowych. Powtórzę jeszcze raz: wszelkich. Tych, które już skonstruowano, i tych, które dopiero zostaną wynalezione.
– Teoretycznie zatem: istnieją jakieś problemy, np. z dziedziny księgowości, którym ani mój laptop, ani żaden inny komputer cyfrowy, po prostu nie poradzi. Byłyby to takie problemy, których rozwiązaniami są liczby nieobliczalne.
– Tak. Tak wynika z matematycznych rozumowań Turinga. Liczby nieobliczalne są w pewnym sensie równoważne problemom nierozwiązywalnym przez maszyny cyfrowe. No i tutaj właśnie, w dziedzinie problemów a nie samych liczb, podał Turing sugestywny przykład.
– ???
– Mówiąc z grubsza, postawił problem napisania algorytmu, który sprawdzałby, dla jakich danych inne algorytmy kończą pracę, a dla jakich się zapętlają. Okazało się, że jest to zadanie niewykonalne – innymi słowy, nieobliczalne. Potem zaś odkryto takich zadań więcej.
– Smutne…
– Czy ja wiem? Może nawet krzepiące. Być może ludzki umysł w tym właśnie przewyższa komputery, że potrafi dostrzegać i rozwiązywać problemy nieobliczalne?
– Hmm. Muszę nad tym pomyśleć. Bo filozoficznie rzecz biorąc, jeśli Pani pozwoli, owo intrygujące „umysłowe być-może” jest, być może, kolejnym nieuchwytnym dla maszyn problemem nieobliczalnym. To znaczy: trudno mi sobie wyobrazić, aby jakiś komputer potrafił Pani pytanie rozstrzygnąć?
– Hmm. Tym razem to i ja chyba, i słuchacze, będziemy to musieli przemyśleć. Tymczasem pora kończyć. Dziękuję pięknie za wywiad i filozoficzne zakończenie.
*******
Powyższy tekst pochodzi z materiałów projektu o nazwie „Archipelag Matematyki”, który jest realizowany (z moim udziałem) w Politechnice Warszawskiej. Gdyby ktoś poczuł się mocno zainspirowany i/lub zainteresowany, to mam dla niego inny tekst autorstwa G. Chaitina, odkrywcy pierwszej liczby nieobliczalnej. Artykuł Chaitina jest napisany bardzo przejrzyście i lekko; poprzedza go ciekawa przedmowa Józefa Dębowskiego.
Zapraszam do dyskusji poniżej – Paweł Stacewicz.
Materiał bardzo pożyteczny! Daje wiele ważnych informacji w sposób przystępny, zwięzły i ciekawy. Zasługuje na rozwinięcie w osobnym tekście temat zasygnalizowany zwrotem „problemy, których rozwiązaniami są liczby nieobliczalne”. Jeśli „rozwiązanie” zastąpić przez „rozstrzygnięcie”, od czego pochodzi fundamentalne pojecie rozstrzygalności, to zacytowane zdanie kieruje uwagę na pytanie o stosunek między rozstrzygalnością, której dotyczą wyniki Gödla, i obliczalnością zdefiniowaną przez Turinga. Przydałby się w tej sprawie krótki wpis, jakby przypis do obecnego, połączony linkiem.
X
A ja bym zapytał matematycznej reporterki tak:
Czy spotkała się pani z takim zapisem: 0,9999… = 0,(9) ?
Czy tych cyfr '9′ na kolejnych pozycjach po przecinku jest nieskończoność ∞?
Czy ilość cyfr wzrośnie o '1′ gdy dodamy jedną dziewiątkę?
9 + 0,(9) = 9,(9) Tak?
Czy ∞ + 1 = Ω ?
Czy Ω > ∞ ?
Po odpowiedziach matematycznej reporterki zorientował bym się, czy rozumie sens słów, których używa takich jak : 'nieskończony szereg liczbowy’, 'granica’, 'suma szeregu nieskończonego’.
Tu pani reporterka wyraża się nieściśle. Z dowolnie zadaną dokładnością można wyznaczyć przybliżenie liczby Pi, a nie samą liczbę – która nie jest przybliżeniem, np. liczba 3 nie jest liczbą Pi choć stanowi przybliżenie z dokładnością do liczb całkowitych;
liczba 3,1 nie jest liczbą Pi choć stanowi przybliżenie z dokładnością do jednego miejsca po przecinku itd.
a ponadto:
słowa dowolnie zadana dokładność dotyczą tylko tych liczb, które komputer jest w stanie zarejestrować, a więc to dokładność dowolna, ale nie większa od możliwości obliczeniowych maszyny liczącej.
۞
Może odrobinę sprostuję, żeby kolejni odwiedzający stronę nie zostali wprowadzeni w błąd.
Po pierwsze ∞ nie jest liczbą, a koncepcją matematyczną. Nie można do niej dodać liczby, więc zapis ∞ + 1 jest w tym przypadku bez sensu. 0,(9) nie jest najlepszym przykładem, ale jeśli dopiszemy kolejną cyfrę 9, to cyfr nadal będzie ∞.
Lepiej można tą koncepcję zobrazować na przykładzie logicznym. Załóżmy, że istnieje hotel z nieskończoną ilością pokoi, których numery to kolejne liczby naturalne. Do hotelu przybywa nieskończona liczba gości i każdy zajmuje kolejny pokój. Do hotelu przybywa jeszcze jeden gość. W jaki sposób go zakwaterować? Wystarczy kazać gościom obecnie przebywającym w hotelu przenieść się do pokoju n+1, przez co pierwszy pokój zostanie wolny i można w nim zakwaterować kolejnego gościa, lecz gości nadal jest ∞. Więc ∞ + 1 = ∞.
Może też przybyć kolejna nieskończoność gości i nadal można ich zakwaterować w pełnym hotelu. Wystarczy, że obecni goście przeniosą się do pokoi o numerach n*2, przez co pokoje o numerach nieparzystych zostaną wolne. Wtedy ∞ +∞ = ∞.
Warto w tym miejscu zaznaczyć, że istnieją różne rozmiary nieskończoności, np. liczb rzeczywistych z przedziału od 0 do 1 jest więcej niż wszystkich liczb całkowitych.
Jeśli chodzi o słowa „dowolnie zadana dokładność”, to odnoszą się one do faktu, że istnieje algorytm, który pozwala obliczyć przybliżenie danej liczby z dowolnie zadaną dokładnością. Trochę trudno to sobie wyobrazić, ale w przypadku liczb nieobliczalnych taki algorytm po prostu nie istnieje. Nie ma to nic wspólnego z możliwościami obliczeniowymi maszyny, ponieważ obliczenia można wykonywać nawet na kartce papieru.
Bardzo dziękuję za to sprostowanie, z którym się całkowicie zgadzam. Dwa komentarze niżej też prostowałem stwierdzenia p. Robakksa. Zapraszam do dyskusji, wyjaśnień, dopisków… pod innymi wpisami i komentarzami dotyczącymi nieobliczalności!
Dla wielu ludzi zdziwieniem może być to, ze istnieją problemy nieobliczalne, takie dla których udowodniono, że nie da się ich rozwiązać. I nie jest to nic dziwnego. Nawet tak wielki matematyk jak David Hilbert, który marzył by stworzyć zupełny i niesprzeczny system reguł i aksjomatów w matematyce, mylił się. Właśnie twierdzenie Gödla pozbawiło go tego marzenia.
Odnośnie tekstu, zawsze lubiłem tłumaczenia „na chłopski rozum”. Kształtują wyobraźnie, zostają dłużej w głowie niż zwykłe wzory i wyrabiają pewien instynkt. Szkoda, że są tak rzadko stosowane. Materiał, tak jak zauważył przedmówca, jest dobry. Również z chęcią dowiedziałbym się więcej na temat zasygnalizowany zwrotem „problemy, których rozwiązaniami są liczby nieobliczalne”.
Do MB:
Cieszy mnie uwaga o Hilbercie. Specjaliści wiedzą, o czym marzył Hilbert, ale szerszą publiczność trzeba uświadamiać o tych niespełnionych snach, bo z faktu udowodnienia ich niespełnialności – jak zauważa Chaitin – wzięła się informatyka, mianowicie koncepcja maszyny Turinga. Turingowi służyła ona do wykazania, że program Hilberta to nie jawa, lecz sen, ale zarazem wyłonił się z tego, jakby sam z siebie techniczny (choć wielce schematyczny) projekt komputera cyfrowego.
Odpowiem na początek panu Robaksowi (występując w obronie reporterki):
1) Stosując zasadę interpretacyjnej życzliwości , przyjąłbym jednak, że reporterka wie o czym mówi, gdy używa pojęć „granica” czy „nieskończony szereg liczbowy”. Zresztą będzie się mogła tym wykazać, występując w dwóch innych tekstach z serii „na chłopski rozum” – które zamieszczę w blogu już niebawem (są gotowe, lecz czekają na swoją kolej).
Definicja granicy ciągu liczbowego jest tu kluczowa, stanowi fundament analizy matematycznej, a zaczyna się od słów „Dla każdego epsilon większego od zera…”, gdzie epsilon można interpretować jako dokładność wyznaczenia granicy ciągu.
2) „Obliczania liczby pi z dowolną zadaną dokładnością” też bym się nie czepiał, bo jeśli liczbę pi zdefiniujemy jako sumę pewnego szeregu liczbowego (a tak można zrobić), to tę sumę (istniejącą granicznie, ale jednak) możemy obliczać z dowolną zadaną dokładnością, biorąc dostatecznie dużo wyrazów sumowanego ciągu. Wynik takiego obliczenia można (a nawet trzeba) nazwać przybliżeniem liczby pi (czyli tak jak chce p. Robakks), ale najważniejszy jest tu fakt, że gdy zażyczymy sobie większej dokładności (czyli lepszego przybliżenia), to zawsze ją osiągniemy sumując odpowiednio dużo (niekiedy bardzo dużo) wyrazów odpowiedniego ciągu. Podobnie będzie dla liczby niewymiernej e, której szereg jest wyjątkowo prosty: ∑1/n!.
Dla Turinga takie liczby jak Pi czy e były obliczalne właśnie dlatego, że można je było obliczyć (przybliżyć) z dowolną zadaną dokładnością według pewnej reguły; natomiast okazało się, że prócz nich istnieje nieprzeliczalnie wiele liczb, których w taki sposób obliczyć się nie da; i je właśnie nazwał Turing nieobliczalnymi (uncomputable numbers).
3) Ostatnia uwaga o ograniczeniach maszynowej reprezentacji liczb jest oczywiście słuszna. Wskazuje ona na rozdźwięk, jaki niewątpliwie istnieje, między teoretyczną konstrukcją Turinga (jego maszyna dysponuje w teorii nieskończoną taśmą), a jej praktycznymi realizacjami (komputerami cyfrowymi o skończonej pamięci). Ciekawe jednak, że nawet w sferze teorii pojawia się rozróżnienie między liczbami teoretycznie obliczalnymi (z dowolną zadaną dokładnością) i teoretycznie nieobliczalnymi. Odkrycie tego rozróżnienia – rozróżnienia, które wyznacza teoretyczne (czyli ostateczne) ograniczenia maszyn cyfrowych – jest zasługą Turinga.
Chciałbym na koniec usprawiedliwić reporterkę za jej styl: reporterka nie może posługiwać się językiem matematycznych podręczników, bo wtedy nikt nie chciałby z nią rozmawiać; objaśnia wszystko „na chłopski rozum”, próbując nawiązać żywy kontakt z nawykłym do niematematycznego języka rozmówcą.
Definicja granicy ciągu liczbowego jest tu kluczowa
Uważam, że granica ciągu liczbowego jest kluczem do rozwiązania zagadki nieskończoności aktualnej, a więc zrozumienia czym jest liczba ω (omega).
W Wikipedii można przeczytać takie teksty:
1. „Symbol nieskończoności ∞ – został zaproponowany przez Johna Wallisa w De sectionibus conicis 1655 i konsekwentnie używany przez niego w późniejszych pracach (np. Arithmetica infinitorum – 1655 lub 1656).”
2. „Przejście od indivisibles Cavalieri do ‘nieskończenie małych’ Johna Wallisa, było ważnym krokiem w historii rachunku. W indivisibles były jednostki (codimension 1) współpracujące w taki sposób, że sądzono iż płaszczyzna rysunku wykonana jest z nieskończenie małych (infinity) 1-wymiarowych punktów. Tymczasem ‘nieskończenie małe’ Wallisa to były jednostki o tym samym wymiarze, jak rysunek, który tworzą, dlatego płaszczyznę tworzą „równoległoboki” o nieskończenie małej szerokości. Stosując wzór na sumę ciągu arytmetycznego, Wallis obliczał pole trójkąta przez rozdzielenie go na nieskończenie małe równoległoboki o szerokości 1/∞.”
3. „Po ponumerowaniu wszystkich etapów opisywanych liczbami naturalnymi można przejść do kolejnego etapu, w którym zostanie użyty numer ω. ω oznacza liczbę używaną do oznaczenia kroku, który następuje po wszystkich krokach oznaczonych przy użyciu liczb 0, 1, 2, 3, … ”
Ten 3-ci punkt jest ciekawy i wynika wprost z prac Cantora nad liczbami porządkowymi.
Jeśli wszystkie kroki numerowane kolejnymi liczbami 0, 1, 2, 3, … zostaną wykonane – to w zbiorze liczb naturalnych nie będzie już żadnych numerów które można by użyć do ponumerowania kroków kolejnych, a więc krok ω (omega) jest liczbą, która nie należy do zbioru N. To liczba pozaskończona która występuje po przekroczeniu granicy zbioru N.
Liczba ω jest liczbą całkowitą, a nie jest liczbą naturalną.
۞
Dziękuję za tę uwagę, zwłaszcza punkt trzeci. Temat liczb porządkowych jest niewątpliwie dla tematyki naszego forum ważny i trzeba by go przy jakiejś okazji systematycznie rozwinąć. Najważniejsze byłyby relacje między liczbami kardynalnymi (moce zbiorów) a liczbami porządkowymi (określającymi jakoś sposoby uporządkownia zbiorów). Sporo informacji na ten temat można znaleźć w książce H. Rasiowej „Wstęp do matematyki współczesnej”. Mówiąc szczerze, ja nie jestem tu specjalistą i w tej chwili nie wypowiem nic sensownego. Ale temat odnotowuję jako wart głębokiego namysłu. Czy ma on jakiś głęboki związek z problemem obliczalności/nieobliczalności (w sensie Turinga)? — tego na razie nie wiem.
Moim zdaniem temat liczb porządkowych miałby związek z tematyką rozstrzygalności i obliczalności, gdyby okazało się, że liczby naturalne i liczby porządkowe nie są tożsame.
_przykład
reporterka uczy księgowego:
„Pi jest liczbą niewymierną, czyli taką, której nie da się przedstawić w postaci m/n.”
Liczby m i n to liczby ze zbioru liczb naturalnych ℕ, więc zgodnie z tą nauką liczba Pi nie jest obliczalna z dokładnością nieskończoną ∞, bo nie są znane takie liczby naturalne, których proporcja wyrażałaby Pi.
…ale…
W Internecie można znaleźć wzór Wallisa na liczbę Pi/2 dla n od 1 do ∞ :
Pi/2 = 2/1 ∙ 2/3 ∙ 4/3 ∙ 4/5 ∙ 6/5 ∙ 6/7 ∙ 8/7 ∙ 8/9 ∙ …
wzór ten można przekształcić używając podwójnej silni !!
Pi/2 = (∞!!)^2 / ((∞-1)!! ∙ (∞+1)) = A/B
Jest więc liczba Pi/2 proporcją dwóch liczb całkowitych A i B, ale obie te liczby nie należą do zbioru liczb naturalnych – są większe od największej.
Kurt Gödel (1906 – 1978) zaliczany jest do metamatematyków, a więc do naukowców badających te produkty ludzkiego umysłu, które określa się nazwą matematyka. Twierdzenia Gödla 'o niezupełności’ oraz 'o niedowodliwości niesprzeczności’ dotyczą systemów aksjomatycznych zawierających postulaty Peano, a zwłaszcza propozycję, by liczbami naturalnymi nazywać taki zbiór, który nie posiada granicy. Postulat ten brzmi:
• Każda liczba naturalna ma swój następnik
Przy takim postulacie nie ma oczywiście możliwości rekurencyjnie osiągnąć i przekroczyć granicy ∞, zbadać nieskończenie małej Wallisa 1/∞, chwili dt Newtona, ani zobaczyć mocy zbioru potęgowego Cantora
continuum = 2^∞
Gödel wykazał, że przy takim postulacie występują liczby (zdania) nieosiągalne z założenia.
Zacytuję fragment z artykułu Kazimierza Trzęsickiego:
http://www.calculemus.org/neumann/odczyty/trzesicki2.pdf
„Do dzisiaj zachowało się nagranie wypowiedzi Hilberta w związku z otrzymaniem w 1930 r. honorowego obywatelstwa Królewca, które kończy, tak jak to czynił już na kongresie w Paryżu:
Wir mussen wissen. Wir werden wissen. To „Musimy wiedzieć. Będziemy wiedzieć.”
dotyczy nie tylko matematyki, lecz również nauk przyrodniczych.
Czyni to mimo wyniku Godla, który jak na ironię dzień wcześniej na II Konferencji Epistemologii i Nauk Ścisłych wykładał w Królewcu twierdzenie o niezupełności; to właśnie twierdzenie, o którym można powiedzieć, że zniweczyło program Hilberta. Chociaż — jak mówi o tym sam Godel — twierdzenie to nie jest sprzeczne z Hilberta
formalistycznym punktem widzenia”
Właśnie. Twierdzenia Gödla nie dotyczą programu Hilberta, bowiem w tym programie nie ma założenia o braku granicy zbioru liczb naturalnych. Intuicja Hilberta czy prof. Michała Hellera „Bóg jest matematyką” wykraczają poza założenia Peano np.
wszechświat jest nieskończony, ale Bóg jest większy – przekracza więc nieskończoność.
albo:
liczb całkowitych dodatnich na osi liczbowej Kartezjusza (liczb naturalnych) jest nieskończenie wiele, ale liczb rzeczywistych na odcinku (punktów) jest więcej — liczb naturalnych jest więc za mało aby przeliczyć wszystkie punkty. Do tego by je przeliczyć konieczny jest zbiór większy od ∞.
Takimi liczbami większymi od nieskończoności są liczby porządkowe Cantora.
Jeżeli dobrze zrozumiałam, to liczbami nieobliczalnymi nazywa się problemy, z którymi nie radzą sobie maszyny liczące (tudzież w naszych czasach komputery). Po głębszym namyśle muszę przyznać, ze faktycznie takie liczby powinny, a wręcz muszą istnieć. Przede wszystkim, jak tak sobie pomyśleć o działaniu komputerów w najniższej warstwie – wszystko rozstrzyga zero albo jeden. Już sama ta zasada daje do myślenia i prowokuje do zastanowienia – jeśli tyle osiągnęliśmy używając tak bardzo radykalnego i zasadniczego systemu, to jak bardzo moglibyśmy poszerzyć możliwości maszyn gdyby ich działanie nie opierało się tylko na dwóch stanach ? Tutaj przychodzą mi też na myśl (i wywołują delikatne drżenie zaniepokojenia) komputery analogowe, o których było wspominane kilkakrotnie na wykładzie. Po ich wprowadzeniu w życie zapewne okazałoby się, że człowiek już jest w bardzo znikomym stopniu „mądrzejszy” od maszyny, a to według mnie byłby początek schyłku ludzkości.
I znów dałam się ponieść rozważaniom zakrawającym na sci-fi, przepraszam.
1) W kilku spośród powyższych komentarzy pojawiła się sugestia co do rozwinięcia następującego sformułowania reporterki: „problemy, których rozwiązaniami są liczby nieobliczalne”.
Wśród czytelników blogu istnieje zatem potrzeba lepszego zrozumienia związku między sferą problemów nieobliczalnych (algorytmicznie nierozwiązywalnych) oraz liczb nieobliczalnych (algorytmicznie niewyznaczalnych).
Muszę przyznać, że wciąż nad tym związkiem przemyśliwuję i nie mam jeszcze jakiejś definitywnej odpowiedzi. W formie wstępnego zarysu takiej odpowiedzi przytoczę jednak niewielki fragment pewnego mojego artykułu, który ukazał się niedawno w czasopiśmie „Filozofia Nauki”.
Cytuję:
<< Gdyby ustalenia Turinga co do nierozwiązywalności pewnych problemów zestawić z (neopitagorejskim) przekonaniem o tym, że „wszystko da się wyrazić jakąś liczbą”, to trzeba by uznać, że istnieją liczby, których nie można obliczyć. Dlaczego? Otóż konsekwentny zwolennik rzeczonego przekonania musi przyjąć, że każdemu problemowi i każdemu jego rozwiązaniu odpowiadają jakieś liczby. Z informatycznego punktu widzenia są to: komputerowy kod problemu oraz kod rozwiązującego go programu (równoważne pewnym liczbom). Od czasu Turinga wiadomo jednak, że istnieją problemy nierozwiązywalne za pomocą jakichkolwiek algorytmów. Wynika stąd, że ich niemożliwym do algorytmicznego uzyskania rozwiązaniom nie daje się przypisać żadnych, równoważnych kodom komputerowym, liczb. Skoro jednak, zgodnie z pitagorejskim przekonaniem, liczby takie istnieją, to muszą one należeć do kategorii nieobliczalnych, czyli niemożliwych do algorytmicznego wyznaczenia. Tak w istocie przedstawia się dostrzeżony przez Alana Turinga związek między sferą problemów nieobliczalnych i liczb nieobliczalnych. Dodajmy koniecznie, że związek ten zasadza się na koncepcji maszyny Turinga; to znaczy: i problemy, i liczby traktuje się jako nierozwiązywalne czy też niewyznaczalne za pomocą automatów Turinga właśnie.>>
A zatem: jeśli przyjąć, że rozwiązanie każdego problemu wyraża się jakąś liczbą (dla informatyków powinno być jasne, że tą liczbą jest kod programu rozwiązującego dany problem, np. kod binarny), to problemom nierozwiązywalnym za pomocą programów dla maszyn cyfrowych odpowiadałyby liczby nieobliczalne. Taka jest moja informatyczno-matematyczna intuicja.
2) Natomiast co do oczekiwanego przez Rezenzenta_X objaśnienia związku między pojęciami logicznej rozstrzygalności i informatycznej obliczalności, to mogę się zobowiązać, że w przyszłości postaram się takiego objaśnienia dostarczyć. To znaczy wtedy, gdy sprawę dostatecznie dobrze przemyślę.
Natomiast teraz, jako dobry punkt odniesienia do takich przemyśleń (nie tylko swoich) zdecydowałem się umieścić w swoim serwisie „Filozofia informatyki” link do bardzo ciekawego artykułu Kazimierza Trzęsickiego o klasycznym (tj. logicznym) zagadnieniu rozstrzygalności. Zainteresowani czytelnicy znajdą w nim sporo informacji o programie i poglądach Davida Hilberta, a także dokonaniach Kurta Godla i Alana Turinga.
Aby przeczytać artykuł, naley przejść do serwisu za pomocą przycisku „Filozofia informatyki” na poziomej belce blogu i kliknąć ostatnią pozycję w dziale lektur.
Właśnie miałem zamiar przeczytać zasugerowany tekst o liczbach nieobliczalnych, ale z obawy, że zamaskuje mi on moje dotychczasowe przemyślenia nad tym zagadnieniem pragnę najpierw wypowiedzieć się na zadany temat a dopiero później (jeśli będzie taka potrzeba) nanieść korektę.
Liczba nieobliczalna już w samej nazwie zawiera esencję swojego problemu. Jest ona małym nieobliczalny dzieckiem, o którym wiemy, że istnieje i śmieje się z naszych nieudolnych prób uchwycenia jego ruchu. Dziecko to skacze z miejsca w inne, i gdy już spodziewamy się, że teraz na pewno nam nie ucieknie – ono wyślizguje się skacząc w zupełnie inną stronę. Przechodząc na język bardziej ścisły wiemy, że liczba nieobliczalna to taka, dla której nie ma żadnego schematu obliczania jej (np jako sumy szeregu czy określonego algorytmu obliczeniowego). Jednakże definicja ta nie dostarcza nam żadnego gotowego przykładu, który w prosty sposób zobrazowałby nam z czym mamy do czynienia. A więc rzucając się na głęboką wodę poszukamy liczby nieobliczalnej. Wiemy, że nie może ona mieć jakiejś charakterystycznej budowy, którą to komputer mógłby zaimplementować do wygenerowania jej. Dlatego posłużymy się tym czego komputer nie posiada (i obawiam się, że nie posiądzie) czyli wyobraźnia. Generując losowo kilka cyfr, np. 391283495430316… nie dajemy możliwości komputerowi znalezienia klucza, którym mógłby po którymś kroku powiedzieć: „dobrze, tyle mi wystarczy – dalej już ci podam liczbę z zadaną dokładnością”. I nawet jeśli w wymienionym ciągu znajdzie się regularność, którą komputer odnajdzie i wypowie swoją kwestię, my odpowiemy mu że na ostatniej pozycji pomylił się, np. o jeden.
Tak więc liczbą nieobliczalną jest każda liczba wygenerowana w sposób czysto losowy. Oczywiście elementem tego zbioru jest liczba omega. Z tym, że tutaj generatorem ciągu liczb jest pewien matematyczny algorytm, który z punktu widzenia programu czytającego te liczby jest w pełni losowy. Jednostka odbierająca wyniki nie jest w stanie na podstawie uzyskanych danych zapewnić przekonanie jaka liczba pojawi się jako następna.
Problemem wartym poruszenia jest również pytanie czy będziemy w stanie obliczać liczby nieobliczalne. Czyli czy na podstawie uzyskanych danych będziemy mogli przewidzieć coś co jest teoretycznie nieprzewidywalne. Moim zdaniem być może z ogromnej grupy liczb nieobliczalnych uda się odsączyć trochę „słabo” losowych liczb.
Jednakże szansa rozwikłania problemu całego zbioru jest moim zdaniem nierozwiązywalna.
Biorąc prosty sympatyczny przykład: niech liczba składa się z numerów kolejnych dni tygodnia kiedy to pan Prezes K. obraża się na kogoś. Komputer zbiera kolejne dane i załóżmy że po miesiącu dostrzega dominację poniedziałku, środy i soboty. Jednakże wysuwając hipotezę że Prezes obrazi się w przyszłym tygodniu w poniedziałek, nie ma żadnej pewności czy tak będzie na pewno (bo Prezes zmienny jest i obraził się we wtorek). I teraz gdyby nawet po wielu latach analizy komputer znalazł ścieżkę generowania wspomnianej liczby – wszyscy wiedzieliby, kiedy Prezes znowu się obrazi i w tym dniu by go po prostu unikali. A wtedy Prezes wspomnianego dnia by się nie obraził i cały program generowania zadanej liczby ległby w gruzach.
Przykład nie był może wysokich lotów, ale pokazuje ilość zmiennych, które utrudniają nam obliczenie liczby nieobliczalnej. I tu warto zauważyć, że liczby nieobliczalnej nie potrafimy obliczyć nie dlatego, że nie mamy ani jednego przepisu jak to zrobić, tylko dlatego, że jest nieskończenie wiele składowych przepisów i wynik zależy od każdego z nich.
Spostrzeżenia p. Arkadego (którego namawiam gorąco do przeczytania dwóch udostępnionych tekstów Chaitina) uświadomiły mi, że zarówno w swoich tekstach o nieobliczalności, jak i w towarzyszących im pytaniach, źle rozłożyłem akcenty.
Po namyśle wydaje mi się, że od zagadnienia nieobliczalności ważniejsze jest zagadnienie obliczalności. O liczbach nieobliczalnych możemy powiedzieć tylko tyle, że na obecnym poziomie rozwoju pojęć matematycznych oraz technik algorytmicznych, nie jesteśmy w stanie znaleźć w nich żadnej regularności, która pozwoliłaby „skompresować” ich niekończenie długi zapis do jakiegoś zapisu skończonego i w dodatku efektywnego obliczeniowo.
I tak np. dla Pitagorejczyków realnie istniejące (bo definiowalne geometrycznie) liczby niewymierne były w pewnym sensie nieobliczalne, bo nie miały w sobie tej regularności, która przysługiwała liczbom wymiernym (dziś powiemy: okresowości rozwinięcia).
Dla Turinga natomiast, z perspektywy znanych mu pojęć (granica ciągu liczbowego, maszyna cyfrowa), nieobliczalne były już tylko te wielkości, których z dowolną zadaną dokładnością (czyli granicznie) w efektywny sposób nie dało się wyznaczyć za pomocą algorytmów dla maszyn cyfrowych.
Innymi słowy i bardziej ogólnie: za sprawą rozszerzania pojęcia obliczalności (a sprzyja temu i rozwój pojęć matematycznych i technik informatycznych) coraz więcej liczb dotychczas nieobliczalnych stawało się obliczalnymi. Pojęcie obliczalności jest więc ważniejsze od pojęcia nieobliczalności. Dzieje się tak, bo ma w sobie pierwiastek pozytywny. Przekształcając czy rozbudowując to pojęcie, poszerzamy zakres naszej wiedzy, uzyskujemy lepszy wgląd w dziedziny dotychczas niepoznawalne.
A co w odkryciu Chaitina jest najważniejsze to fakt, że udało mu się uzyskać kolejny wgląd w dziedzinę aktualnej (to znaczy: turingowskiej) nieobliczalności: zdefiniował liczbę, która za pomocą algorytmów cyfrowych jest niekompresowalna, ale mimo to jest ściśle określona (każdy jej bit musi być taki a taki). Jest niby-losowa, lecz ściśle określona. Być może więc jest losowa tylko w pewien sposób, z punktu widzenia naszych aktualnych pojęć i technik kompresji.
Mimo powyższych stwierdzeń pozostaje oczywiście ważna zagadka – czy przesuwając krok po kroczku granice nieobliczalności, czyli czyniąc nieobliczalne obliczalnym, możemy kiedykolwiek pokonać barierę continuum. Bo okazuje się, że za każdym razem, gdy odkrywamy coś w-nowy-sposób-obliczalnego, to co pozostaje ma moc continuum (jest nieprzeliczalne).
Mam wrażenie, że nasze intuicje – moje i p. Arkadego – są mocno zbieżne. Choć każdy z nas wyraził to samo w nieco innym języku.
(P.S. Bardzo bym prosił, żeby w tym miejscu nie przedstawiał swoich poglądów p. Robakks, bo niebawem odpowiem mu osobno, pod jego ostatnim komentarzem w ramach wpisu o nieobliczalności wg. Chaitina)
Muszę przyznać że wstępna lektura dialogu wzbudziła we mnie znacznie więcej pytań, niż dała odpowiedzi. Sięgnąłem więc do tekstu Chatina. Przykład Omegi zręcznie nakreśla pewne wyobrażenie liczby nieobliczalnej jako takiej. Jeżeli sam miałbym teraz zdefiniować taką liczbę to powiedziałbym że jest to obiekt matematyczny który możemy dokładnie opisać, ale nie możemy go otrzymać na drodze algorytmicznych obliczeń. Mimo posiadania mglistego pojęcia o tym czym jest temat rozważań nadal nie udało mi się znaleźć odpowiedzi na pewne pytania, m. in.:
Czy liczby nieobliczalne mogą być wygenerowane jedynie przez problemy nieobliczalne?
Czy zagadnienia czysto losowe tj. podane przez p. Arkadego (nastrój prezesa K.) możemy postawić na równi z Turingowskim ‘halting problem’? Czy w takim razie te same zadania losowe będą potencjalnymi kandydatami na źródło liczb nieobliczalnych?
Może zastanawialiście się już nad nimi? Jakie są wasze wnioski?
Sam fakt istnienia liczb nieobliczalnych jest bardzo interesujący. Jeszcze ciekawiej zaczyna się robić, kiedy zdamy sobie sprawę że zbiór takich liczb jest nieprzeliczalny. W związku z tym prawie wszystkie liczby rzeczywiste są nieobliczalne i nie istnieje algorytm, który podawałby metodę na ich wyprowadzenie.
Wydawałoby się, że nie jest to takie oczywiste. Jednak jeżeli założylibyśmy, że jest odwrotnie, to okazałoby się że cały świat właśnie stanął do góry nogami. Bylibyśmy w stanie przedstawić prawie wszystkie (w sensie matematycznym) liczby rzeczywiste za pomocą algorytmu. Gdy zdamy sobie sprawę, że nieskończoną liczbę można utożsamiać np. z danymi okazałoby się, że nagle jesteśmy w stanie prawie wszystkie zestawy dowolnie wielkich danych przedstawić jako prosty algorytm. Teraz też jest to możliwe (w końcu rozwinięcie dziesiętne liczby PI zawiera wszystkie możliwe zestawy danych), jednak wyliczenie takiego zestawu stałoby się wielokrotnie prostsze.
To rzeczywiście byłoby bardzo ciekawe, ale zauważmy, że również prawie wszystkie liczby są obliczalne. Zatem jeśli założylibyśmy, że jest odwrotnie, to być może role obliczalność liczb zamieniłyby się miejscami. Spowodowałoby to m.in. konieczność obliczania za każdym razem długiego ciągu cyfr, aby uzyskać małe dane, co znacznie wydłużyłoby czas działania algorytmów. Poza tym algorytmy obliczania dowolnie długich liczb trwałyby dowolnie długo zakładając, co również nie sprzyjałoby uzyskiwaniu tak dużych danych. Jest jeszcze problem przechowywania takich danych – należałoby dysponować dowolnie duża pamięcią, co prowadzi nas do rozważań z fizyki i materii, bo przecież fizycznie mamy ograniczoną ilość miejsca.
Moim zdaniem lepiej by było, gdyby taka odwrotność nie zachodziła, ponieważ zrodziłoby to więcej kłopotów, niż pozytywów