Chaitin o nieobliczalności

Kolejny wpis z cyklu „w miarę zrozumiale o zagadnieniu nieobliczalności, :)” stanowi zachętę do przeczytania popularnego artykułu G. Chaitina p.t. „Omega and why maths has no TOEs”.
Zachętę tę mógłbym dołączyć do dyskusji toczonej w ramach poprzedniego wpisu, ale ze względu na wyjątkowy status autora (wszak to on dostarczył pierwszego przykładu liczby nieobliczalnej) uznałem, że lepiej będzie sporządzić osobny wpis.
W polecanym przeze mnie tekście znajdziemy nie tylko bardzo przystępne omówienie zagadkowej liczby Omega, ale także pouczający opis drogi – wytyczonej m.in. przez Leibniza i Gödla – która doprowadziła Chaitina do odkrycia Omegi.

Życząc wszystkim ciekawej i owocnej lektury, chciałbym poprzedzić ją kilkoma akapitami wstępu.

Otóż prezentując swoją liczbę, Chaitin kładzie nacisk na fakt, że jest ona nieredukowalna do żadnego algorytmu (dla maszyn cyfrowych) — to znaczy nie istnieje żaden skończony algorytm cyfrowy/turingowski, który byłby w stanie, szybko lub wolno, wyznaczać kolejne cyfry jej rozwinięcia dziesiętnego (bo jest to liczba z przedziału (0,1)). A zatem, choć jest owa liczba precyzyjnie zdefiniowana i jej kolejne cyfry binarne są ściśle określone (np. na miejscu 10-tym musi stać albo 0, albo 1 – niezależnie od czyjegoś widzimisię), to nie istnieje algorytm, który dostarczałby krok po kroku wiedzy o dokładnych wartościach tych cyfr.
Innymi słowy, gdyby jakiś „ponad-algorytmiczny, boski umysł” znał liczbę Omega, to musiałby wyjawić ją nam w całości, natomiast nie byłby w stanie dostarczyć zwięzłej algorytmicznej reguły opisującej ją w skończony sposób.
W przypadku innych nieregularnych i nieskończonych liczb, jak np. „pi” czy „pierwiastek z dwóch”, reguły takie istnieją (Chaitin przedstawia taką zwięzłą algorytmiczną regułę dla pierwiastka z dwóch), natomiast w przypadki Omegi NIE. Dzieje się tak, ponieważ jest ona zdefiniowana w odniesieniu do nierozstrzygalnego algorytmicznie problemu stopu maszyny Turinga – mówiąc krótko: jeśli kolejny badany program (maszyna Turinga) zatrzymuje się, to pewien bit Omegi przyjmuje wartość 1, a jeśli program nie zatrzymuje się, to bit ten przyjmuje wartość 0 (sęk w tym, że choć jest ściśle określone, że pewna maszyna dla pewnych danych zatrzyma się lub nie, to nie ma ogólnego algorytmu, który to rozstrzygnie).
Idąc dalej, ponieważ liczba Omega jest z definicji algorytmicznie niewyznaczalna, to musi być skrajnie losowa (bo gdyby taką nie była, to dałoby się znaleźć jakąś algorytmiczną formułę kompresji – która opisywałaby regularność następstwa jej zer i jedynek).

O tym wszystkim autor artykułu kompetentnie pisze – popierając swoje wyjaśnienia przykładami.

Nie pisze natomiast o tym, że jego odkrycie, tj. ścisłe ujęcie pewnego podzbioru liczb nieobliczalnych (bo tak naprawdę liczb Omega jest wiele), stanowi najnowszy wątek pewnej długiej historii „matematycznego wglądu” w dziedzinę liczb niewymiernych.
Historia ta zaczyna się w VI wieku p.n.e wraz z odkryciem niewymierności przez Pitagorejczyków (pod postacią pierwiastka z dwóch), nabiera rumieńców wraz z ustaleniem przez Cantora nieprzeliczalności zbioru liczb niewymiernych, nabiera tempa wraz z odkrywaniem kolejnych, dostępnych obliczeniowo, klas niewymierności (jak liczby algebraiczne czy liczby Louisville’a), a osiąga apogeum wtedy, gdy Alan Turing podaje ścisłą definicję obliczalności i udowadnia, że klasa liczb obliczalnych, czyli algorytmicznie opisywalnych, jest zaledwie przeliczalna. Poza nią pozostaje zaś continuum nieobliczalności.
Odkrycie Chaitina daje w owo continuum nowy zaskakujący wgląd — ujmuje bowiem ściśle coś, co wymyka się cyfrowym algorytmom. Niczego jednak nie zamyka — bo owo nowe “chaitinowskie coś” stanowi znów tylko fragment continuum.

Tyle tytułem przydługiego wstępu, który trzeba potraktować jako moją autorską interpretację tekstu (i odkryć) Chaitina. Jeszcze raz życzę owocnej lektury.
A jeśli ktoś zechce podzielić się swoimi wrażeniami i swoimi interpretacjami, to jest na to miejsce…

Paweł Stacewicz.

Ten wpis został opublikowany w kategorii Dydaktyka logiki i filozofii, Filozofia informatyki, Filozofia nauki, Światopogląd informatyczny. Dodaj zakładkę do bezpośredniego odnośnika.

