Teoria rekursji

Wygląd przypnij ukryj

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.

Zobacz też

• maszyna Turinga
• NP

Podstawy matematyki

logika matematyczna	algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów
metamatematyka	metalogika
teoria mnogości	opisowa arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF
teoria obliczeń	teoria obliczalności teoria złożoności
inne	teoria kategorii filozofia matematyki

Działy matematyki

działy ogólne	według trudności matematyka elementarna matematyka wyższa według celu matematyka czysta matematyka stosowana inne matematyka doświadczalna matematyka parakonsystentna supermatematyka
działy czyste	algebra elementarna liniowa i wieloliniowa abstrakcyjna algebra przemienna algebra lokalna teoria Galois różniczkowa teoria Galois teoria grup geometryczna teoria grup teoria Liego homologiczna różniczkowa uniwersalna teoria reprezentacji analiza matematyczna analiza algebraiczna analiza funkcjonalna teoria spektralna analiza geometryczna analiza globalna analiza harmoniczna analiza mikrolokalna analiza na rozmaitościach analiza niestandardowa analiza numeryczna nomografia analiza p-adyczna analiza rzeczywista analiza wektorowa analiza wielowymiarowa analiza wypukła analiza zespolona rachunek różniczkowy i całkowy rachunek wariacyjny teoria dystrybucji teoria miary teoria potencjału arytmetyka elementarna teoretyczna lub wyższa, in. teoria liczb algebraiczna algorytmiczna analityczna elementarna geometryczna teoria sit geometria absolutna afiniczna algebraiczna analityczna arytmetyczna diofantyczna dyskretna euklidesowa planimetria stereometria fraktalna inwersyjna kombinatoryczna konforemna metryczna nieeuklidesowa eliptyczna hiperboliczna sferyczna nieprzemienna obliczeniowa różniczkowa symplektyczna rzutowa skończona syntetyczna tropikalna uporządkowania wykreślna zespolona trygonometria sferyczna matematyka dyskretna kombinatoryka teoria Ramseya teoria grafów algebraiczna geometryczna spektralna topologiczna podstawy logika matematyczna algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów metamatematyka metalogika teoria kategorii teoria mnogości opisowa arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF teoria obliczeń teoria obliczalności teoria złożoności teoria układów dynamicznych teoria chaosu teoria katastrof teoria ergodyczna topologia algebraiczna teoria homotopii geometryczna mnogościowa ogólna różniczkowa teoria Morse’a teoria położenia teoria węzłów teoria warkoczy teoria wymiaru pozostałe K-teoria probabilistyka rachunek różnicowy teoria osobliwości teoria porządku teoria punktu stałego
działy stosowane	nauki przyrodnicze biomatematyka chemia matematyczna fizyka matematyczna nauki społeczne ekonomia matematyczna lingwistyka matematyczna matematyka finansowa matematyka ubezpieczeniowa psychologia matematyczna socjologia matematyczna teoria głosowań nauki techniczne kryptologia teoria informacji teoria kolejek teoria sterowania statystyka matematyczna rachunek wyrównawczy statystyka nieparametryczna teoria estymacji inne teoria gier teoria decyzji
powiązane dyscypliny	ściśle naukowe dydaktyka matematyki historia matematyki inne filozofia matematyki matematyka rekreacyjna numerologia pseudomatematyka

Encyklopedia internetowa (zdublowana strona w projekcie Wikimedia):

• Britannica: topic/recursion-theory