b'\n_START_ARTICLE_\nHipoteza Churcha-Turinga\n_START_PARAGRAPH_\nHipoteza Churcha-Turinga (zwana r\xc3\xb3wnie\xc5\xbc Tez\xc4\x85 Churcha-Turinga) jest hipotez\xc4\x85 okre\xc5\x9blaj\xc4\x85c\xc4\x85 mo\xc5\xbcliwo\xc5\x9bci komputer\xc3\xb3w i innych maszyn obliczeniowych. M\xc3\xb3wi ona, \xc5\xbce ka\xc5\xbcdy problem, dla kt\xc3\xb3rego przy nieograniczonej pami\xc4\x99ci oraz zasobach istnieje efektywny algorytm jego rozwi\xc4\x85zywania, da si\xc4\x99 rozwi\xc4\x85za\xc4\x87 na maszynie Turinga. Hipotezy tej nie da si\xc4\x99 \xc5\x9bci\xc5\x9ble sformu\xc5\x82owa\xc4\x87 w j\xc4\x99zyku matematyki, poniewa\xc5\xbc \xc5\x82\xc4\x85czy w sobie zar\xc3\xb3wno \xc5\x9bcis\xc5\x82e, jak i nieprecyzyjne sformu\xc5\x82owania, kt\xc3\xb3rych interpretacja mo\xc5\xbce zale\xc5\xbce\xc4\x87 od konkretnej osoby. Dlatego traktowana jest bardziej jako filozoficzny punkt widzenia._NEWLINE_Hipoteza pozwala dok\xc5\x82adniej sformu\xc5\x82owa\xc4\x87 poj\xc4\x99cie samego algorytmu, m\xc3\xb3wi\xc4\x85c jednocze\xc5\x9bnie, \xc5\xbce komputery s\xc4\x85 w stanie go wykona\xc4\x87. Co wi\xc4\x99cej, wszystkie komputery maj\xc4\x85 jednakowe mo\xc5\xbcliwo\xc5\x9bci, je\xc5\x9bli chodzi o zdolno\xc5\x9b\xc4\x87 do ich wykonywania, a nie dost\xc4\x99pne zasoby oraz \xc5\xbce nie jest mo\xc5\xbcliwe zbudowanie komputera o zdolno\xc5\x9bci do rozwi\xc4\x85zywania wi\xc4\x99kszej liczby problem\xc3\xb3w, ni\xc5\xbc najprostsza maszyna Turinga._NEWLINE_Hipotez\xc4\x99 zaproponowa\xc5\x82 po raz pierwszy Stephen Cole Kleene w 1943 roku, lecz zosta\xc5\x82a ona nazwana od Alonzo Churcha i Alana Turinga.\n_START_SECTION_\nNierozwi\xc4\x85zywalne problemy\n_START_PARAGRAPH_\nIstniej\xc4\x85 funkcje oraz problemy, kt\xc3\xb3re s\xc4\x85 niemo\xc5\xbcliwe do obliczenia za pomoc\xc4\x85 maszyny Turinga. Dla takich problem\xc3\xb3w, zawsze istnieje zestaw danych, dla kt\xc3\xb3rych dowolny zaproponowany algorytm nie zatrzyma si\xc4\x99 lub da b\xc5\x82\xc4\x99dn\xc4\x85 odpowied\xc5\xba. W przypadku funkcji, operuj\xc4\x85c na liczbach naturalnych, mog\xc4\x85 one produkowa\xc4\x87 niezwykle du\xc5\xbce wyniki. Jedn\xc4\x85 z najs\xc5\x82ynniejszych takich funkcji jest Busy Beaver. Okre\xc5\x9bla ona maksymaln\xc4\x85 ilo\xc5\x9b\xc4\x87 pracy, jak\xc4\x85 mo\xc5\xbce wykona\xc4\x87 maszyna Turinga o zadanej z g\xc3\xb3ry liczbie stan\xc3\xb3w n (argument funkcji), przy czym nie uwzgl\xc4\x99dniamy tutaj maszyn dzia\xc5\x82aj\xc4\x85cych w niesko\xc5\x84czono\xc5\x9b\xc4\x87. Naukowcy potrafi\xc4\x85 poda\xc4\x87 jedynie prawid\xc5\x82owy wynik dla pierwszych czterech liczb naturalnych, natomiast dla kolejnych znane jest tylko dolne oszacowanie. Funkcja ta ma wiele powi\xc4\x85za\xc5\x84 z problemem stopu, kt\xc3\xb3ry tak\xc5\xbce jest nierozwi\xc4\x85zywalny.'