{"id":3398,"date":"2014-01-21T07:34:46","date_gmt":"2014-01-21T06:34:46","guid":{"rendered":"http:\/\/naukowy.blog.polityka.pl\/?p=3398"},"modified":"2014-01-21T07:34:46","modified_gmt":"2014-01-21T06:34:46","slug":"czekajac-bez-konca","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/naukowy\/2014\/01\/21\/czekajac-bez-konca\/","title":{"rendered":"Czekaj\u0105c bez ko\u0144ca"},"content":{"rendered":"<p><strong><a href=\"\/wp-content\/uploads\/2014\/01\/Turing-statue-Bletchley_11.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-large wp-image-3399\" title=\"Turing-statue-Bletchley_11\" src=\"\/wp-content\/uploads\/2014\/01\/Turing-statue-Bletchley_11-678x1024.jpg\" alt=\"Pomink Alana Turinga w Bletchley \" width=\"620\" height=\"936\" srcset=\"\/naukowy\/wp-content\/uploads\/2014\/01\/Turing-statue-Bletchley_11-678x1024.jpg 678w, \/naukowy\/wp-content\/uploads\/2014\/01\/Turing-statue-Bletchley_11-198x300.jpg 198w\" sizes=\"(max-width: 620px) 100vw, 620px\" \/><\/a><br \/>\n<\/strong><\/p>\n<p>Jak obiecali\u015bmy, tak robimy: dzi\u015b kolejny tekst o braku komunikatu traktowanym jako komunikat.<\/p>\n<p>Tym razem mowa b\u0119dzie o teorii obliczalno\u015bci, kt\u00f3ra jest dziedzin\u0105 matematyki. To istotne zastrze\u017cenie, bo terminologia i spos\u00f3b opisu poni\u017cej mog\u0105 sugerowa\u0107, \u017ce chodzi o informatyk\u0119. Tymczasem to, o czym opowiem, to twierdzenia matematyczne, kt\u00f3re niew\u0105tpliwie nale\u017c\u0105 do teorii informatyki, ale na praktyk\u0119 informatyczn\u0105 nie maj\u0105 wi\u0119kszego wp\u0142ywu.<\/p>\n<p>O poj\u0119ciach z zakresu obliczalno\u015bci m\u00f3wi si\u0119, odwo\u0142uj\u0105c do jakiego\u015b formalnego systemu zapisu algorytm\u00f3w, najcz\u0119\u015bciej do maszyny Turinga. Ja zdecydowa\u0142em si\u0119 zrobi\u0107 inaczej, bo nie planuj\u0119 przeprowadza\u0107 \u017cadnych dowod\u00f3w, a b\u0119d\u0119, jak to si\u0119 w moich kr\u0119gach m\u00f3wi, &#8222;macha\u0142 r\u0119kami&#8221;. Jednak to, co opisz\u0119 poni\u017cej odnosi si\u0119 jednakowo do w\u0142a\u015bciwie ka\u017cdej formalizacji poj\u0119cia algorytmu.<\/p>\n<p>Pos\u0142u\u017c\u0119 si\u0119 (cokolwiek umownym) poj\u0119ciem <em>program\u00f3w<\/em>. Nale\u017cy przez nie rozumie\u0107 programy, napisane w jakim\u015b ustalonym, ale bli\u017cej niesprecyzowanym j\u0119zyku programowania, uruchamiane na idealnym, nieograniczonym komputerze, kt\u00f3remu nigdy nie zabraknie pami\u0119ci operacyjnej, miejsca na dysku, czasu na obliczenia ani pr\u0105du do ich wykonania. Co wi\u0119cej, programista komputera jest r\u00f3wnie\u017c idealny, nigdy nie robi b\u0142\u0119d\u00f3w w swoich programach ani nigdy mu nie brakuje cierpliwo\u015bci, \u017ceby czeka\u0107 na wyniki oblicze\u0144.<\/p>\n<p>Nast\u0119pnie trzeba zastanowi\u0107 si\u0119, jakie problemy b\u0119dzie ten nasz idealny komputer rozwi\u0105zywa\u0142. Wybieramy do tego <em>problemy decyzyjne<\/em>. Polegaj\u0105 one na sprawdzaniu pewnej konkretnej w\u0142asno\u015bci dla ka\u017cdego mo\u017cliwego pliku z danymi tekstowymi (sko\u0144czonej wielko\u015bci). Je\u015bli plik ma t\u0119 w\u0142asno\u015b\u0107, nale\u017cy odpowiedzie\u0107 &#8222;TAK&#8221;, je\u015bli jej nie ma, nale\u017cy odpowiedzie\u0107 &#8222;NIE&#8221;. Przyk\u0142adami takich w\u0142asno\u015bci mog\u0105 by\u0107:<\/p>\n<ul>\n<li>Plik zmierzony w bajtach ma rozmiar, kt\u00f3ry jest liczb\u0105 pierwsz\u0105<\/li>\n<li> Wszystkie s\u0142owa w pliku sa poprawnie odmienionymi formami s\u0142\u00f3w z pierwszego wydania &#8222;S\u0142ownika poprawnej polszczyzny&#8221; Wydawnictwa PWN<\/li>\n<li>Plik zawiera poprawny sk\u0142adniowo program dla naszego idealnego komputera<\/li>\n<li>Plik zawiera list\u0119 r\u00f3\u017cnych miast wraz z wszystkimi odleg\u0142o\u015bciami drogowymi pomi\u0119dzy nimi, w dodatku ustawion\u0105 w takiej kolejno\u015bci, \u017ceby objechanie ich wszytkich w tej w\u0142a\u015bnie kolejno\u015bci dawa\u0142o najkr\u00f3tsz\u0105 mo\u017cliw\u0105 tras\u0119<\/li>\n<li>Plik zawiera wz\u00f3r r\u00f3wnania wielomianowego o wielu zmiennych, kt\u00f3re ma rozwi\u0105zanie z\u0142o\u017cone z liczb rzeczywistych<\/li>\n<\/ul>\n<p>Dla ka\u017cdego z nich programista mo\u017ce napisa\u0107 program, kt\u00f3rego nast\u0119pnie u\u017cywa nast\u0119puj\u0105co: na dysk swojego idealnego komputera \u0142aduje plik, co do kt\u00f3rego ma by\u0107 podj\u0119ta decyzja i uruchamia program, kt\u00f3ry mo\u017ce da\u0107 tylko dwa mo\u017cliwe wyniki:<\/p>\n<ol>\n<li>zatrzyma\u0107 si\u0119 i odpowiedzie\u0107 &#8222;TAK&#8221;,<\/li>\n<li>zatrzyma\u0107 si\u0119 i odpowiedzie\u0107 &#8222;NIE&#8221;.<\/li>\n<\/ol>\n<p>Taki program w\u00f3wczas rozstrzyga ten problem decyzyjny, a my m\u00f3wimy, \u017ce jest on <em>rozstrzygalny<\/em>. Wszystkie pi\u0119\u0107 przyk\u0142adowych problem\u00f3w powy\u017cej jest rozstrzygalnych.<\/p>\n<p>Mo\u017cemy jednak powo\u0142a\u0107 si\u0119 na paradygmat &#8222;brak komunikatu to te\u017c komunikat&#8221; i zgodzi\u0107 si\u0119 na bardziej liberalne warunki dzia\u0142ania programu. Ot\u00f3\u017c dopuszczamy teraz trzy mo\u017cliwe wyniki dzia\u0142ania programu:<\/p>\n<ol>\n<li>mo\u017ce zatrzyma\u0107 si\u0119 i odpowiedzie\u0107 &#8222;TAK&#8221;,<\/li>\n<li>mo\u017ce zatrzyma\u0107 si\u0119 i odpowiedzie\u0107 &#8222;NIE&#8221;,<\/li>\n<li>mo\u017ce nigdy nie zatrzyma\u0107 si\u0119 i kontynuowa\u0107 obliczenie w niesko\u0144czono\u015b\u0107, co r\u00f3wnie\u017c traktujemy jako form\u0119 odpowiedzi &#8222;NIE&#8221;.<\/li>\n<\/ol>\n<p>Gdy jaki\u015b program rozstrzyga problem decyzyjny w powy\u017cszy spos\u00f3b, to m\u00f3wimy, \u017ce to problem <em>cz\u0119\u015bciowo rozstrzygalny<\/em>. Jednym z kluczowych twierdze\u0144 teorii obliczalno\u015bci jest to, \u017ce<\/p>\n<blockquote><p><em>Istniej\u0105 problemy, kt\u00f3re s\u0105 cz\u0119\u015bciowo rozstrzygalne, ale nie s\u0105 rozstrzygalne.<\/em><\/p><\/blockquote>\n<p>Przyk\u0142adami takich problem\u00f3w s\u0105<\/p>\n<ul>\n<li>Plik zawiera poprawny sk\u0142adniowo program dla naszego idealnego komputera, kt\u00f3ry uruchomiony na tym komputerze kiedy\u015b si\u0119 zatrzyma (to tzw. &#8222;problem stopu&#8221;, a dow\u00f3d w tym wypadku by\u0142 dzie\u0142em Alana Turinga)<\/li>\n<li>Plik zawiera wz\u00f3r r\u00f3wnania wielomianowego o wielu zmiennych, kt\u00f3re ma rozwi\u0105zanie z\u0142o\u017cone z liczb ca\u0142kowitych (to tzw. dziesi\u0105ty problem Hilberta, a twierdzenie o jego nierozstrzygalno\u015bci udowodni\u0142 Jurij Matijasewicz).<\/li>\n<\/ul>\n<p>Wynika z tego, \u017ce<\/p>\n<blockquote><p><em>Traktowanie braku komunikatu jako komunikatu daje nowe mo\u017cliwo\u015bci (przynajmniej w teorii obliczalno\u015bci).<\/em><\/p><\/blockquote>\n<p>Ten z pozoru optymistyczny komunikat jest w istocie pesymistyczny: wskazuje, \u017ce s\u0105 problemy obliczeniowe, dla kt\u00f3rych nie da si\u0119 unikn\u0105\u0107 czekania w niesko\u0144czono\u015b\u0107 na rozstrzygni\u0119cie dr\u0119cz\u0105cego nas pytania. A pytania wskazane jako przyk\u0142ady s\u0105 dla informatyk\u00f3w b\u0105d\u017a matematyk\u00f3w naprawd\u0119 interesuj\u0105ce.<\/p>\n<p><strong>Jerzy Tyszkiewicz<\/strong><\/p>\n<p><em>Ilustracja: Pomnik Alana Turinga w Bletchley Park, autor Stephen Kettle, zdj\u0119cie Antoine Taveneaux\/Wikimedia Commons, CC-BY SA 3.0<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Jak obiecali\u015bmy, tak robimy: dzi\u015b kolejny tekst o braku komunikatu traktowanym jako komunikat. Tym razem mowa b\u0119dzie o teorii obliczalno\u015bci, kt\u00f3ra jest dziedzin\u0105 matematyki. To istotne zastrze\u017cenie, bo terminologia i spos\u00f3b opisu poni\u017cej mog\u0105 sugerowa\u0107, \u017ce chodzi o informatyk\u0119. Tymczasem to, o czym opowiem, to twierdzenia matematyczne, kt\u00f3re niew\u0105tpliwie nale\u017c\u0105 do teorii informatyki, ale na [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60,69],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/3398"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/comments?post=3398"}],"version-history":[{"count":4,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/3398\/revisions"}],"predecessor-version":[{"id":3407,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/3398\/revisions\/3407"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/media?parent=3398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/categories?post=3398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/tags?post=3398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}