{"id":2395,"date":"2012-10-24T18:34:50","date_gmt":"2012-10-24T18:34:50","guid":{"rendered":"http:\/\/blog.marciszewski.eu\/?p=2395"},"modified":"2025-09-23T11:17:27","modified_gmt":"2025-09-23T09:17:27","slug":"nieobliczalni-i-nieobliczalne","status":"publish","type":"post","link":"https:\/\/marciszewski.eu\/?p=2395","title":{"rendered":"Nieobliczalni i nieobliczalne"},"content":{"rendered":"

Przygotowuj\u0105c wyk\u0142ad dla m\u0142odzie\u017cy szkolnej p.t. \u201eCzy komputery mog\u0105 by\u0107 nieobliczalne?<\/em>\u201d, pomy\u015bla\u0142em sobie, \u017ce warto zagai\u0107 \u00f3w temat w blogu.
\nZagai\u0107 tak, by ukaza\u0107 obecny w j\u0119zyku polskim zwi\u0105zek mi\u0119dzy nieobliczalno\u015bci\u0105<\/em> ludzi i komputerowych algorytm\u00f3w.<\/p>\n

Zacznijmy od ludzi. W odniesieniu do nich nieobliczalny to tyle co nieprzewidywalny<\/em> \u2013 osobnik tak jako\u015b fizycznie i psychicznie uwarunkowany (zwichrowany?), \u017ce trudno w danej sytuacji dociec, co pomy\u015bli, co zrobi, jak si\u0119 zachowa etc. Innymi s\u0142owy, mianem \u201enieobliczalnego\u201d vel \u201enieprzewidywalnego\u201d nazwiemy ka\u017cdego orygina\u0142a, ekscentryka, dewianta czy szale\u0144ca, ale tak\u017ce \u2013 tu uwaga na pozytywny wyd\u017awi\u0119k nieobliczalno\u015bci \u2013 ka\u017cdego tw\u00f3rczego naukowca czy wr\u0119cz geniusza.
\nMamy zatem dwa jakby oblicza ludzkiej nieobliczalno\u015bci: negatywne \u2013 w\u0142a\u015bciwe gro\u017anym dla otoczenia szale\u0144com, oraz pozytywne \u2013 w\u0142a\u015bciwe bezcennym dla ludzko\u015bci tw\u00f3rcom i geniuszom.<\/p>\n

Je\u015bli skupimy uwag\u0119 na tych drugich, to ujrzymy kolejne, tym razem specjalistyczne, znaczenie terminu \u201enieobliczalno\u015b\u0107\u201d. Powo\u0142ali je do \u017cycia geniusze w\u0142a\u015bnie, to znaczy wyj\u0105tkowo tw\u00f3rczy matematycy XX-wieczni, w tym Kurt G\u00f6del, Emil Post i Alan Turing.
\nIch niezwykle donios\u0142e dla nauki odkrycie polega\u0142o na dostrze\u017ceniu problem\u00f3w, kt\u00f3rych nie spos\u00f3b rozwi\u0105za\u0107 algorytmicznie, za pomoc\u0105 algorytm\u00f3w dla maszyn cyfrowych. I to w\u0142a\u015bnie tego typu zagadnienia nazwano nieobliczalnymi<\/em>.<\/p>\n

W formie ilustracji owej nie-ludzkiej, bo matematyczno-informatycznej dziedziny nieobliczalno\u015bci, sformu\u0142ujmy jedno z najwa\u017cniejszych zagadnie\u0144 nieobliczalnych, tzw. problem stopu<\/em>.
\nOto on: \u201eCzy istnieje uniwersalny algorytm-wyrocznia, kt\u00f3ry analizuj\u0105c symboliczne zapisy innych algorytm\u00f3w oraz ich dane wej\u015bciowe, by\u0142by w stanie odpowiedzie\u0107 jednoznacznie, i to w ka\u017cdym analizowanym przypadku, czy dany algorytm dla takich-a-takich danych wej\u015bciowych zatrzyma si\u0119, czy te\u017c b\u0119dzie przetwarza\u0142 dane w niesko\u0144czono\u015b\u0107?<\/em>\u201d.
\nPoniewa\u017c algorytmu takiego nie ma (co udowodni\u0142 wzmiankowany wy\u017cej Alan Turing), problem \u00f3w nale\u017cy do ekskluzywnego grona nieobliczalnych.<\/p>\n

Czy jednak wszystkie problematyczne dla komputer\u00f3w problemy nale\u017c\u0105 do naszego ekskluzywnego zbioru?
\nOkazuje si\u0119, \u017ce NIE. Istnieje bowiem inna, i to bardzo liczna, grupa zagadnie\u0144, kt\u00f3re cho\u0107 mog\u0105 zosta\u0107 rozwi\u0105zane za pomoc\u0105 jakich\u015b algorytm\u00f3w (ju\u017c znanych lub jeszcze nie), to potrzeba na to astronomicznie du\u017co czasu. M\u00f3wi\u0105c dok\u0142adniej: gdy rozmiar danych wej\u015bciowych dla takich problem\u00f3w ro\u015bnie, to czas potrzebny na ich algorytmiczne rozwi\u0105zanie ro\u015bnie o wiele szybciej, np. wyk\u0142adniczo<\/em> (tak jak funkcja 2n<\/sup>) lub silniowo<\/em> (tak jak funkcja n!).<\/p>\n

Jeden ze wzmiankowanych problem\u00f3w wydaje si\u0119 ca\u0142kiem banalny: \u201eSprawdzi\u0107, czy przy jakim\u015b warto\u015bciowaniu zmiennych dana formu\u0142a logicznego rachunku zda\u0144 jest prawdziwa<\/em>\u201d. Mimo jego koncepcyjnej prostoty udowodniono, \u017ce ma on z\u0142o\u017cono\u015b\u0107 wyk\u0142adnicz\u0105, to znaczy najbardziej pesymistyczny czas rozwi\u0105zania ro\u015bnie wyk\u0142adniczo wraz ze wzrostem liczby zmiennych w zdaniu. Problemy tego typu mo\u017cemy nazwa\u0107 trudno-obliczalnymi<\/em>.<\/p>\n

I teraz w\u0142a\u015bnie, znaj\u0105c ju\u017c obydwa poj\u0119cia nieobliczalno\u015bci \u2013 ludzkie (szale\u0144cy i geniusze) oraz komputerowe (trudne problemy algorytmiczne) \u2013 mo\u017cemy przyjrze\u0107 si\u0119 bli\u017cej pytaniu o to \u201eCzy komputery mog\u0105 by\u0107 nieobliczalne?<\/em>\u201d.
\nOt\u00f3\u017c moim zdaniem MOG\u0104, a przes\u0105dza o tym fakt istnienia problem\u00f3w nieobliczalnych i trudno-obliczalnych.<\/p>\n

Za\u0142\u00f3\u017cmy bowiem, \u017ce komputer staje przed konieczno\u015bci\u0105 rozwi\u0105zania pewnego konkretnego problemu, kt\u00f3ry jest jak\u0105\u015b szczeg\u00f3ln\u0105 wersj\u0105 og\u00f3lnie znanego problemu nieobliczalnego lub trudno-obliczalnego (np. okre\u015blenia warunk\u00f3w prawdziwo\u015bci formu\u0142y rachunku zda\u0144). Poniewa\u017c nie istnieje efektywny algorytm rozwi\u0105zania takiego problemu w ka\u017cdym konkretnym przypadku, to komputer nie mo\u017ce z niego skorzysta\u0107, a skoro tak, to mo\u017ce dzia\u0142a\u0107 na dwa sposoby: albo stosowa\u0107 tak lub inaczej zorganizowan\u0105 metod\u0119 pr\u00f3b i b\u0142\u0119d\u00f3w<\/em>, albo stosowa\u0107 jak\u0105\u015b strategi\u0119 heurystyczn\u0105<\/em> (kt\u00f3ra w wielu sytuacjach skutkuje, aczkolwiek nie zawsze).
\nObydwie metody kryj\u0105 w sobie \u201eziarno niepewno\u015bci\u201d. Co wi\u0119cej, wiele faktycznie realizowanych metod tego typu zale\u017cy od wybor\u00f3w losowych<\/em> (ma wi\u0119c charakter niedeterministyczny). Losowo\u015b\u0107 z kolei poci\u0105ga za sob\u0105 nieobliczalno\u015b\u0107 \u2013 po prostu nie wiemy dok\u0142adnie, jak steruj\u0105cy komputerem algorytm si\u0119 zachowa, kt\u00f3r\u0105 \u015bcie\u017ck\u0105 pod\u0105\u017cy, jakie rozwi\u0105zanie znajdzie. Algorytm zatem, a w rezultacie i realizuj\u0105cy go komputer, nie b\u0119dzie z naszego punktu widzenia obliczalny.<\/p>\n","protected":false},"excerpt":{"rendered":"

Przygotowuj\u0105c wyk\u0142ad dla m\u0142odzie\u017cy szkolnej p.t. \u201eCzy komputery mog\u0105 by\u0107 nieobliczalne?\u201d, pomy\u015bla\u0142em sobie, \u017ce warto zagai\u0107 \u00f3w temat w blogu. Zagai\u0107 tak, by ukaza\u0107 obecny w j\u0119zyku polskim zwi\u0105zek mi\u0119dzy nieobliczalno\u015bci\u0105 ludzi i komputerowych algorytm\u00f3w. Zacznijmy od ludzi. W odniesieniu … 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":[20,8],"tags":[],"class_list":["post-2395","post","type-post","status-publish","format-standard","hentry","category-filozofia-informatyki","category-informatyzm"],"_links":{"self":[{"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts\/2395","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=2395"}],"version-history":[{"count":14,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts\/2395\/revisions"}],"predecessor-version":[{"id":12765,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=\/wp\/v2\/posts\/2395\/revisions\/12765"}],"wp:attachment":[{"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2395"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2395"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/marciszewski.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2395"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}