Funkcja rekurencyjna

Funkcja rekurencyjna – funkcja ${\displaystyle \mathbb {N} ^{i}\to \mathbb {N} ,}$ 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

${\displaystyle Z\colon \mathbb {N} \to \mathbb {N} ,}$ zdefiniowana jako ${\displaystyle {\begin{matrix}Z(n)=0\end{matrix}}}$

• Funkcja następnika

${\displaystyle S\colon \mathbb {N} \to \mathbb {N} ,}$ zdefiniowana jako ${\displaystyle {\begin{matrix}S(n)=n+1\end{matrix}}}$

• Funkcja rzutowania

${\displaystyle I_{n}^{i}\colon \mathbb {N} ^{n}\to \mathbb {N} ,}$ zdefiniowana jako ${\displaystyle I_{n}^{i}(x_{1},\dots ,x_{n})=x_{i},\ i\leqslant n}$

oraz wszystkie funkcje zbudowane z funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:

• Złożenia funkcji

Dla danych funkcji ${\displaystyle f\colon \mathbb {N} ^{k}\to \mathbb {N} }$ oraz ${\displaystyle g_{1},\dots ,g_{k}\colon \mathbb {N} ^{n}\to \mathbb {N} ,}$ złożeniem nazywamy funkcję

${\displaystyle h\colon \mathbb {N} ^{n}\to \mathbb {N} ,}$ zdefiniowaną jako ${\displaystyle h({\overline {n}})=f(g_{1}({\overline {n}}),\dots ,g_{k}({\overline {n}}))}$

• Rekursji prostej

Dla danych funkcji ${\displaystyle g\colon \mathbb {N} ^{n}\to \mathbb {N} }$ oraz ${\displaystyle h\colon \mathbb {N} ^{n+2}\to \mathbb {N} ,}$ złożeniem rekurencyjnym nazywamy funkcję

${\displaystyle f\colon \mathbb {N} ^{n+1}\to \mathbb {N} }$ zdefiniowaną jako ${\displaystyle {\begin{cases}f({\overline {n}},0)=g({\overline {n}})\\f({\overline {n}},S(m))=h(f({\overline {n}},m),{\overline {n}},m)\end{cases}}}$

Funkcja częściowo rekurencyjna

Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych:

• Operator minimalizacji

Dla danej funkcji ${\displaystyle f\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,}$ definiujemy funkcję ${\displaystyle h\colon \mathbb {N} ^{n}\to \mathbb {N} }$ w ten sposób, że wartością ${\displaystyle h(x_{1},x_{2},\dots ,x_{n})}$ jest minimalne y takie, że

${\displaystyle \forall _{x\leqslant y}f(x,x_{1},x_{2},\dots ,x_{n})}$ jest zdefiniowane, oraz

${\displaystyle f(y,x_{1},x_{2},\dots ,x_{n})=0.}$

Ponieważ nie dla wszystkich wartości ${\displaystyle x_{1},\dots x_{n}}$ 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

${\displaystyle {\dot {-}}\colon \mathbb {N} ^{2}\to \mathbb {N} ,}$ zdefiniowaną jako ${\displaystyle {\dot {-}}(x,y)={\begin{cases}{0,\ x<y}\\{x-y,\ x\geqslant y}\end{cases}},}$

• funkcję potęgowania

${\displaystyle pow\colon \mathbb {N} ^{2}\to \mathbb {N} ,}$ zdefiniowaną jako ${\displaystyle {\begin{matrix}pow(x,y)=x^{y}\end{matrix}}.}$

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 ${\displaystyle f\colon \mathbb {N} ^{n+1}\to \mathbb {N} .}$ Wówczas funkcje

${\displaystyle h_{1}\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,}$ zdefiniowana jako ${\displaystyle h_{1}({\overline {n}},m)=\sum _{i=0}^{m}f({\overline {n}},i),}$

${\displaystyle h_{2}\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,}$ zdefiniowana jako ${\displaystyle h_{2}({\overline {n}},m)=\prod _{i=0}^{m}f({\overline {n}},i)}$

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, [1] (dostęp 27 sierpnia 2011).

Linki zewnętrzne

• PiergiorgioP. Odifreddi PiergiorgioP., S. BarryS.B. Cooper S. BarryS.B., Recursive Functions, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 11 maja 2012, ISSN 1095-5054 [dostęp 2017-12-30]  (ang.). (Funkcje rekurencyjne)