{"id":4523,"date":"2013-04-07T19:33:00","date_gmt":"2013-04-07T19:33:00","guid":{"rendered":"http:\/\/blog.marciszewski.eu\/?p=4523"},"modified":"2025-09-23T11:09:48","modified_gmt":"2025-09-23T09:09:48","slug":"chaitin-o-nieobliczalnosci","status":"publish","type":"post","link":"https:\/\/marciszewski.eu\/?p=4523","title":{"rendered":"Chaitin o nieobliczalno\u015bci"},"content":{"rendered":"

Kolejny wpis z cyklu \u201ew miar\u0119 zrozumiale o zagadnieniu nieobliczalno\u015bci<\/em>, :)\u201d stanowi zach\u0119t\u0119 do przeczytania popularnego artyku\u0142u G. Chaitina p.t. \u201eOmega and why maths has no TOEs<\/a>\u201d.
\nZach\u0119t\u0119 t\u0119 m\u00f3g\u0142bym do\u0142\u0105czy\u0107 do dyskusji toczonej w ramach poprzedniego wpisu, ale ze wzgl\u0119du na wyj\u0105tkowy status autora (wszak to on dostarczy\u0142 pierwszego przyk\u0142adu liczby nieobliczalnej) uzna\u0142em, \u017ce lepiej b\u0119dzie sporz\u0105dzi\u0107 osobny wpis.
\nW polecanym przeze mnie tek\u015bcie znajdziemy nie tylko bardzo przyst\u0119pne om\u00f3wienie zagadkowej liczby Omega, ale tak\u017ce pouczaj\u0105cy opis drogi – wytyczonej m.in. przez Leibniza i G\u00f6dla – kt\u00f3ra doprowadzi\u0142a Chaitina do odkrycia Omegi.<\/p>\n

\u017bycz\u0105c wszystkim ciekawej i owocnej lektury, chcia\u0142bym poprzedzi\u0107 j\u0105 kilkoma akapitami wst\u0119pu.<\/p>\n

Ot\u00f3\u017c prezentuj\u0105c swoj\u0105 liczb\u0119, Chaitin k\u0142adzie nacisk na fakt, \u017ce jest ona nieredukowalna<\/strong> do \u017cadnego algorytmu (dla maszyn cyfrowych) — to znaczy nie istnieje \u017caden sko\u0144czony algorytm cyfrowy\/turingowski, kt\u00f3ry by\u0142by w stanie, szybko lub wolno, wyznacza\u0107 kolejne cyfry jej rozwini\u0119cia dziesi\u0119tnego (bo jest to liczba z przedzia\u0142u (0,1)). A zatem, cho\u0107 jest owa liczba precyzyjnie zdefiniowana i jej kolejne cyfry binarne s\u0105 \u015bci\u015ble okre\u015blone (np. na miejscu 10-tym musi sta\u0107 albo 0, albo 1 \u2013 niezale\u017cnie od czyjego\u015b widzimisi\u0119), to nie istnieje algorytm, kt\u00f3ry dostarcza\u0142by krok po kroku wiedzy o dok\u0142adnych warto\u015bciach tych cyfr.
\nInnymi s\u0142owy, gdyby jaki\u015b \u201eponad-algorytmiczny, boski umys\u0142\u201d zna\u0142 liczb\u0119 Omega, to musia\u0142by wyjawi\u0107 j\u0105 nam w ca\u0142o\u015bci<\/strong>, natomiast nie by\u0142by w stanie dostarczy\u0107 zwi\u0119z\u0142ej algorytmicznej regu\u0142y opisuj\u0105cej j\u0105 w sko\u0144czony spos\u00f3b.
\nW przypadku innych nieregularnych i niesko\u0144czonych liczb, jak np. \u201epi\u201d czy \u201epierwiastek z dw\u00f3ch\u201d, regu\u0142y takie istniej\u0105 (Chaitin przedstawia tak\u0105 zwi\u0119z\u0142\u0105 algorytmiczn\u0105 regu\u0142\u0119 dla pierwiastka z dw\u00f3ch), natomiast w przypadki Omegi NIE. Dzieje si\u0119 tak, poniewa\u017c jest ona zdefiniowana w odniesieniu do nierozstrzygalnego algorytmicznie problemu stopu<\/strong> maszyny Turinga – m\u00f3wi\u0105c kr\u00f3tko: je\u015bli kolejny badany program (maszyna Turinga) zatrzymuje si\u0119, to pewien bit Omegi przyjmuje warto\u015b\u0107 1, a je\u015bli program nie zatrzymuje si\u0119, to bit ten przyjmuje warto\u015b\u0107 0 (s\u0119k w tym, \u017ce cho\u0107 jest \u015bci\u015ble okre\u015blone, \u017ce pewna maszyna dla pewnych danych zatrzyma si\u0119 lub nie, to nie ma og\u00f3lnego algorytmu, kt\u00f3ry to rozstrzygnie).
\nId\u0105c dalej, poniewa\u017c liczba Omega jest z definicji algorytmicznie niewyznaczalna, to musi by\u0107 skrajnie losowa<\/strong> (bo gdyby tak\u0105 nie by\u0142a, to da\u0142oby si\u0119 znale\u017a\u0107 jak\u0105\u015b algorytmiczn\u0105 formu\u0142\u0119 kompresji – kt\u00f3ra opisywa\u0142aby regularno\u015b\u0107 nast\u0119pstwa jej zer i jedynek).<\/p>\n

O tym wszystkim autor artyku\u0142u kompetentnie pisze \u2013 popieraj\u0105c swoje wyja\u015bnienia przyk\u0142adami.<\/p>\n

Nie pisze natomiast o tym, \u017ce jego odkrycie, tj. \u015bcis\u0142e uj\u0119cie pewnego podzbioru liczb nieobliczalnych (bo tak naprawd\u0119 liczb Omega jest wiele), stanowi najnowszy w\u0105tek pewnej d\u0142ugiej historii \u201ematematycznego wgl\u0105du\u201d w dziedzin\u0119 liczb niewymiernych<\/strong>.
\nHistoria ta zaczyna si\u0119 w VI wieku p.n.e wraz z odkryciem niewymierno\u015bci przez Pitagorejczyk\u00f3w (pod postaci\u0105 pierwiastka z dw\u00f3ch), nabiera rumie\u0144c\u00f3w wraz z ustaleniem przez Cantora nieprzeliczalno\u015bci<\/strong> zbioru liczb niewymiernych, nabiera tempa wraz z odkrywaniem kolejnych, dost\u0119pnych obliczeniowo, klas niewymierno\u015bci (jak liczby algebraiczne czy liczby Louisville\u2019a), a osi\u0105ga apogeum wtedy, gdy Alan Turing podaje \u015bcis\u0142\u0105 definicj\u0119 obliczalno\u015bci i udowadnia, \u017ce klasa liczb obliczalnych, czyli algorytmicznie opisywalnych, jest zaledwie przeliczalna. Poza ni\u0105 pozostaje za\u015b continuum nieobliczalno\u015bci<\/strong>.
\nOdkrycie Chaitina daje w owo continuum nowy zaskakuj\u0105cy wgl\u0105d — ujmuje bowiem \u015bci\u015ble co\u015b, co wymyka si\u0119 cyfrowym algorytmom. Niczego jednak nie zamyka — bo owo nowe „chaitinowskie co\u015b” stanowi zn\u00f3w tylko fragment continuum.<\/p>\n

Tyle tytu\u0142em przyd\u0142ugiego wst\u0119pu, kt\u00f3ry trzeba potraktowa\u0107 jako moj\u0105 autorsk\u0105 interpretacj\u0119<\/strong> tekstu (i odkry\u0107) Chaitina. Jeszcze raz \u017cycz\u0119 owocnej lektury.
\nA je\u015bli kto\u015b zechce podzieli\u0107 si\u0119 swoimi wra\u017ceniami i swoimi interpretacjami, to jest na to miejsce…<\/p>\n

Pawe\u0142 Stacewicz.<\/p>\n","protected":false},"excerpt":{"rendered":"

Kolejny wpis z cyklu \u201ew miar\u0119 zrozumiale o zagadnieniu nieobliczalno\u015bci, :)\u201d stanowi zach\u0119t\u0119 do przeczytania popularnego artyku\u0142u G. Chaitina p.t. \u201eOmega and why maths has no TOEs\u201d. Zach\u0119t\u0119 t\u0119 m\u00f3g\u0142bym do\u0142\u0105czy\u0107 do dyskusji toczonej w ramach poprzedniego wpisu, ale ze … Czytaj dalej →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,20,42,8],"tags":[],"class_list":["post-4523","post","type-post","status-publish","format-standard","hentry","category-dydaktyka","category-filozofia-informatyki","category-filoz-nauki","category-informatyzm"],"_links":{"self":[{"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts\/4523","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4523"}],"version-history":[{"count":9,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts\/4523\/revisions"}],"predecessor-version":[{"id":12742,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts\/4523\/revisions\/12742"}],"wp:attachment":[{"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4523"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}