b'\n_START_ARTICLE_\nTeoria rekursji\n_START_PARAGRAPH_\nTeoria rekursji to dzia\xc5\x82 logiki matematycznej, kt\xc3\xb3rego pocz\xc4\x85tki si\xc4\x99gaj\xc4\x85 lat trzydziestych XX wieku. Do jego powstania i rozwoju w znacznym stopniu przyczynili si\xc4\x99 mi\xc4\x99dzy innymi Alan Turing i Stephen Cole Kleene._NEWLINE_Teoria rekursji zaczyna od badania obiekt\xc3\xb3w (na przyk\xc5\x82ad funkcji, relacji czy zbior\xc3\xb3w), kt\xc3\xb3re nazywa si\xc4\x99 rekurencyjnymi. Funkcje rekurencyjne to takie funkcje o argumentach i warto\xc5\x9bciach nale\xc5\xbc\xc4\x85cych do zbioru liczb naturalnych, kt\xc3\xb3re albo s\xc4\x85 szczeg\xc3\xb3lnie prostej postaci (jak funkcja sta\xc5\x82a czy funkcja identyczno\xc5\x9bciowa), albo powstaj\xc4\x85 z tych pierwszych w wyniku zastosowania sko\xc5\x84czonej liczby \xe2\x80\x9eporz\xc4\x85dnych\xe2\x80\x9d operacji (takich jak sk\xc5\x82adanie funkcji czy definiowanie rekurencyjne). Natomiast zbi\xc3\xb3r jest rekurencyjny, gdy jego funkcja charakterystyczna jest rekurencyjna. Funkcje rekurencyjne s\xc4\x85 modelem (w sensie nieformalnym) funkcji czy relacji \xe2\x80\x9eobliczalnych\xe2\x80\x9d, to znaczy takich kt\xc3\xb3rych warto\xc5\x9b\xc4\x87 dla dowolnych argument\xc3\xb3w mo\xc5\xbcna poda\xc4\x87 w sko\xc5\x84czonej liczbie krok\xc3\xb3w w spos\xc3\xb3b mechaniczny._NEWLINE_Obiekty rekurencyjne mo\xc5\xbcna te\xc5\xbc zdefiniowa\xc4\x87 w pozornie inny (lecz tak naprawd\xc4\x99 r\xc3\xb3wnowa\xc5\xbcny) spos\xc3\xb3b. Mianowicie podzbi\xc3\xb3r A zbioru liczb naturalnych nazywamy rekurencyjnym, je\xc5\x9bli istnieje algorytm rozstrzygaj\xc4\x85cy dla ka\xc5\xbcdej liczby naturalnej czy nale\xc5\xbcy ona do zbioru A, czy nie. Okre\xc5\x9blone w ten spos\xc3\xb3b poj\xc4\x99cie zbioru rekurencyjnego nie tylko jest identyczne z podanym powy\xc5\xbcej, lecz nawet nie zale\xc5\xbcy od tego, jaki model oblicze\xc5\x84 (przyk\xc5\x82ady zobacz w: funkcja rekurencyjna, teoria oblicze\xc5\x84, teoria obliczalno\xc5\x9bci) wybierzemy do wykonywania algorytm\xc3\xb3w. R\xc3\xb3wnowa\xc5\xbcno\xc5\x9b\xc4\x87 wszystkich \xe2\x80\x9esensownych\xe2\x80\x9d modeli oblicze\xc5\x84 jest postulowana w tezie Churcha, wed\xc5\x82ug kt\xc3\xb3rej to czy zbi\xc3\xb3r (funkcja, relacja) jest obliczalny, czy te\xc5\xbc nie, nie zale\xc5\xbcy od wyboru modelu oblicze\xc5\x84._NEWLINE_Po obiektach rekurencyjnych nast\xc4\x99pny stopie\xc5\x84 z\xc5\x82o\xc5\xbcono\xc5\x9bci prezentuj\xc4\x85 obiekty rekurencyjnie przeliczalne. Je\xc5\x9bli relacja R(m(1),...,m(k),n(1),...,n(l)) jest rekurencyjna, to relacja \xe2\x80\x9eistniej\xc4\x85 takie m(1),...,m(k), \xc5\xbce R(m(1),...,m(k),n(1),...,n(l))\xe2\x80\x9d jest rekurencyjnie przeliczalna. Dodaj\xc4\x85c w definicji relacji kolejne kwantyfikatory og\xc3\xb3lne i egzystencjalne w spos\xc3\xb3b naprzemienny, uzyskujemy nowe relacje, kt\xc3\xb3re maj\xc4\x85 (a w ka\xc5\xbcdym razie mog\xc4\x85 mie\xc4\x87) coraz wi\xc4\x99kszy stopie\xc5\x84 z\xc5\x82o\xc5\xbcono\xc5\x9bci. W ten spos\xc3\xb3b powstaje ca\xc5\x82a hierarchia obiekt\xc3\xb3w, nazywana hierarchi\xc4\x85 arytmetyczn\xc4\x85, kt\xc3\xb3rej \xe2\x80\x9epi\xc4\x99tra\xe2\x80\x9d mo\xc5\xbcna ponumerowa\xc4\x87 liczbami naturalnymi._NEWLINE_Nast\xc4\x99pnym krokiem jest dalsze komplikowanie rozwa\xc5\xbcanych obiekt\xc3\xb3w, kt\xc3\xb3re skutkuje przed\xc5\x82u\xc5\xbceniem hierarchii arytmetycznej do jeszcze og\xc3\xb3lniejszej hierarchii analitycznej. Teoria rekursji zajmuje si\xc4\x99 konstrukcj\xc4\x85 i szczeg\xc3\xb3\xc5\x82owym badaniem tego typu hierarchii oraz szukaniem odpowiedzi na pytania w rodzaju: \xe2\x80\x9ejak skomplikowany jest dany zbi\xc3\xb3r (relacja, funkcja)?\xe2\x80\x9d, \xe2\x80\x9ena kt\xc3\xb3rym pi\xc4\x99trze w badanej hierarchii mo\xc5\xbcna go umie\xc5\x9bci\xc4\x87?\xe2\x80\x9d, \xe2\x80\x9ena jakim poziomie stabilizuje si\xc4\x99 dana hierarchia?\xe2\x80\x9d. Pytania te, jakkolwiek \xc5\x82atwe do formu\xc5\x82owania, okazuj\xc4\x85 si\xc4\x99 cz\xc4\x99sto bardzo trudne. Teoria rekursji we wsp\xc3\xb3\xc5\x82czesnym stanie jest wysoce abstrakcyjn\xc4\x85 dziedzin\xc4\x85, kt\xc3\xb3r\xc4\x85 zajmuje si\xc4\x99 stosunkowo niewielka liczba badaczy.\n_START_SECTION_\nZwi\xc4\x85zek z informatyk\xc4\x85\n_START_PARAGRAPH_\nNa gruncie teorii rekursji powsta\xc5\x82a w drugiej po\xc5\x82owie XX wieku teoria oblicze\xc5\x84, kt\xc3\xb3ra stanowi obecnie wa\xc5\xbcny dzia\xc5\x82 informatyki teoretycznej. Na pewnych wynikach tej teorii oparte zosta\xc5\x82y m.in. systemy zabezpiecze\xc5\x84 sieci komputerowych przed w\xc5\x82amaniami. W tym przypadku podstawowym za\xc5\x82o\xc5\xbceniem jest, by \xc5\x82amanie zabezpiecze\xc5\x84 trwa\xc5\x82o dostatecznie d\xc5\x82ugo \xe2\x80\x93 czyli \xe2\x80\x9eniewielomianowo\xe2\x80\x9d wiele czasu. Ma to zwi\xc4\x85zek z bardzo wa\xc5\xbcn\xc4\x85 i dotychczas nierozstrzygni\xc4\x99t\xc4\x85 hipotez\xc4\x85 P=NP, kt\xc3\xb3ra dotyczy istnienia szybkich (czyli dzia\xc5\x82aj\xc4\x85cych w czasie wielomianowym) algorytm\xc3\xb3w dla pewnej klasy problem\xc3\xb3w.'