Funkcja rekurencyjna – funkcja która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:
Funkcja pierwotnie rekurencyjna Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje: Funkcja zerowa zdefiniowana jako Funkcja następnika zdefiniowana jako Funkcja rzutowania zdefiniowana jako
oraz wszystkie funkcje zbudowane z funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:
Złożenia funkcji Dla danych funkcji oraz złożeniem nazywamy funkcję zdefiniowaną jako
Rekursji prostej Dla danych funkcji oraz złożeniem rekurencyjnym nazywamy funkcję zdefiniowaną jako
Funkcja częściowo rekurencyjna Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych: Operator minimalizacji
Dla danej funkcji definiujemy funkcję w ten sposób, że wartością jest minimalne y takie, że jest zdefiniowane, oraz
Ponieważ nie dla wszystkich wartości takie y musi istnieć, funkcje częściowe rekurencyjne mogą być (w przeciwieństwie do funkcji pierwotnie rekurencyjnych) funkcjami częściowymi.
Funkcja rekurencyjna Funkcję częściowo rekurencyjną, która jest zdefiniowana dla każdego argumentu, nazywamy funkcją rekurencyjną
Przykładem funkcji która jest rekurencyjna, ale nie jest pierwotnie rekurencyjna, jest funkcja Ackermanna.
Funkcja elementarnie rekurencyjna Funkcjami elementarnie rekurencyjnymi nazywamy funkcje: funkcję następnika, funkcję odejmowania ograniczonego zdefiniowaną jako funkcję potęgowania zdefiniowaną jako
oraz wszystkie funkcje zbudowane z powyższych trzech za pomocą złożenia funkcji i operatora minimalizacji ograniczonej.
Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn Niech dana będzie pierwotnie rekurencyjna funkcja Wówczas funkcje zdefiniowana jako zdefiniowana jako
są funkcjami pierwotnie rekurencyjnymi.
Analogicznie twierdzenie zachodzi dla funkcji elementarnie rekurencyjnych.
Przykłady funkcji rekurencyjnych ciąg Fibonacciego funkcja Ackermanna symbol Newtona
Zobacz też teoria obliczeń teoria rekursji zbiór rekurencyjny złożoność obliczeniowa
Bibliografia Mycka J., Teoria funkcji rekurencyjnych, wrzesień 2000, (dostęp 27 sierpnia 2011).
Linki zewnętrzne
Kategoria:Rekurencja