Teoria rekursji
Teoria rekursji – dział logiki matematycznej, którego początki sięgają lat trzydziestych XX wieku. Do jego powstania i rozwoju w znacznym stopniu przyczynili się między innymi Alan Turing i Stephen Cole Kleene.
Teoria rekursji zaczyna od badania obiektów (na przykład funkcji, relacji czy zbiorów), które nazywa się rekurencyjnymi. Funkcje rekurencyjne to takie funkcje o argumentach i wartościach należących do zbioru liczb naturalnych, które albo są szczególnie prostej postaci (jak funkcja stała czy funkcja identycznościowa), albo powstają z tych pierwszych w wyniku zastosowania skończonej liczby „porządnych” operacji (takich jak składanie funkcji czy definiowanie rekurencyjne). Natomiast zbiór jest rekurencyjny, gdy jego funkcja charakterystyczna jest rekurencyjna. Funkcje rekurencyjne są modelem (w sensie nieformalnym) funkcji czy relacji „obliczalnych”, to znaczy takich których wartość dla dowolnych argumentów można podać w skończonej liczbie kroków w sposób mechaniczny.
Obiekty rekurencyjne można też zdefiniować w pozornie inny (lecz tak naprawdę równoważny) sposób. Mianowicie podzbiór A zbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istnieje algorytm rozstrzygający dla każdej liczby naturalnej czy należy ona do zbioru A, czy nie. Określone w ten sposób pojęcie zbioru rekurencyjnego nie tylko jest identyczne z podanym powyżej, lecz nawet nie zależy od tego, jaki model obliczeń (przykłady zobacz w: funkcja rekurencyjna, teoria obliczeń, teoria obliczalności) wybierzemy do wykonywania algorytmów. Równoważność wszystkich „sensownych” modeli obliczeń jest postulowana w tezie Churcha, według której to czy zbiór (funkcja, relacja) jest obliczalny, czy też nie, nie zależy od wyboru modelu obliczeń.
Po obiektach rekurencyjnych następny stopień złożoności prezentują obiekty rekurencyjnie przeliczalne. Jeśli relacja R(m(1),...,m(k),n(1),...,n(l)) jest rekurencyjna, to relacja „istnieją takie m(1),...,m(k), że R(m(1),...,m(k),n(1),...,n(l))” jest rekurencyjnie przeliczalna. Dodając w definicji relacji kolejne kwantyfikatory ogólne i egzystencjalne w sposób naprzemienny, uzyskujemy nowe relacje, które mają (a w każdym razie mogą mieć) coraz większy stopień złożoności. W ten sposób powstaje cała hierarchia obiektów, nazywana hierarchią arytmetyczną, której „piętra” można ponumerować liczbami naturalnymi.
Następnym krokiem jest dalsze komplikowanie rozważanych obiektów, które skutkuje przedłużeniem hierarchii arytmetycznej do jeszcze ogólniejszej hierarchii analitycznej. Teoria rekursji zajmuje się konstrukcją i szczegółowym badaniem tego typu hierarchii oraz szukaniem odpowiedzi na pytania w rodzaju: „jak skomplikowany jest dany zbiór (relacja, funkcja)?”, „na którym piętrze w badanej hierarchii można go umieścić?”, „na jakim poziomie stabilizuje się dana hierarchia?”. Pytania te, jakkolwiek łatwe do formułowania, okazują się często bardzo trudne. Teoria rekursji we współczesnym stanie jest wysoce abstrakcyjną dziedziną, którą zajmuje się stosunkowo niewielka liczba badaczy.
Związek z informatyką
Na gruncie teorii rekursji powstała w drugiej połowie XX wieku teoria obliczeń, która stanowi obecnie ważny dział informatyki teoretycznej. Na pewnych wynikach tej teorii oparte zostały m.in. systemy zabezpieczeń sieci komputerowych przed włamaniami. W tym przypadku podstawowym założeniem jest, by łamanie zabezpieczeń trwało dostatecznie długo – czyli „niewielomianowo” wiele czasu. Ma to związek z bardzo ważną i dotychczas nierozstrzygniętą hipotezą P=NP, która dotyczy istnienia szybkich (czyli działających w czasie wielomianowym) algorytmów dla pewnej klasy problemów.