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 innymiAlan TuringiStephen Cole Kleene.
Teoriarekursjizaczyna od badania obiektów (na przykładfunkcji,relacjiczyzbiorów), które nazywa sięrekurencyjnymi.Funkcje rekurencyjneto takie funkcje o argumentach i wartościach należących do zbioruliczb naturalnych,które albo są szczególnie prostej postaci (jakfunkcja stałaczy funkcja identycznościowa), albo powstają z tych pierwszych w wyniku zastosowania skończonej liczby „porządnych” operacji (takich jakskładanie funkcjiczy definiowanie rekurencyjne). Natomiast zbiór jest rekurencyjny, gdy jegofunkcja charakterystycznajest 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.
Obiektyrekurencyjnemożna też zdefiniować w pozornie inny (lecz tak naprawdę równoważny) sposób. Mianowicie podzbiórAzbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istniejealgorytmrozstrzygający dla każdej liczby naturalnej czy należy ona do zbioruA,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, jakimodel 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 wtezie 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ą obiektyrekurencyjnie przeliczalne.Jeśli relacjaR(m(1),...,m(k),n(1),...,n(l)) jest rekurencyjna, to relacja „istnieją takie m(1),...,m(k), żeR(m(1),...,m(k),n(1),...,n(l))” jest rekurencyjnie przeliczalna. Dodając w definicji relacji kolejnekwantyfikatory ogólnei 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, nazywanahierarchią 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żeniemhierarchii arytmetycznejdo jeszcze ogólniejszejhierarchii 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ą
[edytuj|edytuj kod]Na gruncie teorii rekursji powstała w drugiej połowieXX wiekuteoria obliczeń,która stanowi obecnie ważny dział informatyki teoretycznej. Na pewnych wynikach tej teorii oparte zostały m.in. systemy zabezpieczeńsieci komputerowychprzed 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.