3 Responses to Chaitin o nieobliczalności

  1. Robakks pisze:

    Otóż prezentując swoją liczbę, Chaitin kładzie nacisk na fakt, że jest ona nieredukowalna do żadnego algorytmu (dla maszyn cyfrowych) — to znaczy nie istnieje żaden skończony algorytm cyfrowy/turingowski, który byłby w stanie, szybko lub wolno, wyznaczać kolejne cyfry jej rozwinięcia dziesiętnego (bo jest to liczba z przedziału (0,1)).

    Ja to zdanie bym uściślił w oparciu o przykład.
    Do 1889 roku prawdziwe było twierdzenie: “nie istnieje wieża Eifla zbudowana na Wystawę Światową w Paryżu”, ale po tym roku do dnia dzisiejszego takie twierdzenie jest niezgodne z rzeczywistością, bo wieża Eifla JEST.

    Analogicznie cytowane zdanie IMHO powinno być doposażone o klauzulę teraźniejszości:
    nie istnieje WSPÓŁCZEŚNIE żaden skończony algorytm cyfrowy/turingowski, który byłby w stanie, szybko lub wolno, wyznaczać kolejne cyfry jej rozwinięcia dziesiętnego (bo jest to liczba z przedziału (0,1))

    A dlaczego nie istnieje?
    Ano dlatego, że WSPÓŁCZEŚNIE ludzie zajmujący się matematyką nie potrafią nadać nazw wszystkim punktom z przedziału (0,1).

    A dlaczego nie potrafią?
    Ano dlatego, bo nie badają obiektów matematycznych (pewniki), lecz kreują założenia (aksjomaty). Gdy wymyśla się aksjomaty mające na celu wykazać, że czegoś się nie da – to z takiego systemu aksjomatycznego siłą rzeczy będzie wynikać, że tego się nie da.

    Czy tak zawsze musi być w NAUCE?
    Moim zdaniem nie musi. Jeśli w środowisku naukowców powstaną takie trendy, że aksjomaty będą mogły być wykluczane z nauki przez pewniki
    -to-
    powstaną warunki do tego, by odkryte przez Chaitina liczby nieobliczalne stały się zwykłymi jednoznacznie określonymi liczbami rzeczywistymi. Zniknie również problem STOPU, bo takiego problemu nie ma: Achilles dogania żółwia, a ułamki okresowe choć mają pętlę, to są ścisłe np. 0,(123) .
    ۞

    • Paweł Stacewicz pisze:

      Powyższy komentarz jest tego rodzaju, że niemal każde zdanie wzbudza we mnie reakcję polemiczną – co zresztą komponuje się dobrze z tytułem blogu: „Polemiki i rozmówki…”

      1) Cytowanego zdania o „nieistnieniu algorytmu cyfrowego wyznaczającego wszystkie bity Omegi” nie można uzupełnić o klauzulę teraźniejszości.
      Jeśli godzimy się na daną przez Turinga definicję obliczalności (a skoro p. Robakks tylko uzupełnia moje zdanie, a nie odrzuca pojęcia cyfrowej obliczalności – to godzi się na nią), to musimy przyjąć dowód istnienia liczb nieobliczalnych., czyli zasadniczą niemożność wyznaczania pewnych wielkości za pomocą maszyn Turinga.
      Możemy przypuszczać co najwyżej, że (o czym p. Robakks jednak nie pisze),ze istnieją algorytmy innego rodzaju (nie cyfrowe, to znaczy nie redukowalne do maszyn Turinga), które zapewnią nam dostęp do liczb cyfrowo nieobliczalnych.

      2) Na gruncie definicji obliczalności w sensie Turinga liczba 0,(123) jest jak najbardziej obliczalna (i nieskończoność, czy też nieskończona pętla nie ma tu nic do rzeczy). Zapis (123) określa pewną regułę obliczania tej liczby w systemie dziesiętnym – obliczania z coraz lepszą dokładnością.

      3) Liczby Omega są jednoznacznie określonymi liczbami rzeczywistymi (nie muszą się takimi stawać, bo takimi są).
      Cały ich „urok” polega na tym, że mimo faktu, iż są zupełnie jednoznacznie określone, nie możemy obliczyć ich wszystkich bitów.

      4) Nie wydaje mi się, żeby treść takich czy innych aksjomatów (takiej czy innej teorii) prowadziła w sposób oczywisty do wniosku o nie zachodzeniu pewnych faktów (np. niemożliwości obliczenia za pomocą maszyn Turinga pewnych liczb). Gdyby tak było, nikt by nie musiał się trudzić wynajdywaniem dowodów lub wykazywaniem, że dla pewnych faktów one nie istnieją. Przykładowo; twierdzenie Godla było dla współczesnych Godlowi matematyków szokiem, a nie odkryciem jakiejś oczywistości. Zrozumienie dowodu tego twierdzenia też nie było łatwe.

      5) Nie za bardzo rozumiem, na czym w ujęciu p. Robakksa miałby polegać różnica między aksjomatem a pewnikiem. Nie zostało to wyjaśnione.

  2. Harriet pisze:

    Bardzo dziękuję za ten wpis, artykuł przeczytałam i naprawdę mnie wciągnął. Jak na zawiłe matematyczno – filozoficzne rozważania jest rzeczywiście bardzo przystępnie i ciekawie napisany. Szczególnie interesujące są wnioski w ostatnim akapicie. Rzeczywiście, wynalezienie liczby Omega i twierdzenie Turinga na temat warunku stopu pozwala się zastanowić, jak długo matematyce będzie wystarczać dodawanie nowych twierdzeń na podstawie dowodów. Wydaje się, że jeśli nie zostaną zaproponowane i zatwierdzone nowe aksjomaty, trafne i szczegółowo opisane ale jednak nie poparte konkretnym dowodem, to rozwój matematyki może w pewnym momencie bardzo zwolnić lub wręcz zatrzymać się. Dlatego też rozważania Chaitina pozwalają z nadzieją patrzeć w przyszłość i oczekiwać nowych, innowacyjnych sposobów opisu świata, co jest niezbędne by wciąż w tak szaleńczym tempie pchać postęp do przodu.

Skomentuj Robakks Anuluj pisanie odpowiedzi

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *