Teoria rekursji - Polski Serwis Naukowy

Teoria rekursji to 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.

Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) jest hipotezą określającą możliwości komputerów i innych maszyn obliczeniowych. Mówi ona, że każdy problem, dla którego przy nieograniczonej pamięci oraz zasobach istnieje efektywny algorytm jego rozwiązywania, da się rozwiązać na maszynie Turinga. Hipoteza jest niemożliwa do sprawdzenia matematycznie, ponieważ łączy w sobie zarówno ścisłe, jak i nieprecyzyjne sformułowania, których interpretacja może zależeć od konkretnej osoby. Dlatego traktowana jest bardziej jako aksjomat lub swoiste prawo.

Alan Mathison Turing (ur. 23 czerwca 1912 w Londynie, zm. 7 czerwca 1954 w Wilmslow) – angielski matematyk, kryptolog, twórca pojęcia maszyny Turinga i jeden z twórców informatyki.

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ń 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ń.

Zbiór (niegdyś mnogość, wielość) – jedno z fundamentalnych pojęć współczesnej matematyki, w teorii mnogości (teorii zbiorów) przyjmowane jako pojęcie pierwotne. Intuicyjnie: kolekcja, zestaw niepowtarzających się obiektów bez wyróżnionej kolejności nazywanych elementami.

Problem NP (niedeterministycznie wielomianowy, ang. nondeterministic polynomial) to problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.

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.

Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.

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.

Relacja – w teorii mnogości dowolny podzbiór iloczynu kartezjańskiego skończonej liczby zbiorów; definicja ta oddaje intuicję pewnego związku, czy zależności między elementami wspomnianych zbiorów (elementy wspomnianych zbiorów pozostają w związku albo łączy je pewna zależność, czy też własność lub nie). Najważniejszymi relacjami są relacje dwuargumentowe, tj. między elementami pary zbiorów (opisane w osobnym artykule, w tym funkcje i działania jednoargumentowe); relacje jednoargumentowe to po prostu podzbiory pewnego zbioru.

Rekurencja albo rekursja (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie. Wbrew próbom rozróżnienia terminów [potrzebne źródło] rekursja i rekurencja w rzeczywistości słowa te mają identyczne znaczenie[potrzebne źródło].

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 zabezpieczenia sieci komputerowych przed włamaniami (chodzi o to, żeby złamanie tych zabezpieczeń musiało trwać dostatecznie długo – czyli aby zabierało "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.

Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb.

Zobacz też

maszyna Turinga