b'\n_START_ARTICLE_\nProblem nierozstrzygalny\n_START_PARAGRAPH_\nProblem nierozstrzygalny \xe2\x80\x93 problem decyzyjny, dla kt\xc3\xb3rego nie istnieje algorytm, kt\xc3\xb3ry po sko\xc5\x84czonej liczbie krok\xc3\xb3w i dla dowolnych danych wej\xc5\x9bciowych jednoznacznie odpowie tak lub nie._NEWLINE_Turing w 1936 roku wykaza\xc5\x82, \xc5\xbce udzielenie odpowiedzi na pytanie, czy maszyna Turinga o numerze  wykonuj\xc4\x85c dzia\xc5\x82ania nad liczb\xc4\x85  zako\xc5\x84czy kiedy\xc5\x9b swoj\xc4\x85 prac\xc4\x99, czy te\xc5\xbc przewidziany dla niej algorytm b\xc4\x99dzie realizowany w niesko\xc5\x84czono\xc5\x9b\xc4\x87, jest problemem nierozstrzygalnym (patrz: problem stopu)._NEWLINE_Innym przyk\xc5\x82adem problemu nierozstrzygalnego jest tzw. zdanie G\xc3\xb6dla o postaci 17 Gen r (generalizacja {kwantyfikator og\xc3\xb3lny} formu\xc5\x82y r wzgl\xc4\x99dem zmiennej z numerem 17). Jest to zdanie posiadaj\xc4\x85ce t\xc4\x99 w\xc5\x82asno\xc5\x9b\xc4\x87, \xc5\xbce ani ono, ani jego negacja nie daj\xc4\x85 si\xc4\x99 formalnie dowie\xc5\x9b\xc4\x87. Zdanie nierozstrzygalne 17 gen r powsta\xc5\x82o w wyniku odwzorowania antynomii logicznej (zwanej antynomi\xc4\x85 Richarda) poprzez tak zwan\xc4\x85 arytmetyzacj\xc4\x85 j\xc4\x99zyka klasycznego rachunku zda\xc5\x84. Arytmetyzacja j\xc4\x99zyka pozwala na odwzorowanie relacji logicznych jakie zachodz\xc4\x85 mi\xc4\x99dzy zdaniami w relacje arytmetyczne mi\xc4\x99dzy liczbami stanowi\xc4\x85cymi numery tych zda\xc5\x84. Dzi\xc4\x99ki temu zamiast o relacjach logicznych mo\xc5\xbcna m\xc3\xb3wi\xc4\x87 o relacjach arytmetycznych._NEWLINE_Istnienie zdania 17 gen r jest powodem nierozstrzygalno\xc5\x9bci arytmetyki, uwa\xc5\xbcanej do czas\xc3\xb3w G\xc3\xb6dla za system rozstrzygalny, to znaczy taki, w kt\xc3\xb3rym prawdziwo\xc5\x9b\xc4\x87 ka\xc5\xbcdego twierdzenia mo\xc5\xbcna rozstrzygn\xc4\x85\xc4\x87 w oparciu o sko\xc5\x84czony zbi\xc3\xb3r kryteri\xc3\xb3w. Inaczej m\xc3\xb3wi\xc4\x85c, zbi\xc3\xb3r twierdze\xc5\x84 arytmetycznych jest nieobliczalny, co znaczy, \xc5\xbce nie mo\xc5\xbcna w sko\xc5\x84czonej ilo\xc5\x9bci krok\xc3\xb3w rozstrzygn\xc4\x85\xc4\x87, czy dany element tego zbioru, b\xc4\x99d\xc4\x85cy twierdzeniem arytmetycznym, jest, czy nie jest elementem zbioru twierdze\xc5\x84. Tymczasem zbi\xc3\xb3r dowod\xc3\xb3w systemu formalnego jest obliczalny, poniewa\xc5\xbc w sko\xc5\x84czonej ilo\xc5\x9bci krok\xc3\xb3w mo\xc5\xbcna rozstrzygn\xc4\x85\xc4\x87, czy dany ci\xc4\x85g napis\xc3\xb3w jest, czy nie jest dowodem danego twierdzenia._NEWLINE_Tak wi\xc4\x99c zbi\xc3\xb3r zda\xc5\x84 prawdziwych nie pokrywa si\xc4\x99 ze zbiorem twierdze\xc5\x84 dowodzonych przez system. Wiemy bowiem, \xc5\xbce istniej\xc4\x85 zdania prawdziwe, kt\xc3\xb3rych nie da si\xc4\x99 dowie\xc5\x9b\xc4\x87 w tym systemie. Jednym z nich jest w\xc5\x82a\xc5\x9bnie zdanie 17 Gen r.\n_START_SECTION_\nNierozstrzygalno\xc5\x9b\xc4\x87 problemu r\xc3\xb3wnowa\xc5\xbcno\xc5\x9bci dla rachunku lambda\n_START_PARAGRAPH_\nWyobra\xc5\xbamy sobie, \xc5\xbce istnieje algorytm w postaci \xce\xbb-wyra\xc5\xbcenia  rozstrzygaj\xc4\x85cy, czy dwa \xce\xbb-wyra\xc5\xbcenia s\xc4\x85 r\xc3\xb3wnowa\xc5\xbcne:_NEWLINE_algorytm bierze cztery wyra\xc5\xbcenia, po czym zwraca trzecie, je\xc5\x9bli dwa pierwsze s\xc4\x85 r\xc3\xb3wnowa\xc5\xbcne lub czwarte w przeciwnym wypadku._NEWLINE_Je\xc5\x9bli  zwr\xc3\xb3ci true, wyra\xc5\xbcenie zwr\xc3\xb3ci false, je\xc5\x9bli  zwr\xc3\xb3ci false, wyra\xc5\xbcenie zwr\xc3\xb3ci true.\n_START_SECTION_\nNierozstrzygalno\xc5\x9b\xc4\x87 problemu s\xc5\x82owa dla p\xc3\xb3\xc5\x82grup\n_START_PARAGRAPH_\nProblemem jest rozstrzygni\xc4\x99cie, czy   dla dowolnej struktury spe\xc5\x82niaj\xc4\x85cej sko\xc5\x84czony zbi\xc3\xb3r r\xc3\xb3wnowa\xc5\xbcno\xc5\x9bci . Naturaln\xc4\x85 reprezentacj\xc4\x85 p\xc3\xb3\xc5\x82grup s\xc4\x85 ci\xc4\x85gi element\xc3\xb3w nad sko\xc5\x84czonym alfabetem z dzia\xc5\x82aniem konkatenacji, st\xc4\x85d nazwa problemu.\n_START_SECTION_\nNierozstrzygalno\xc5\x9b\xc4\x87 problemu pokrycia p\xc5\x82aszczyzny\n_START_PARAGRAPH_\nPrzypu\xc5\x9b\xc4\x87my, \xc5\xbce dysponujemy sko\xc5\x84czonym zbiorem jednostkowych kwadrat\xc3\xb3w ze zdefiniowanymi kolorami kraw\xc4\x99dzi poziomych i pionowych. Przedmiotem problemu jest pytanie, czy mo\xc5\xbcliwe jest pokrycie p\xc5\x82aszczyzny euklidesowej elementami tego zbioru, stosuj\xc4\x85c jedynie translacje (bez obrot\xc3\xb3w) przy za\xc5\x82o\xc5\xbceniu, \xc5\xbce s\xc4\x85siaduj\xc4\x85ce kraw\xc4\x99dzie dowolnej pary kwadrat\xc3\xb3w musz\xc4\x85 mie\xc4\x87 ten sam kolor. Nie istnieje og\xc3\xb3lny algorytm odpowiadaj\xc4\x85cy na tak postawione pytanie w sko\xc5\x84czonej liczbie krok\xc3\xb3w._NEWLINE_Je\xc5\xbceli dla danego zbioru p\xc5\x82ytek pokrycie nie istnieje lub istnieje pokrycie okresowe (symetryczne wzgl\xc4\x99dem pewnej niezerowej translacji), to odpowied\xc5\xba na wy\xc5\xbcej postawione pytanie zawsze mo\xc5\xbcna uzyska\xc4\x87 w sko\xc5\x84czonej liczbie krok\xc3\xb3w, po prostu pokazuj\xc4\x85c wystarczaj\xc4\x85co szeroki obszar p\xc5\x82aszczyzny, kt\xc3\xb3rego nie da si\xc4\x99 pokry\xc4\x87 lub (w przypadku pokrycia okresowego), kt\xc3\xb3ry mo\xc5\xbcna pokry\xc4\x87 w ca\xc5\x82o\xc5\x9bci._NEWLINE_Mo\xc5\xbcna r\xc3\xb3wnie\xc5\xbc poda\xc4\x87 pewne kryteria, pozwalaj\xc4\x85ce dowie\xc5\x9b\xc4\x87 w niekt\xc3\xb3rych przypadkach, \xc5\xbce istnieje pokrycie nieokresowe (jak w przypadku pokazanym na obrazku po prawej), jednak \xc5\xbcaden sko\xc5\x84czony zbi\xc3\xb3r kryteri\xc3\xb3w nie wystarcza do uwzgl\xc4\x99dnienia wszystkich przypadk\xc3\xb3w zbior\xc3\xb3w kwadrat\xc3\xb3w, dla kt\xc3\xb3rych istnieje jedynie pokrycie nieokresowe.'